[PDF] 13 Table de symboles et arbres binaires de recherche

View - Download 13 Table de symboles et arbres binaires de recherche

Previous PDF

Next PDF

IFT2015Miklos Cs}uros 10 avril 2012

13 Table de symboles et arbres binaires de recherche

13.1 Table de symboles

Type abstraittable de symboles(symbol table) oudictionnaire: ensemble d"objets avec cl´es. Typique-

ment (mais pas toujours!) les cl ´es sont comparables (abstraction : nombres naturels). Op

´eration principale :

?search(k): recherche d"un´el´ement`a cl´ek op´eration fondamentale - peutˆetre fructueuse ou

infructeuse. Op

´erations souvent support´ees :

?insert(x): insertion de l"´el´ementx(cl´e+info) ?delete(k): supprimer´el´ement avec cl´ek ?select(i): s´election de l"i-`eme´el´ement (selon l"ordre des cl´es)

Implantations

´el´ementaires

?liste chaˆın´ee ou tableau non-tri´e : recherche s´equentielle - temps de(n)au pire (mˆeme en moyenne),

mais insertion/suppression en(1)[si non-tri´e] ?tableau tri´e : recherche binaire - temps de(logn)au pire, mais insertion/suppression en(n)au pire cas

13.2 Arbre binaire de recherche (ABR)(fr)961238111571419chaque noeud interne poss

`ede une cl´e : les cl´es sont comparables. D ´efinition 13.1.Dans unarbre binaire de recherche (ABR), les noeuds internes poss `edent des cl´es comparables, en respectant un ordre parmi les enfants gauches et droits : le parcours infixe

´enum`ere les noeuds internes dans l"ordre

croissant de cl

´es.

On sp

´ecifie l"ABR par sa racineroot. Acc`es aux

noeuds : x: leftetx:rightpour les enfants dex (nullsi l"enfant est un noeud externe) x: parentpour le parent dex (null`a la racine) x: keypour la cl´e d"un noeud internex (en g

´en´eral, un entier dans nos discussions)

Normalement, on indique les noeuds externes parnull(donc, p.e.,x:parentn"est pas valide quandxest un noeud externe). Th

´eor`eme 13.1(Ordre d"ABR).Soitxun noeud interne dans un arbre binaire de recherche. Siy6=xest un noeud

interne dans le sous-arbre gauche dex, alorsy:key< x:key. Siy6=xest un noeud interne dans le sous-arbre droit de

x, alorsy:key> x:key. 1

13.3 Op

´erations sur l"ABR

Op ´erations : la structure ABR permet l"implantation efficace derecherched"une valeur particuli`ere (op

´eration principale du TAD dictionnaire),insertionetsuppressiond"´el´ements (op´erations optionnelles

pour dictionnaires dynamiques), et m ˆeme recherche deminoumax(permettant l"implantation de file`a priorit

´e), et beaucoup d"autres.Recherche.SEARCH(root;v)retourne (a) soit un noeud dont la cl´e est´egale`av, (b) soitnulls"il n"y a

pas de noeud avec cl ´ev. Th´eor`eme 13.1 m`ene`aux algorithmes suivants bas´es sur la mˆeme logique.

Solution r

´ecursive Solution it´erativeSEARCH(x,v) //trouve cl´evdans le sous-arbre dex

S1ifx=nullouv=x:keythen returnx

S2ifv < x:key

S3then returnSEARCH(x:left;v)

S4else returnSEARCH(x:right;v)SEARCH(x,v) //trouve cl´evdans le sous-arbre dex

S1whilex6=nulletv6=x:keydo

S2ifv < x:key

S3thenx x:left

S4elsex x:right

S5returnx96123811157141914insertion de "14»Insertion.Pour ins´erer une cl´evil suffit d"attacher son

noeud interne en remplac¸ant un seul noeud externe, identifi ´e a l"´echec de SEARCH(v).INSERT(v) //ins`ere la cl´evdans l"arbre

I1x root;y nouveau noeud;y:key v

I2ifx=nullthenroot y;return

I3loop//boucler : conditions d"arrˆet test´ees dans le corps I4ifv=x:keythen erreur//on ne permet pas de cl´es dupliqu´ees

I5ifv < x:key

I6then ifx:left=null

I7thenx:left y;y:parent x;return//attacherycomme enfant gauche dex

I8elsex x:left

I9else ifx:right=null

I10thenx:right y;y:parent x;return//attacherycomme enfant droit dex

I11elsex x:right2

Suppressiondu noeud x.

0. triviale si xn"apas d"enfantsinternes : fairex:parent:left nullsixest l"enfant gauche de son parent, oux:parent:right nullsixest l"enfant droit 1. facile si xa seulement1 enfant: fairex:parent:left x:right;x:right:parent x:parentsixa un

enfant droit etxest l"enfant gauche de son parent (il y a 4 cas en total d´ependant de la position dexet

celle de son enfant) 2. un peu plus compliqu ´e sixa2 enfants: on trouve d"abord remplacement (successeur ou pr´edecesseur dans le parcours infixe)9612381115714191314 (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 droitLemme 13.2.Le noeud avec la cl´e minimale dans le sous-arbre droit dex n"a pas d"enfant gauche. )il est facile d"enlever le succes- seur (d"un noeud `a deux enfants)...DELETE(z) //supprime le noeudz D1ifz:left=nullouz:right=nullalorsy z//cas 1. ou 2.

D2elsey MINz:right//cas 3.

//c"est le noeudyqu"on enl`eve physiquement : un de ses enfants est externe D3ify:left6=nullthenx y:leftelsex y:right//le noeudxremplacey`a son parent

D4ifx6=nullthenx:parent y:parent

D5ify:parent=nullthenroot x//y´etait la racine

D6else//on remplace

D7ify=y:parent:lefttheny:parent:left x//yest enfant gauche

D8elsey:parent:right x//yest enfant droit

D9ify6=zthenremplacer noeudzparydans l"arbre //copier contenu :z:key y:keyExercice 13.1.I´Ecrire l"algorithmeSUCCESSEUR(x)qui trouve le successeur du noeudxdans le parcours infixe.IMontrer

que le temps de calcul deSUCCESSEUR(x)est(h)dans le pire cas o`uhest la hauteur de l"arbre.IMontrer que le temps de

calcul est(1)en moyenne (quandxest un noeud al´eatoire dans l"arbre).Indice: consid´erer un parcours infixe en utilisant l"it´eration

x SUCCESSEUR(x). 3 S

´electionTh´eor`eme 13.1 sugg`ere imm´ediatement la d´emarche pour trouver le minimum ou le maxi-

mum.MIN(r) //noeud`a cl´e minimale dans le sous-arbre der

1x r;y null

2whilex6=nulldoy x;x x:gauche

3returnyMAX(r) //noeud`a cl´e maximale dans le sous-arbre der

1x r;y null

2whilex6=nulldoy x;x x:droit

3returnyExercice 13.2.Pour implanter l"op´erationselect(i)(qui retourne lei-`eme´el´ement selon l"ordre de cl´es), on a besoin de stocker

