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é Acc`es aux nœuds :
| Previous PDF | Next PDF |
[PDF] Arbres binaires de recherche [br] Algorithmique - Unisciel
Un arbre binaire de recherche est une structure de donnée qui permet de représen- opérations caractéristiques sont l'insertion, la suppression et la recherche L'algorithme d'insertion recherche donc l'élément dans l'arbre et, quand il
[PDF] Arbres binaires de recherche - CNU 27 Marseille
Pour être efficaces, les algorithmes qui utilisent des arbres binaires font en sorte que binaires de recherche sont l'insertion, la suppression, et la recherche
[PDF] Algorithmique Les arbres
Algorithmes et structures de données La plupart Représentations graphiques d'arbres binaires et vocabulaire 15 4 33 recherche, insertion, suppression
[PDF] ARBRES BINAIRES DE RECHERCHE
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é Acc`es aux nœuds :
[PDF] LIFAP3 – Algorithmique et programmation avancée - CNRS
recherche de la feuille à supprimer et de son père en + Un arbre binaire peut être dégénéré ou équilibré ou aucun Algorithmes de parcours
[PDF] Algo 2 – séance 6 Arbres binaires de recherche (ABR (suite - Moais
Arbres binaires de recherche (ABR (suite) : suppression et arbres équilibrés Quelle est la complexité en pire cas de cet algorithme de suppression d'un
[PDF] Complexité et les ABR - IRISA
Suppression Analyse Programmation avancée Chapitre 1 : Complexité et les ABR (arbres binaires de recherche) Mickaël Algorithme : spécification bien définie d'un schéma de recherche d'un élément sur un disque ; nombre d' accès
[PDF] les arbres binaires de recherche (ABR) - Département de génie
Chapitre 9 : Les arbres binaires de recherche : interface et implantation Département Notes de cours GEI 442 : STRUCTURES DE DONNÉES ET ALGORITHMES removeMin( ) : recherche et suppression du plus petit élément de l 'ABR
[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
[PDF] construire un arbre de décision
[PDF] arbre de décision définition
[PDF] dénombrement cours 1ere s
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
quotesdbs_dbs10.pdfusesText_16
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
quotesdbs_dbs10.pdfusesText_16
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
quotesdbs_dbs10.pdfusesText_16
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