TD: arbres binaires de recherche
NB: selon la mise en oeuvre de l’arbre binaire de recherche, on pourra interdire ou non des cl es de valeur egale Exemple 1: v eri er que l’arbre de la gure 1 est un arbre binaire de recherche: Figure 1: Arbre binaire de recherche Exemple 2: Dessiner un arbre binaire de recherche contenant les valeurs 11, 13, 14, 15, 17, 18,
ARBRES BINAIRES DE RECHERCHE
Def ´ Un arbre binaire est un arbre de recherche ssi les nœuds sont enumer´ es lors´ d’un parcours infixe en ordre croissant de cles ´ Thm Soit x un nœud dans un arbre binaire de recherche Si y est un nœud dans le sous-arbre gauche de x, alors cle(y) ≤cle(x) Si y est un nœud dans le sous-arbre droit de x, alors cle(y) ≥ (x)
ARBRES BINAIRES DE RECHERCHE
Def ´ Un arbre binaire est un arbre de recherche ssi les nœuds sont enumer´ es lors´ d’un parcours infixe en ordre croissant de cles ´ Thm Soit xun nœud dans un arbre binaire de recherche Si yest un nœud dans le sous-arbre gauche de x, alors cle(y) cle(x) Si yest un nœud dans le sous-arbre droit de x, alors cle(y) cle(x)
Arbres binaires de recherche
Le nombre total de noeuds d’un arbre binaire complet de h niveaux est h−1 i=0 2i =2h −1 On en d´eduit que la hauteur ht(A) (le nombre de niveaux) d’un arbre binaire A contenant n noeuds est au moins ´egale a log 2n+1 Preuve Si A est arbre de hauteur h et comportant n noeuds, pour tout entier m, on a : h ≤ m−1 ⇒ n
Arbres binaires de recherche
On a un arbre binaire de recherche défini par les variables N key (clé), N parent, N left et N right (enfants gauche et droit) à tout nœud interne N; null représente un nœud externe On considère la recherche d’une clé s : ESEARCH(N,s) // recherche de s dans le sous-arbre du nœud N E1 if N = null then return null // recherche
Arbres binaires de recherche - Inria
l’arbre pass´e en argument est vide, vous l`everez une ex-ception value max tree : 0a tree →0a 2 Arbres binaires de recherche Un arbre binaire de recherche est un arbre binaire v´erifiant la propri´et´e suivante : Pour tout nœud ⁄(g,x,d), les ´etiquettes apparaissant dans le sous-arbre gauche g sont strictement inf´erieures `a x
ARBRE BINAIRE DE RECHERCHE - WordPresscom
Soit xun nœud interne dans un arbre binaire de recherche Si y6= xest un nœud interne dans le sous-arbre gauche de x, alors y:key x:key Preuve Le parcours infixe visite les nœuds du sous-arbre gauche avant, et les nœuds du sous-arbre droit après la racine
TP 8 : Arbres binaires de recherche
en argument à l'aide d'un arbre binaire de recherche Remarque : on pourra écrire une fonction auxiliaire récursive qui, à partir d'un sous-arbre d'un ABR et d'une position dans le tableau, remplit le tableau, à partir de la position donnée, avec les aleursv contenues dans ce sous-arbre binaire et renvoie le nombre de aleursv du sous-arbre
Algo 2 séance 6 Arbres binaires de recherche (ABR (suite
I D es equilibre d(A) d’un arbre binaire A : hauteur ls gauche - hauteur ls droit I d(A) ∈Z I Arbre equilibr e : A tel que, ∀S sous-arbre de A, d(S) ∈{−1,0,1} I AVL : ABR equilibr e 17/37 ECOLE NATIONALE SUPERIEURE 17 / 37 D’INFORMATIQUE ET DE MATHEMATIQUES APPLIQUEES
[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
[PDF] classification par arbre de décision
[PDF] arbre de décision exemple
[PDF] arbre de décision cart
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSARBRES BINAIRES DE RECHERCHE
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
Arbres AVL
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxiAVL : Adelson-Velsky et Landis (1962) D ´ef.Un arbre binaire est un arbre AVL ssi`a chaque noeud, la hauteur du sous-arbre gauche et la hauteur du sous-arbre droit diff `erent par 1 au plus. (hauteur d"un sous-arbre vide = -1.) On va donc stocker la hauteur de chaque sous-arbre `a sa racine. Remarque.On peut calculer la hauteur de tous les noeuds en parcours post-fixe. Insertion dans arbre AVL
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxiiInsertion dans le sous-arbre gauche d"un enfant gauche : une rotation si n
´ecessaireRotation
droite à y h+1xy B A z h ou h-1 h C monter vers la racine pour trover le noeud le plus profond où l"équilibre est violé: entre ce noeud et le noeud inseré z, z est la feuille la plus distante qui détermine la hauteur h yx A B C h h ou h-1 z>=>>===Changement
dans la condition d"équilibre(cas sym ´etrique si sous-arbre droit d"un enfant droit; autres cas plus compliqu´es) Hauteur d"un arbre AVL
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxiiiSoitN(h)le nombre minimal de noeuds dans un arbre AVL de hauteurh0.
On aN(0) = 1,N(1) = 2.
Lemme.Pour touth >1,
N(h) =N(h1) +N(h2) + 1:
LemmeIl existec >0tel queN(h)ch1pour touth0o`u=
1+p52 . (Notez que2=+ 1.) PreuveLa constantecsera sp´ecifi´ee plus tard. Supposons queN(k)ck1 pour tout0k < h. Alors, N(h) =N(h1) +N(h2) + 1ch1+ch21 =ch1:
Si on choisitc= 2, la borne est correcte pourh= 0;1et donc elle est correcte pour touth. Hauteur d"un arbre AVL (cont)
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxivDonc un arbre AVL surnnoeuds est de hauteur hlogn+ 12 =lg(n+ 1)1lg1:44lgn2O(logn): ArbressplayABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxvOn utilise souvent des variables auxiliares pour maintenir l"
quotesdbs_dbs23.pdfusesText_29
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
Arbres AVL
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxiAVL : Adelson-Velsky et Landis (1962) D ´ef.Un arbre binaire est un arbre AVL ssi`a chaque noeud, la hauteur du sous-arbre gauche et la hauteur du sous-arbre droit diff `erent par 1 au plus. (hauteur d"un sous-arbre vide = -1.) On va donc stocker la hauteur de chaque sous-arbre `a sa racine. Remarque.On peut calculer la hauteur de tous les noeuds en parcours post-fixe. Insertion dans arbre AVL
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxiiInsertion dans le sous-arbre gauche d"un enfant gauche : une rotation si n
´ecessaireRotation
droite à y h+1xy B A z h ou h-1 h C monter vers la racine pour trover le noeud le plus profond où l"équilibre est violé: entre ce noeud et le noeud inseré z, z est la feuille la plus distante qui détermine la hauteur h yx A B C h h ou h-1 z>=>>===Changement
dans la condition d"équilibre(cas sym ´etrique si sous-arbre droit d"un enfant droit; autres cas plus compliqu´es) Hauteur d"un arbre AVL
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxiiiSoitN(h)le nombre minimal de noeuds dans un arbre AVL de hauteurh0.
On aN(0) = 1,N(1) = 2.
Lemme.Pour touth >1,
N(h) =N(h1) +N(h2) + 1:
LemmeIl existec >0tel queN(h)ch1pour touth0o`u=
1+p52 . (Notez que2=+ 1.) PreuveLa constantecsera sp´ecifi´ee plus tard. Supposons queN(k)ck1 pour tout0k < h. Alors, N(h) =N(h1) +N(h2) + 1ch1+ch21 =ch1:
Si on choisitc= 2, la borne est correcte pourh= 0;1et donc elle est correcte pour touth. Hauteur d"un arbre AVL (cont)
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxivDonc un arbre AVL surnnoeuds est de hauteur hlogn+ 12 =lg(n+ 1)1lg1:44lgn2O(logn): ArbressplayABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxvOn utilise souvent des variables auxiliares pour maintenir l"
quotesdbs_dbs23.pdfusesText_29
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
Arbres AVL
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxiAVL : Adelson-Velsky et Landis (1962) D ´ef.Un arbre binaire est un arbre AVL ssi`a chaque noeud, la hauteur du sous-arbre gauche et la hauteur du sous-arbre droit diff `erent par 1 au plus. (hauteur d"un sous-arbre vide = -1.) On va donc stocker la hauteur de chaque sous-arbre `a sa racine. Remarque.On peut calculer la hauteur de tous les noeuds en parcours post-fixe. Insertion dans arbre AVL
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxiiInsertion dans le sous-arbre gauche d"un enfant gauche : une rotation si n
´ecessaireRotation
droite à y h+1xy B A z h ou h-1 h C monter vers la racine pour trover le noeud le plus profond où l"équilibre est violé: entre ce noeud et le noeud inseré z, z est la feuille la plus distante qui détermine la hauteur h yx A B C h h ou h-1 z>=>>===Changement
dans la condition d"équilibre(cas sym ´etrique si sous-arbre droit d"un enfant droit; autres cas plus compliqu´es) 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
Arbres AVL
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxiAVL : Adelson-Velsky et Landis (1962) D ´ef.Un arbre binaire est un arbre AVL ssi`a chaque noeud, la hauteur du sous-arbre gauche et la hauteur du sous-arbre droit diff `erent par 1 au plus. (hauteur d"un sous-arbre vide = -1.) On va donc stocker la hauteur de chaque sous-arbre `a sa racine. Remarque.On peut calculer la hauteur de tous les noeuds en parcours post-fixe.Insertion dans arbre AVL
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxiiInsertion dans le sous-arbre gauche d"un enfant gauche : une rotation si n
´ecessaireRotation
droite à y h+1xy B A z h ou h-1 h C monter vers la racine pour trover le noeud le plus profond où l"équilibre est violé: entre ce noeud et le noeud inseré z, z est la feuille la plus distante qui détermine la hauteur h yx A B C h h ou h-1 z>=>>===Hauteur d"un arbre AVL
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxiiiSoitN(h)le nombre minimal de noeuds dans un arbre AVL de hauteurh0.
On aN(0) = 1,N(1) = 2.
Lemme.Pour touth >1,
N(h) =N(h1) +N(h2) + 1:
LemmeIl existec >0tel queN(h)ch1pour touth0o`u=
1+p52 . (Notez que2=+ 1.) PreuveLa constantecsera sp´ecifi´ee plus tard. Supposons queN(k)ck1 pour tout0k < h. Alors,N(h) =N(h1) +N(h2) + 1ch1+ch21 =ch1:
Si on choisitc= 2, la borne est correcte pourh= 0;1et donc elle est correcte pour touth.Hauteur d"un arbre AVL (cont)
ABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxivDonc un arbre AVL surnnoeuds est de hauteur hlogn+ 12 =lg(n+ 1)1lg1:44lgn2O(logn):ArbressplayABR?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxxvOn utilise souvent des variables auxiliares pour maintenir l"
quotesdbs_dbs23.pdfusesText_29