la taille de chaque sous-arbre

`a sa racine par la variablex:size:x:sizeest le nombre d"internes dans le sous-arbre enracin´e au noeud

internex.IDonner une d´efinition r´ecursive pourx:size.IDonner un algorithme r´ecursif pour initialiserx:sizepartout dans un

ABR donn

´e.IMontrer comment mettre`a jourx:sizelors d"une insertion ou suppression.

13.4 Temps de calcul des op

´erations

Les op

´erations prennentO(h)au pire dans les implantations dex13.3.Hauteurs extr ˆemes.Par Th´eor`eme 7.2 (v. aussi Exercice 7.2), la hauteurhd"un arbre binaire avecn noeuds internes est born ´ee commelg(n+ 1)hnavec´egalit´es dans le cas d"un arbre binaire complet

a la borne inf´erieure, et l"arbre r´esultant de l"ins´ertion succ´essive d"´el´ements1;2;3;4;:::;n.Arbre"moyen».

D

´efinition 13.2.UnABR al´eatoirese construit en ins´erant les valeurs1;2;:::;nselon une permutation al´eatoire,

choisie

`a l"uniforme.REMARQUE. Notez que cette notion est tout`a fait diff´erente de celle d"une strcuture choisie`a l"uniforme : les 6 permutations des

cl ´esf1;2;3;gm`enent`a juste 5 arbres possibles.Th

´eor`eme 13.3(Bruce Reed & Michael Drmota).La hauteur d"un ABR al´eatoire surncl´es estEh=lgn

lglgn+O(1)en esp´erance o`u2:99et=32lg(=2)1:35. La variance de la hauteur al´eatoire estO(1). Le th

´eor`eme 13.3 applique au pire cas des op´erations (noeud externe le plus distant) d"un ABR al´eatoire.

