[PDF] ARBRES BINAIRES DE RECHERCHE Dans un arbre binaire de

View - Download ARBRES BINAIRES DE RECHERCHE

Previous PDF

Next PDF

ABR?IFT2015 H2007?UDEM?MIKL´OSCSUR¨OSARBRES BINAIRES DE RECHERCHE

Table de symbole

ABR?IFT2015 H2007?UDEM?MIKL´OSCSUR¨OSiRecherche : op

´eration fondamentale

donn

´ees :´

el´ementsaveccl ´esType abstrait d"unetable de symboles(symbol table) ou dictionnaire

Objets : 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ˆetreinfructeuse) 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 H2007?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 H2007?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 H2007?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 droit dex, alorscle(y)≥cle(x).

Arbre binaire de recherche - exemple

ABR?IFT2015 H2007?UDEM?MIKL´OSCSUR¨OSv961238111571419

Arbre binaire de recherche (cont)

ABR?IFT2015 H2007?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 desfeuillesou noeuds externes Donc toutes les feuilles sontnullet tous les noeuds avec une valeurcle()sont des noeuds internes.

Min et max

ABR?IFT2015 H2007?UDEM?MIKL´OSCSUR¨OSviiAlgoMIN() // trouve la valeur minimale dans l"arbre1x←racine;y←null2tandis quex?=nullfaire3y←x;x←gauche(x)4retourneryAlgoMAX() // trouve la valeur maximale dans l"arbre1x←racine;y←null2tandis quex?=nullfaire3y←x;x←droit(x)4retournery

Recherche

ABR?IFT2015 H2007?UDEM?MIKL´OSCSUR¨OSviiiAlgoSEARCH(x,v) // trouve la cl´evdans le sous-arbre dexF1six=nullouv=cle(x)alorsretournerxF2siv - 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 H2007?UDEM?MIKL´OSCSUR¨OSixSolution it

´erative (plus rapide) :AlgoSEARCH(x,v) // trouve la cl´evdans le sous-arbre dexF1tandis quex?=nulletv?=cle(x)faireF2siv

Recherche - efficacit

´eABR?IFT2015 H2007?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 H2007?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 H2007?UDEM?MIKL´OSCSUR¨OSxiiinsertion - pas de cl

´es dupliqu´eesAlgoINSERT(v) // ins`ere la cl´evdans l"arbreI1x←racineI2six=nullalorsinitialiser avec une racine de cl´evet retournerI3tandis quevraifaire// (conditions d"arrˆete test´ees dans le corps)I4siv=cle(x)alorsretourner // (pas de valeurs dupliqu´ees)I5siv

Suppression

ABR?IFT2015 H2007?UDEM?MIKL´OSCSUR¨OSxiiiSuppression d"un noeudx1.triviale sixest unefeuille:gauche(parent(x))←nullsixest l"enfant gauche

de son parent, oudroit(parent(x))←nullsixest l"enfant droit2.facile sixa 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 H2007?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 H2007?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 H2007?UDEM?MIKL´OSCSUR¨OSxviToutes les op ´erations prendentO(h)dans un arbre de hauteurh. Arbre binaire complet :2h+1-1noeuds dans un arbre de hauteurh, donc hauteur h=?lg(n+ 1)? -1pournnoeuds est possible. Insertion successive de1,2,3,4,...,ndonne un arbre avech=n-1. Est-ce qu"il est possible d"assurer queh?O(logn)toujours? R ´eponse 1 [randomisation] : la hauteur est deO(logn)en moyenne(permutations al

´eatoires de{1,2,...,n})

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 H2007?UDEM?MIKL´OSCSUR¨OSxviiThm.Hauteur moyenne d"un arbre de recherche construit en ins´erant les valeurs

1,2,...,nselon une permutation al´eatoire estαlgnen moyenne o`uα≈2.99.

(preuve trop compliqu

´ee pour les buts de ce cours)

On peut analyser le cas moyen en regardant laprofondeur moyenned"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

?O(logn). (Donc le temps moyen d"une recherche fructueuse est enO(logn).)

Performance moyenne (cont.)

ABR?IFT2015 H2007?UDEM?MIKL´OSCSUR¨OSxviiiLemme.On aD(0) =D(1) = 0, et

D(n) =n-1 +1n

n-1? i=0?

D(i) +D(n-1-i)?

=n-1 +2n n-1? 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 H2007?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 H2007?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

ArbressplayABR?IFT2015 H2007?UDEM?MIKL´OSCSUR¨OSxxiOn utilise souvent des variables auxiliares pour maintenir l"

´equilibre de l"arbre

p.e., arbre rouge et noir : au moins un bit (couleur)

Arbresplay: aucune variable

maisO(logn)seulement comme coˆut amorti Arbressplay(cont)ABR?IFT2015 H2007?UDEM?MIKL´OSCSUR¨OSxxiiId ´ee principale : rotations sans tests sp´ecifiques pour l"´equilibre

Quand on acc

`ede`a noeudx, on performe des rotations sur le chemin de la racine axpour monterx`a la racine. D ´eploiement (splaying) du noeudx:´etapes successives jusqu"`a ce queparent(x) deviennenull (et doncxdevient la racine de l"arbre)

