Arbres binaires de recherche [br] Algorithmique
Un arbre binaire de recherche est une structure de donnée qui permet de représen- sont l'insertion la suppression et la recherche d'une valeur.
Algorithmes sur les arbres binaires de recherche
Seconde implémentation : Arbre Binaire de Recherche Recherche puis suppression dans le cas où l'élément est dans une feuille. `a supprimer.
Programmation fonctionnelle
23 nov. 2011 Un arbre binaire est ordonné (ou de recherche) par rapport `a une ... La suppression d'un élément x dans un arbre binaire de recherche.
ARBRES BINAIRES DE RECHERCHE
temps de ?(logn) au pire tableau trié : insertion/suppression en ?(n) au pire cas Dans un arbre binaire de recherche chaque nœud a une clé.
INF601 : Algorithme et Structure de données - Cours 2 : TDA Arbre
27 févr. 2010 6 Suppression d'un élément ... adjonction et suppression peuvent être en O(n) ... celle de l'arbre binaire de recherche ...
Les arbres binaires de recherche équilibrés
10 Correction d'un arbre rouge-noir après une suppression (cas 2) . La propriété d'arbre binaire de recherche permet de trouver d'insérer ou de.
INF421-a Bases de la programmation et de lalgorithmique Tas
7 oct. 2005 Arbres binaires de recherche. Supprimer dans un tas (la racine). On enl`eve la racine du tas. ? Retasser : le contenu du nœud le plus `a ...
Programmation avancée - Chapitre 1 : Complexité et les ABR
Recherche. Ajout aux feuilles. Ajout à la racine. Suppression. Analyse. Programmation avancée. Chapitre 1 : Complexité et les ABR (arbres binaires de.
Arbres binaires de recherche
Question 8 (Suppression). ´Ecrivez une fonction remove max prenant pour argument un arbre binaire de recherche non-vide a et qui retourne le couple (a z)
Sommaire
Les arbres binaires de recherche (ABR) constituent une structure permettant de algorithmes d'accès d'insertion ou de suppression de données.
Cours 4 : Les arbres binaires - LRI
Un arbre binaire de recherche (ABR) est un arbre binaire dans lequel chaque nœud possède une clé telle que • chaque nœud du sous-arbre gauche possède une clé inférieure ou égale à celle du nœud considéré • chaque nœud du sous-arbre droit possède une clé supérieure ou égale à celle-ci
Les arbres binaires de recherche équilibrés
Un arbre binaire de recherche est une structure de donn ee qui permet de repr esen-ter un ensemble de valeurs si l’on dispose d’une relation d’ordre sur ces valeurs Les op erations caract eristiques sont l’insertion la suppression et la recherche d’une valeur Ces op erations sont peu cou^teuses si l’arbre n’est pas trop d es
ARBRES BINAIRES DE RECHERCHE - Université de Montréal
A l’aide d’un arbre de recherche on peut impl` ementer une table de symboles d’une´ maniere tr` es ef?cace ` Operations :´ recherche d’une valeur particuliere` insertion ou suppression d’une valeur recherche de min ou max et des autres Pour la discussion des arbres binaires de recherche on va considerer les pointeurs´
13 Table de symboles et arbres binaires de recherche
? tableau tri´e : recherche binaire — temps de (log n) au pire mais insertion/suppression en ( n) au pire cas 13 2 Arbre binaire de recherche (ABR) (fr) 9 6 12 3 8 11 15 1 4 7 19 chaque nœud interne poss`ede une cl ´e : les cl es sont´ comparables De?nition 13 1 ´ Dans un arbre binaire de recherche
Algo 2 séance 6 Arbres binaires de recherche (ABR (suite
Arbres binaires de recherche (ABR (suite) : suppression et arbres equilibr es Franck Hetroy et Denis Trystram mars 2017 1/37 ECOLE NATIONALE SUPERIEURE 1 / 37 D’INFORMATIQUE ET DE MATHEMATIQUES APPLIQUEES
Searches related to arbre binaire de recherche suppression PDF
Arbre binaire de recherche Un arbre binaire de recherche est un arbre binaire dans lequel chaque sommet est etiquet e par un couple (k;D) avec la propri et e suivante: I tous les sommets du sous-arbre gauche ont une cl e inf erieure a k droit ont une cl e sup erieure a k Exemple: 7 3 1 4 5 9 8 (Seules les cl es sont repr esent ees dans les
Comment définir un arbre binaire?
Un arbre binaire est : – soit l’arbre vide?; – soit un nœud A(g,r,d), où g désigne le sous-arbre gauche, d le sous-arbre droit, et r ? E les données satellites stockées dans le nœud. Dé?nition 2 (Arbre binaire de recherche).
Quand un arbre binaire est dit tasse ?
Un arbre binaire est dit tasse si Itous les niveaux sauf peut-^etre le dernier sont complets.
Comment reequilibrer un arbre ?
Iinserer, rechercher, supprimer, maximum, minimum s’e ectuent en temps O(log n). Remarque: reequilibrer un arbre Iapres une insertion, en fait une seule rotation, ou double rotation sut. Iapres une suppression, il peut y avoir jusqu’a h rotations ou double rotations.
Comment supprimer la racine d'un sous-arbre ?
IOn supprime la racine du sous-arbre correspondant: static ArbresupprimerRacine(Arbre a) { //Castrivial&Facile if (a.gauche==null) return a.droite; if (a.droite==null) return a.gauche; //Casmoinsfacile Arbre g= maximum(a.gauche); return new Arbre(supprimer(g.k,a.gauche),g.k,g.D,a.droite);} 20 Complexite des algorithmes
Table de symboles
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSiRecherche : op´eration fondamentale
donn´ees :´el´ementsavec cl ´es
Type abstrait d"unetable de symboles(symbol table) ou dictionnaireObjets : ensembles d"objets avec cl
´es
typiquement : cl ´es comparables (abstraction : nombres naturels) Op´erations :
insert(x;D): insertion de l"´el´ementxdansD search(k;D): recherche d"un´el´ement`a cl´ek(peutˆetreinfr ucteuse) Op´erations parfois support´ees :
delete(k;D): supprimer´el´ement avec cl´ek select(i;D): s´election de l"i-`eme´el´ement (selon l"ordre des cl´es)Structures de donn
´eesABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSiistructures simples : tableau tri´e ou liste chaˆın´ee
arbre binaire de recherche tableau de hachage (plus tard)Structures simples
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSiiiliste cha ˆın´ee ou tableau non-tri´e : recherche s´equentielle temps de(n)au pire (mˆeme en moyenne) tableau tri´e : recherche binaire
temps de(logn)au pire tableau tri´e : insertion/suppression en(n)au pire cas
Arbre binaire de recherche
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSivDans un arbre binaire de recherche, chaque noeud a une cl
´e.
Acc `es aux noeuds : gauche(x)etdroit(x)pour les enfants dex(nulls"il n"y en a pas) parent(x)pour le parent dex(nullpour la racine) cle(x)pour la cl´e de noeudx(en g´en´eral, un entier dans nos discussions) D ´ef.Un arbre binaire est un arbre de recherche ssi les noeuds sont´enumer´es lors d"un parcours infixe en ordre croissant de cl´es.
Thm.Soitxun noeud dans un arbre binaire de recherche. Siyest un noeud dans le sous-arbre gauche dex, alorscle(y)cle(x). Siyest un noeud dans le sous-arbre droit dex, alorscle(y)cle(x).Arbre binaire de recherche - exemple
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSv961238111571419Arbre binaire de recherche (cont)
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSvi`
A l"aide d"un arbre de recherche, on peut impl´ementer une table de symboles d"une mani `ere tr`es efficace. Op ´erations :recherched"une valeur particuli`ere,insertionousuppressiond"une valeur, recherche deminoumax, et des autres. Pour la discussion des arbres binaires de recherche, on va consid´erer les pointeurs
nullpour des enfants manquants comme des pointeurs vers desfeuilles ou noeuds externes Donc toutes les feuilles sontnullet tous les noeuds avec une valeurcle()sont des noeuds internes.Min et max
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSviiAlgoMIN() // trouve la valeur minimale dans l"arbre1x racine;y null
2tandis quex6=nullfaire
3y x;x gauche(x)
4 r etourneryAlgoMAX() // trouve la valeur maximale dans l"arbre1x racine;y null
2tandis quex6=nullfaire
3y x;x droit(x)
4 r etourneryRecherche
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSviiiAlgoSEARCH(x,v) // trouve la cl´evdans le sous-arbre dex
F1six=nullouv=cle(x)alorsretournerx
F2siv F3alorsretourner SEARCH(gauche(x);v)
F4sinonretourner SEARCH(droit(x);v)Maintenant, SEARCH(racine;v)retourne - soit un noeud dont la cl ´e est´egale`av,
- soitnull. Notez que c"est une recursion terminale)transformation en forme it´erative Recherche (cont)
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSixSolution it ´erative (plus rapide) :AlgoSEARCH(x,v) // trouve la cl´evdans le sous-arbre dex F1tandis quex6=nulletv6=cle(x)faire
F2siv F3alorsx gauche(x)
F4sinonx droit(x)
F5 r etournerx Recherche - efficacit
´eABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxDans un arbre binaire de recherche de hauteurh: MIN()prendO(h)
MAX()prendO(h)
SEARCH(racine;v)prendO(h)
Insertion
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxiOn veut ins ´erer une cl´ev
Id ´ee : comme en SEARCH, on trouve la place pourv(enfant gauche ou droit manquant)96123811157141914insertion de "14» Insertion (cont.)
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxiiinsertion - pas de cl ´es dupliqu´eesAlgoINSERT(v) // ins`ere la cl´evdans l"arbre I1x racine
I2six=nullalorsinitialiser avec une racine de cl´evet retourner I3tandis quevraifaire// (conditions d"arrˆete test´ees dans le corps) I4siv=cle(x)alorsretourner // (pas de valeurs dupliqu´ees) I5siv I6alors sigauche(x) =null
I7alorsattacher nouvel enfant gauche dexavec cl´evet retourner I8sinonx gauche(x)
I9sinon sidroit(x) =null
I10alorsattacher nouvel enfant droit dexavec cl´evet retourner I11sinonx droit(x)
Suppression
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxiiiSuppression d"un noeudx 1. triviale si xest unefe uille: gauche(parent(x)) nullsixest l"enfant gauche de son parent, oudroit(parent(x)) nullsixest l"enfant droit 2. facile si xa seulementun enfant : gauche(parent(x)) droit(x)sixa un enfant droit et il est l"enfant gauche (4 cas en total d ´ependant de la position de
xet celle de son enfant) 3. un peu plus compliqu ´e sixadeux enfants
Suppression - deux enfants
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxiv9612381115714191314 (1) pour supprimer ce noeud x, on cherche un autre qui peut le remplacer (2) pour le remplacement, on peut utiliser le successeur de x c"est le min dans le sous-arbre droitLemmeLe noeud avec la valeur minimale dans le sous-arbre droit dexn"a pas
d"enfant gauche. Insertion et suppression - efficacit
´eABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxvDans un arbre binaire de recherche de hauteurh: INSERT(v)prendO(h)
suppression d"un noeud prendO(h) Hauteur de l"arbre
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxviToutes les op ´erations prendentO(h)dans un arbre de hauteurh. Arbre binaire complet :2h+11noeuds dans un arbre de hauteurh, donc hauteur h=dlg(n+ 1)e 1pournnoeuds est possible. Insertion successive de1;2;3;4;:::;ndonne un arbre avech=n1. Est-ce qu"il est possible d"assurer queh2O(logn)toujours? R ´eponse 1 [randomisation] : la hauteur est deO(logn)en moyenne(permutations al ´eatoires def1;2;:::;ng)
R ´eponse 2 [optimisation] : la hauteur est deO(logn)en pire caspour beaucoup de genres d"arbres de recherche ´equilibr´es : arbre AVL, arbre rouge-noir, arbre 2-3-4 (ex
´ecution des op´erations est plus sophistiqu´ee - mais toujoursO(logn)) R ´eponse 3 [amortisation] : ex´ecution des op´erations estO(logn)en moyenne (co ˆut amortis´e dans s´eries d"op´erations) pour des arbressplay Performance moyenne
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxviiThm.Hauteur moyenne d"un arbre de recherche construit en ins´erant les valeurs
1;2;:::;nselon une permutation al´eatoire estlgnen moyenne o`u2:99.
(preuve trop compliqu ´ee pour les buts de ce cours)
On peut analyser le cas moyen en regardant la
profondeur moyenne d"un noeud dans un tel arbre de recherche al ´eatoire : le coˆut de chaque op´eration d´epend de la profondeur du noeud acc ´ed´e dans l"arbre.
D ´ef.SoitD(n)la somme des profondeurs des noeuds dans un arbre de recherche al ´eatoire surnnoeuds.
On va d
´emontrer queD(n)n
2O(logn).
(Donc le temps moyen d"une recherche fructueuse est enO(logn).) Performance moyenne (cont.)
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxviiiLemme.On aD(0) =D(1) = 0, et D(n) =n1 +1n
n1X i=0 D(i) +D(n1i)
=n1 +2n n1X i=0D(i): Preuve.(Esquiss´e)i+1est la racine, somme des profondeurs = (n-1)+somme des profondeurs dans le sous-arbre gauche +somme des profondeurs dans le sous-arbre droit. D"ici, comme l"analyse de la performance du tri rapide... (en fait, chaque ABR correspond `a une ex´ecution de tri rapide : pivot du sous- tableau comme la racine du sous-arbre) Arbres
´equilibr´esABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxixArbres ´equilibr´es: on maintient une condition qui assure que les sous-arbres ne sont trop diff ´erents`a aucun noeud.
Si l"on veut maintenir une condition d"
´equilibre, il faudra travailler un peu plus`a
chaque (ou quelques) op ´erations...mais on veut toujours maintenirO(logn)par op ´eration
Balancer les sous-arbres
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxM
´ethode : rotations (gauche ou droite) - pr´eservent la propri´et´e des arbres de recherche et prennent seulementO(1)yx ABC xy BCA Rotation droite à yRotation gauche à x
quotesdbs_dbs13.pdfusesText_19
F3alorsretourner SEARCH(gauche(x);v)
F4sinonretourner SEARCH(droit(x);v)Maintenant, SEARCH(racine;v)retourne - soit un noeud dont la cl´e est´egale`av,
- soitnull. Notez que c"est une recursion terminale)transformation en forme it´erativeRecherche (cont)
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSixSolution it ´erative (plus rapide) :AlgoSEARCH(x,v) // trouve la cl´evdans le sous-arbre dexF1tandis quex6=nulletv6=cle(x)faire
F2siv F3alorsx gauche(x)
F4sinonx droit(x)
F5 r etournerx Recherche - efficacit
´eABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxDans un arbre binaire de recherche de hauteurh: MIN()prendO(h)
MAX()prendO(h)
SEARCH(racine;v)prendO(h)
Insertion
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxiOn veut ins ´erer une cl´ev
Id ´ee : comme en SEARCH, on trouve la place pourv(enfant gauche ou droit manquant)96123811157141914insertion de "14» Insertion (cont.)
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxiiinsertion - pas de cl ´es dupliqu´eesAlgoINSERT(v) // ins`ere la cl´evdans l"arbre I1x racine
I2six=nullalorsinitialiser avec une racine de cl´evet retourner I3tandis quevraifaire// (conditions d"arrˆete test´ees dans le corps) I4siv=cle(x)alorsretourner // (pas de valeurs dupliqu´ees) I5siv I6alors sigauche(x) =null
I7alorsattacher nouvel enfant gauche dexavec cl´evet retourner I8sinonx gauche(x)
I9sinon sidroit(x) =null
I10alorsattacher nouvel enfant droit dexavec cl´evet retourner I11sinonx droit(x)
Suppression
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxiiiSuppression d"un noeudx 1. triviale si xest unefe uille: gauche(parent(x)) nullsixest l"enfant gauche de son parent, oudroit(parent(x)) nullsixest l"enfant droit 2. facile si xa seulementun enfant : gauche(parent(x)) droit(x)sixa un enfant droit et il est l"enfant gauche (4 cas en total d ´ependant de la position de
xet celle de son enfant) 3. un peu plus compliqu ´e sixadeux enfants
Suppression - deux enfants
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxiv9612381115714191314 (1) pour supprimer ce noeud x, on cherche un autre qui peut le remplacer (2) pour le remplacement, on peut utiliser le successeur de x c"est le min dans le sous-arbre droitLemmeLe noeud avec la valeur minimale dans le sous-arbre droit dexn"a pas
d"enfant gauche. Insertion et suppression - efficacit
´eABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxvDans un arbre binaire de recherche de hauteurh: INSERT(v)prendO(h)
suppression d"un noeud prendO(h) Hauteur de l"arbre
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxviToutes les op ´erations prendentO(h)dans un arbre de hauteurh. Arbre binaire complet :2h+11noeuds dans un arbre de hauteurh, donc hauteur h=dlg(n+ 1)e 1pournnoeuds est possible. Insertion successive de1;2;3;4;:::;ndonne un arbre avech=n1. Est-ce qu"il est possible d"assurer queh2O(logn)toujours? R ´eponse 1 [randomisation] : la hauteur est deO(logn)en moyenne(permutations al ´eatoires def1;2;:::;ng)
R ´eponse 2 [optimisation] : la hauteur est deO(logn)en pire caspour beaucoup de genres d"arbres de recherche ´equilibr´es : arbre AVL, arbre rouge-noir, arbre 2-3-4 (ex
´ecution des op´erations est plus sophistiqu´ee - mais toujoursO(logn)) R ´eponse 3 [amortisation] : ex´ecution des op´erations estO(logn)en moyenne (co ˆut amortis´e dans s´eries d"op´erations) pour des arbressplay Performance moyenne
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxviiThm.Hauteur moyenne d"un arbre de recherche construit en ins´erant les valeurs
1;2;:::;nselon une permutation al´eatoire estlgnen moyenne o`u2:99.
(preuve trop compliqu ´ee pour les buts de ce cours)
On peut analyser le cas moyen en regardant la
profondeur moyenne d"un noeud dans un tel arbre de recherche al ´eatoire : le coˆut de chaque op´eration d´epend de la profondeur du noeud acc ´ed´e dans l"arbre.
D ´ef.SoitD(n)la somme des profondeurs des noeuds dans un arbre de recherche al ´eatoire surnnoeuds.
On va d
´emontrer queD(n)n
2O(logn).
(Donc le temps moyen d"une recherche fructueuse est enO(logn).) Performance moyenne (cont.)
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxviiiLemme.On aD(0) =D(1) = 0, et D(n) =n1 +1n
n1X i=0 D(i) +D(n1i)
=n1 +2n n1X i=0D(i): Preuve.(Esquiss´e)i+1est la racine, somme des profondeurs = (n-1)+somme des profondeurs dans le sous-arbre gauche +somme des profondeurs dans le sous-arbre droit. D"ici, comme l"analyse de la performance du tri rapide... (en fait, chaque ABR correspond `a une ex´ecution de tri rapide : pivot du sous- tableau comme la racine du sous-arbre) Arbres
´equilibr´esABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxixArbres ´equilibr´es: on maintient une condition qui assure que les sous-arbres ne sont trop diff ´erents`a aucun noeud.
Si l"on veut maintenir une condition d"
´equilibre, il faudra travailler un peu plus`a
chaque (ou quelques) op ´erations...mais on veut toujours maintenirO(logn)par op ´eration
Balancer les sous-arbres
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxM
´ethode : rotations (gauche ou droite) - pr´eservent la propri´et´e des arbres de recherche et prennent seulementO(1)yx ABC xy BCA Rotation droite à yRotation gauche à x
quotesdbs_dbs13.pdfusesText_19
F3alorsx gauche(x)
F4sinonx droit(x)
F5 r etournerxRecherche - efficacit
´eABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxDans un arbre binaire de recherche de hauteurh:MIN()prendO(h)
MAX()prendO(h)
SEARCH(racine;v)prendO(h)
Insertion
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxiOn veut ins´erer une cl´ev
Id ´ee : comme en SEARCH, on trouve la place pourv(enfant gauche ou droit manquant)96123811157141914insertion de "14»Insertion (cont.)
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxiiinsertion - pas de cl ´es dupliqu´eesAlgoINSERT(v) // ins`ere la cl´evdans l"arbreI1x racine
I2six=nullalorsinitialiser avec une racine de cl´evet retourner I3tandis quevraifaire// (conditions d"arrˆete test´ees dans le corps) I4siv=cle(x)alorsretourner // (pas de valeurs dupliqu´ees)I5siv I6alors sigauche(x) =null
I7alorsattacher nouvel enfant gauche dexavec cl´evet retourner I8sinonx gauche(x)
I9sinon sidroit(x) =null
I10alorsattacher nouvel enfant droit dexavec cl´evet retourner I11sinonx droit(x)
Suppression
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxiiiSuppression d"un noeudx 1. triviale si xest unefe uille: gauche(parent(x)) nullsixest l"enfant gauche de son parent, oudroit(parent(x)) nullsixest l"enfant droit 2. facile si xa seulementun enfant : gauche(parent(x)) droit(x)sixa un enfant droit et il est l"enfant gauche (4 cas en total d ´ependant de la position de
xet celle de son enfant) 3. un peu plus compliqu ´e sixadeux enfants
Suppression - deux enfants
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxiv9612381115714191314 (1) pour supprimer ce noeud x, on cherche un autre qui peut le remplacer (2) pour le remplacement, on peut utiliser le successeur de x c"est le min dans le sous-arbre droitLemmeLe noeud avec la valeur minimale dans le sous-arbre droit dexn"a pas
d"enfant gauche. Insertion et suppression - efficacit
´eABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxvDans un arbre binaire de recherche de hauteurh: INSERT(v)prendO(h)
suppression d"un noeud prendO(h) Hauteur de l"arbre
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxviToutes les op ´erations prendentO(h)dans un arbre de hauteurh. Arbre binaire complet :2h+11noeuds dans un arbre de hauteurh, donc hauteur h=dlg(n+ 1)e 1pournnoeuds est possible. Insertion successive de1;2;3;4;:::;ndonne un arbre avech=n1. Est-ce qu"il est possible d"assurer queh2O(logn)toujours? R ´eponse 1 [randomisation] : la hauteur est deO(logn)en moyenne(permutations al ´eatoires def1;2;:::;ng)
R ´eponse 2 [optimisation] : la hauteur est deO(logn)en pire caspour beaucoup de genres d"arbres de recherche ´equilibr´es : arbre AVL, arbre rouge-noir, arbre 2-3-4 (ex
´ecution des op´erations est plus sophistiqu´ee - mais toujoursO(logn)) R ´eponse 3 [amortisation] : ex´ecution des op´erations estO(logn)en moyenne (co ˆut amortis´e dans s´eries d"op´erations) pour des arbressplay Performance moyenne
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxviiThm.Hauteur moyenne d"un arbre de recherche construit en ins´erant les valeurs
1;2;:::;nselon une permutation al´eatoire estlgnen moyenne o`u2:99.
(preuve trop compliqu ´ee pour les buts de ce cours)
On peut analyser le cas moyen en regardant la
profondeur moyenne d"un noeud dans un tel arbre de recherche al ´eatoire : le coˆut de chaque op´eration d´epend de la profondeur du noeud acc ´ed´e dans l"arbre.
D ´ef.SoitD(n)la somme des profondeurs des noeuds dans un arbre de recherche al ´eatoire surnnoeuds.
On va d
´emontrer queD(n)n
2O(logn).
(Donc le temps moyen d"une recherche fructueuse est enO(logn).) Performance moyenne (cont.)
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxviiiLemme.On aD(0) =D(1) = 0, et D(n) =n1 +1n
n1X i=0 D(i) +D(n1i)
=n1 +2n n1X i=0D(i): Preuve.(Esquiss´e)i+1est la racine, somme des profondeurs = (n-1)+somme des profondeurs dans le sous-arbre gauche +somme des profondeurs dans le sous-arbre droit. D"ici, comme l"analyse de la performance du tri rapide... (en fait, chaque ABR correspond `a une ex´ecution de tri rapide : pivot du sous- tableau comme la racine du sous-arbre) Arbres
´equilibr´esABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxixArbres ´equilibr´es: on maintient une condition qui assure que les sous-arbres ne sont trop diff ´erents`a aucun noeud.
Si l"on veut maintenir une condition d"
´equilibre, il faudra travailler un peu plus`a
chaque (ou quelques) op ´erations...mais on veut toujours maintenirO(logn)par op ´eration
Balancer les sous-arbres
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxM
´ethode : rotations (gauche ou droite) - pr´eservent la propri´et´e des arbres de recherche et prennent seulementO(1)yx ABC xy BCA Rotation droite à yRotation gauche à x
quotesdbs_dbs13.pdfusesText_19
I6alors sigauche(x) =null
I7alorsattacher nouvel enfant gauche dexavec cl´evet retournerI8sinonx gauche(x)
I9sinon sidroit(x) =null
I10alorsattacher nouvel enfant droit dexavec cl´evet retournerI11sinonx droit(x)
Suppression
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxiiiSuppression d"un noeudx 1. triviale si xest unefe uille: gauche(parent(x)) nullsixest l"enfant gauche de son parent, oudroit(parent(x)) nullsixest l"enfant droit 2. facile si xa seulementun enfant : gauche(parent(x)) droit(x)sixa un enfant droit et il est l"enfant gauche (4 cas en total d´ependant de la position de
xet celle de son enfant) 3. un peu plus compliqu´e sixadeux enfants
Suppression - deux enfants
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxiv9612381115714191314 (1) pour supprimer ce noeud x, on cherche un autre qui peut le remplacer (2) pour le remplacement, on peut utiliser le successeur de xc"est le min dans le sous-arbre droitLemmeLe noeud avec la valeur minimale dans le sous-arbre droit dexn"a pas
d"enfant gauche.Insertion et suppression - efficacit
´eABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxvDans un arbre binaire de recherche de hauteurh:INSERT(v)prendO(h)
suppression d"un noeud prendO(h)Hauteur de l"arbre
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxviToutes les op ´erations prendentO(h)dans un arbre de hauteurh. Arbre binaire complet :2h+11noeuds dans un arbre de hauteurh, donc hauteur h=dlg(n+ 1)e 1pournnoeuds est possible. Insertion successive de1;2;3;4;:::;ndonne un arbre avech=n1. Est-ce qu"il est possible d"assurer queh2O(logn)toujours? R ´eponse 1 [randomisation] : la hauteur est deO(logn)en moyenne(permutations al´eatoires def1;2;:::;ng)
R ´eponse 2 [optimisation] : la hauteur est deO(logn)en pire caspour beaucoup de genres d"arbres de recherche ´equilibr´es : arbre AVL, arbre rouge-noir, arbre2-3-4 (ex
´ecution des op´erations est plus sophistiqu´ee - mais toujoursO(logn)) R ´eponse 3 [amortisation] : ex´ecution des op´erations estO(logn)en moyenne (co ˆut amortis´e dans s´eries d"op´erations) pour des arbressplayPerformance moyenne
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxviiThm.Hauteur moyenne d"un arbre de recherche construit en ins´erant les valeurs
1;2;:::;nselon une permutation al´eatoire estlgnen moyenne o`u2:99.
(preuve trop compliqu´ee pour les buts de ce cours)
On peut analyser le cas moyen en regardant la
profondeur moyenne d"un noeud dans un tel arbre de recherche al ´eatoire : le coˆut de chaque op´eration d´epend de la profondeur du noeud acc´ed´e dans l"arbre.
D ´ef.SoitD(n)la somme des profondeurs des noeuds dans un arbre de recherche al´eatoire surnnoeuds.
On va d
´emontrer queD(n)n
2O(logn).
(Donc le temps moyen d"une recherche fructueuse est enO(logn).)Performance moyenne (cont.)
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxviiiLemme.On aD(0) =D(1) = 0, etD(n) =n1 +1n
n1X i=0D(i) +D(n1i)
=n1 +2n n1X i=0D(i): Preuve.(Esquiss´e)i+1est la racine, somme des profondeurs = (n-1)+somme des profondeurs dans le sous-arbre gauche +somme des profondeurs dans le sous-arbre droit. D"ici, comme l"analyse de la performance du tri rapide... (en fait, chaque ABR correspond `a une ex´ecution de tri rapide : pivot du sous- tableau comme la racine du sous-arbre)Arbres
´equilibr´esABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxixArbres ´equilibr´es: on maintient une condition qui assure que les sous-arbres ne sont trop diff´erents`a aucun noeud.
Si l"on veut maintenir une condition d"
´equilibre, il faudra travailler un peu plus`a
chaque (ou quelques) op ´erations...mais on veut toujours maintenirO(logn)par op´eration
Balancer les sous-arbres
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxM
´ethode : rotations (gauche ou droite) - pr´eservent la propri´et´e des arbres de recherche et prennent seulementO(1)yx ABC xy BCARotation droite à yRotation gauche à x
quotesdbs_dbs13.pdfusesText_19[PDF] exercice corrigé arbre rouge et noir
[PDF] arbre binaire de recherche en c
[PDF] les arbres en c openclassroom
[PDF] arbre binaire de recherche algorithme
[PDF] arbre binaire de recherche algorithme suppression
[PDF] parcours en profondeur arbre
[PDF] arbre binaire complet
[PDF] dénombrement cours
[PDF] arbre de probabilité pile ou face
[PDF] arbre de probabilité seconde
[PDF] arbre probabilité conditionnelle
[PDF] arbre de décision exercices corrigés
[PDF] arbre de décision data mining
[PDF] cours arbre de décision