Il montre que les op

´erations prennentO(logn)en moyenne. La preuve du th`eor`eme est trop compliqu´ee

pour les buts de ce cours.Profondeur moyenne.Le temps moyen de la recherche (ou d"insertion) correspond au niveau moyen

de noeuds internes parce que c"est o `u la recherche se termine. On va d´emontrer que la profondeur moyenne

estO(logn). La preuve exploˆıte la correspondance`a une ex´ecution du tri rapide : le pivot du sous-tableau

correspond `a la racine du sous-arbre. D

´efinition 13.3.Soitxun noeud interne d"un ABR, et soitTxle sous-arbre enracin´e`ax. Pour tout noeud interne

y2Tx, la distanced(x;y)est d´efinie comme la longueur du chemin dex`ay. On d´efinitd(x) =P y2Txd(x;y) comme la somme des profondeurs des noeuds internes dans le sous-arbreTxenracin´e`ax.

Avec cette d

´efinition,d(root;y)est la profondeur (ou niveau) du noeudyetd(racine)n est la moyenne des profondeurs dans l"arbre. Th

´eor`eme 13.4.SoitD(n) =Ed(root)l"esp´erance de la somme des profondeurs dans un arbre al´eatoire avecncl´es

comme en Th

´eor`eme 13.3. Alors,D(n)=n=O(logn)

D ´emonstration.Preuve comme pour Th´eor`eme 12.1 (temps de calcul moyen du tri rapide). 4

13.5 Rotations

(en)

Vu que la performance d"un ABR est d

´etermin´ee par sa hauteur, des implantations efficaces visent`a maintenir un arbre

´equilibr´e.yx

ABC xy BCA Rotation droite à yRotation gauche à xLa technique principale dans l"

´etablissement de l"´equilibre est la

rotation. Les rotations (gauche ou droite) - pr

´eservent la propri´et´e

des arbres de recherche et prennent seulementO(1).ROTR(y)//rotation droite`ay

R1x y:left;B x:right;p y:parent

R2x:right y;y:parent x

R3y:left B;ifB6=nullthenB:parent y

R4x:parent p

R5ifp6=nullthen

R6ify=p:leftthenp:left x

R7elsep:right xROTL(x)//rotation gauche`ax

L1y x:right;B y:left;p x:parent

L2y:left x;x:parent y

L3x:right B;ifB6=nullthenB:parent x

L4y:parent p

L5ifp6=nullthen

L6ifx=p:leftthenp:left y

L7elsep:right yIl existe de nombreuses implantations efficaces qui utilisent des rotations : (Randomisation)En maintenant une variablex:size`a chaque noeeud internex(v. Exercice 13.2) qui stocke le nombre de noeuds internes dans le sous-arbre dex, on peut simuler l"ABR al´eatoire de D

´ef. 13.2, ind´ependamment de l"ordre des insertions. L"id´ee est de d´ecider lors de la descente dans

INSERT(v)au hasard quevdevienne la racine du sous-arbre1Pour un tel arbre, les op´erations prennent

O(logn)en moyenne(individuellement). (Mais un temps de calcul de(n)arrive avec une probabilit´e positive.) (Amortisation)Dans un arbresplay, on remonte un noeud jusqu"`a la racine par des rotations selon une logique analogue `a celle de compression de chemin par r´eduction`a moiti´e d"Union-find (path halving,

v.x6.5). Dans un tel arbre, une s´equence quelconque demop´erations s"ex´ecute enO(mlogn)au pire

cas

2, donc les op´erations prennentO(logn)detemps amorti.

(Optimisation)La hauteur estO(logn)au pire cas(individuellement) pour beaucoup de genres d"arbres de recherche ´equilibr´es : arbre AVL, arbre rouge-noir, arbre 2-3-4. Il faut toujours stocker au moins une variable additionnelle `a chaque noeud interne pour guider la d´emarche de rotations.1

Plus pr´ecisement, au noeud internex, on performe une"insertion`a la racine»avec probabilit´e1=(x:size+ 1): apr`es avoir

inser

´evdans le sous-arbre dexselon la d´emarche usuelle, on remonte`ax, en performant des rotations jusqu"`ax.

2ici,nest la taille maximal de l"arbre pendant la s´equence

5quotesdbs_dbs13.pdfusesText_19

[PDF] exercices sur les arbres binaires en c

[PDF] exercice corrigé arbre rouge et noir

[PDF] arbre binaire de recherche en c

[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