Zig et zag

ABR?IFT2015 H2007?UDEM?MIKL´OSCSUR¨OSxxiiiTrois cas majeurs pour une

´etape de d´eploiement :

1.xsans grand-parent (zigouzag)

2.xetparent(x)au mˆeme cot´e (gauche-gauche ou droit-droit :zig-zigouzag-zag)

3.xetparent(x)`a des cˆot´es diff´erents (gauche-droit ou droit-gauche :zig-zagouzag-zig)yx

ABC xy BCA

Cas 1: zig1 rotation simple

Zig et zag (cont)

ABR?IFT2015 H2007?UDEM?MIKL´OSCSUR¨OSxxivCas 2: zig-zig

2 rotations simples

(à z et à y) z D yx ABC x A yz DCB

Zig et zag (cont)

ABR?IFT2015 H2007?UDEM?MIKL´OSCSUR¨OSxxvCas 3: zig-zagRotation doublez D yx BCA z D xy ABC D

´eploiementABR?IFT2015 H2007?UDEM?MIKL´OSCSUR¨OSxxviChoix dexpour d´eploiement :•insert:xest le nouveau noeud•search:xest le noeud o`u on arrive`a la fin de la recherche•delete:xest le parent du noeud supprim´e

attention : c"est le parent ancien du successeur (ou pr

´edecesseur) si on doit sup-

primer un noeud `a deux enfants (logique : ´echange de noeuds, suivi par la suppression du noeud sans enfant) Co

ˆut amortiABR?IFT2015 H2007?UDEM?MIKL´OSCSUR¨OSxxviiTemps moyen dans unes´eried"op´erations

"moyen»ici : temps total divis´e par nombre d"op´erations (aucune probabilit

´e)

Th ´eor`eme.Le temps pour ex´ecuter une s´erie demop´erations (search,insertet delete) en commenc¸ant avec l"arbre vide est deO(mlogn)o`unest le nombre d"op

´erations d"insertdans la s´erie.

→il peut arriver que l"ex´ecution est tr`es rapide au d´ebut et tout d"un coup une op

´eration prend tr`es long...

→tout`a fait acceptable si utilis´e dans un algorithme

Arbres rouges et noirs

ABR?IFT2015 H2007?UDEM?MIKL´OSCSUR¨OSxxviiiId ´ee : une valeur enti`ere non-n´egative, appell´ee lerang, associ´ee`a chaque noeud.

Notation :rang(x).

R `egles :1.Pour chaque noeudxexcept´e la racine, rang(x)Arbres RN (cont) ABR?IFT2015 H2007?UDEM?MIKL´OSCSUR¨OSxxixD"o `u vient la couleur?

Les noeuds peuvent

ˆetre colori´es par rouge ou noir.

- sirang(parent(x)) =rang(x), alorsxest colori´e parrouge - sixest la racine ourang(parent(x)) =rang(x) + 1, alorsxest colori´e parnoir

Thm.Coloriage :

quotesdbs_dbs44.pdfusesText_44

[PDF] sommet arbre binaire

[PDF] arbre binaire java

[PDF] retour ? l'unité proportionnalité

[PDF] le timbre d'un son

[PDF] psychologie criminelle cours pdf

[PDF] passage ? l'acte psychologie

[PDF] cours de criminologie générale pdf

[PDF] livre criminologie pdf

[PDF] tétraèdre régulier propriétés

[PDF] passage ? l'acte

[PDF] tétraèdre propriétés

[PDF] grille d'estimation de la dangerosité d'un passage ? l'acte suicidaire pondération

[PDF] intervenir auprès de la personne suicidaire ? l'aide de bonnes pratiques

[PDF] grille estimation dangerosité suicidaire

[PDF] grille d'évaluation de l'urgence suicidaire