TP 8 : Arbres binaires de recherche
Ajouter des typedef pour définir les nouveaux types noeud_t et arbre_t (ces types devraient permettre de représenter une feuille c'est à dire un arbre vide).
Parcours dun arbre binaire
ordre infixe : ch
ARBRES BINAIRES DE RECHERCHE
Dans un arbre binaire de recherche chaque nœud a une clé. soit null. Notez que c'est une recursion terminale ? transformation en forme itérative ...
Un analogue du monoïde plaxique pour les arbres binaires de
binaires de recherche tournoi) T (? ) associé à une permutation ? ? Sn. C'est un arbre binaire (incomplet) à n sommets numérotés de 1 à n.
Un analogue du monoïde plaxique pour les arbres binaires de
binaires de recherche tournoi) T (? ) associé à une permutation ? ? Sn. C'est un arbre binaire (incomplet) à n sommets numérotés de 1 à n.
ARBRES BINAIRES DE RECHERCHE
Dans un arbre binaire de recherche chaque nœud a une clé. soit null. Notez que c'est une recursion terminale ? transformation en forme itérative ...
Structures de données Avancée
Les arbres binaires de recherche. — Ce type d'arbre il y a une cohérence entre les nœuds
Les arbres binaires de recherche équilibrés
Un nœud est une feuille si ses deux fils sont vides sinon c'est un nœud La propriété d'arbre binaire de recherche permet de trouver
Programmation avancée Projet 2: Arbre binaire de recherche
Nov 7 2014 associées `a chacun des mots dans l'arbre binaire de recherche. L'arbre binaire de ... C'est `a dire
1 ALGORITHMES ET COMPLEXITÉ
RECHERCHE. Définition. Arbre binaire tel qu'en tout nœud la recherche de l'élément de clé c dans l'arbre a. Elt recherche (c CCle; a ABR; e Elt).
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´
Apprendre à programmer les arbres en langage C - Première partie
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
ARBRES BINAIRES DE RECHERCHE - Université de Montréal
Dans un arbre binaire de recherche chaque nœud a une cle ´ Acces aux nœuds :` gauche(x) etdroit(x) pour les enfants de x (nulls’il n’y en a pas) parent(x) pour le parent de x (nullpour la racine) cle(x) pour la cle de nœud´ x (en gen´ eral un entier dans nos discussions)´
Exercice 1 : Arbre binaire de recherche (15 points) - CNRS
Exercice 1 : Arbre binaire de recherche (15 points) Dans cet exercice nous nous intéressons aux arbres binaires de recherche (ABR) Pour rappel dans un ABR tous les éléments dans le fils gauche d’un nœud sont plus petits que ce nœud et tous les éléments à droite sont plus grands (cf Annexe pour les fonctions membres de la classe Arbre)
Arbres binaires de recherche [br] Algorithmique - Unisciel
Un arbre binaire de recherche (abr eg e ABR) est un arbre binaire v eri ant la propri et e suivante : soient x et y deux noeuds de l’arbre : • Si y est un noeud du sous-arbre gauche de x alors cle(y) ? cle(x) • Si y est un noeud du sous-arbre droit de x alors cle(y) ? cle(x) Exemple
Quelle est la valeur qui décide du lieu d'insertion dans un arbre binaire ?
Le premier élément est inséré à la racine de l'arbre, l'élément suivant est inséré à gauche si la valeur de sa clé est inférieure à celle de la racine et à droite si la valeur de sa clé est supérieure à celle de la racine (on aurait pu faire l'inverse).
Comment comparer deux arbres binaires ?
affiche_arbre2_rec ( arbre ); printf (" " ); } Exercice 7 Écrire une fonction compare() qui compare deux arbres binaires (la fonction renvoie une alveur nulle si et seulement si les deux arbres binaires ont la même structure d'arbre et qu'ils portent les mêmes aleursv aux n÷uds se correspondant).
Quels sont les avantages d'une calculatrice en arbre binaire ?
C'est là son gros avantage par rapport aux listes chaînées. Il est souvent bien plus rapide de parcourir l'arbre de la racine jusqu'à une feuille, plutôt qu'une longue liste chaînée parfois entièrement.
Comment les arbres binaires sont-ils semblables aux listes chaînées?
Ils sont semblables aux listes chaînées par le fait que les éléments sont chaînés les uns avec les autres, mais avec la possibilité que plusieurs branches partent d'un nœud, d'où leur nom (on pourrait très bien voir une liste chaînée comme un arbre à une seule branche). Il est courant d'appeler le premier élément d'un arbre la racine.
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[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
