Dans un arbre binaire de recherche, chaque nœud a une clé Acc`es aux nœuds : gauche(x) et droit(x) pour les enfants de x (null s'
| Previous PDF | Next PDF |
[PDF] Arbres binaires de recherche - CNU 27 Marseille
Arbres binaires : hauteur, nombre de noeuds et nombre de feuilles Un arbre binaire est complet si toutes ses branches ont la même longueur et tous ses noeuds
[PDF] Arbres binaires de recherche [br] Algorithmique - Unisciel
Introduction Un arbre binaire de recherche est une structure de donnée qui permet de représen- ter un ensemble de valeurs si l'on dispose d'une relation
[PDF] ARBRES BINAIRES DE RECHERCHE
Dans un arbre binaire de recherche, chaque nœud a une clé Acc`es aux nœuds : gauche(x) et droit(x) pour les enfants de x (null s'
[PDF] TP 8 : Arbres binaires de recherche - Cedric-Cnam
TP 8 : Arbres binaires de recherche Semaine du 17 Mars 2008 Exercice 1 Définir une structure struct noeud_s permettant de coder un n÷ud d'un arbre binaire
[PDF] Algorithmique Les arbres
arbre binaire de recherche (ou ordonné) ; parcours infixe (ou symétrique) ; par FAUX, branche droite par VRAI Recherche : par arbres binaires de recherche
[PDF] Parcours dun arbre binaire
Edition française : Du- nod 2002 Plus de 1100 pages sur les algorithmes et les structures de référence Le chapitre 12 concerne les arbres binaires de recherche
[PDF] Arbres binaires de recherche optimaux
On veut construire un arbre binaire de recherche T pour les clefs de K Chaque clef ki sera un n÷ud interne et chaque clef factice di sera une feuille de l'arbre
[PDF] Arbres binaires de recherche - Inria
des tables d'association Pour manipuler des arbres binaires en Caml, nous allons Un arbre binaire de recherche est un arbre binaire vérifiant la propriété
[PDF] Arbres binaires de recherche Définition Recherche Ajout Ajout dune
gauche ceux qui suivent sont placés dans le sous-arbre droit Cet arbre est un arbre binaire de recherche (ABR) La recherche - Arbres binaires de recherche
[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
[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 RECHERCHEF2siv
[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
quotesdbs_dbs8.pdfusesText_14
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_dbs8.pdfusesText_14
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_dbs8.pdfusesText_14
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