Ecole normale superieure Departement d'informatique

Publié par

Ecole normale superieure 2010-2011 Departement d'informatique Algorithmique et Programmation TD n? 4 : Arbres Avec Solutions Arbre Binaire de Recherche Randomise Exercice 1. Un treap est un arbre binaire dans lequel chaque noeud a une cle et une priorite, ou la suite des cles est ordonnee par ordre infixe et la priorite d'un noeud est plus petite que celle de ses fils. En d'autre terme un treap est simultanement un arbre binaire de recherche pour les cles et un tas (min) pour les priorites. 1. Montrer que la structure de l'arbre du treap est completement determinee par les cles et les priorites. 2. Montrer qu'un treap est l'arbre binaire de recherche qui resulte des insertions des cles dans l'ordre des priorites croissante. 3. Montrer comment realiser les operations et estimer leur cout en fonction de la profondeur d'un noeud (distance entre la racine et le noeud) et en fonction de n (le nombre total de noeuds) : rechercher, inserer/enlever (inserer (S, 10) par exemple), un element et separer un treap T en deux treaps T< et T> tels que T< contient toutes les cles plus petite que la cle pi et T> toutes les cles superieures et fusionner deux treaps. Un treap randomise est un treap dans lequel les priorites sont des variables aleatoires uniformement distribuee et independantes continues (pour eviter des priorites egales).

  • priorites

  • arbre binaire de recherche

  • treap randomise

  • insertion

  • cles

  • operation splay

  • insertions des cles dans l'ordre des priorites croissante

  • noeud

  • arbre


Publié le : mardi 19 juin 2012
Lecture(s) : 68
Source : di.ens.fr
Nombre de pages : 8
Voir plus Voir moins
´ Ecolenormalesup´erieure D´epartementdinformatique
Algorithmique TD n Avec
ArbreBinairedeRechercheRandomis´e
et Programmation 4 : Arbres Solutions
2010-2011
Exercice 1.Untreapest un arbre binaire dans lequel chaque noeud a unec´leet unet´eioripr,alu`o suitedescl´esestordonne´eparordreinxeetlapriorite´dunnoeudestpluspetitequecelledesesls. Endautretermeuntreapestsimultan´ementunarbrebinairederecherchepourlescle´setuntas(min) pourlespriorite´s.
1.Montrerquelastructuredelarbredutreapestcomple`tementde´termine´eparlescle´setlespriorit´es. 2.Montrerquuntreapestlarbrebinairederecherchequire´sultedesinsertionsdescle´sdanslordre despriorit´escroissante. 3.Montrercommentr´ealiserlesop´erationsetestimerleurcouˆtenfonctiondelaprofondeurdun noeud (distance entre la racine et le noeud) et en fonction den(le nombre total de noeuds) : rechercher,ins´erer/enlever(inse´rer(S,areruntreaple´neme´tetnpe´s)p10exarplem,ue)Ten deux treapsT<etT>tels queT<lce´eualtiqepstelusp´eclesslteouttneitnocπetT>escltesltouse´ supe´rieuresetfusionnerdeuxtreaps.
Unerpaardnomis´etteulnltersepraipdansleeqsunodtseavrotie´sseal´irtoabrisaleme´mtnenuserofi distribue´eetind´ependantescontinues(pour´eviterdespriorite´se´gales).Onvamontrerquela profondeur de tout noeud estO(logn). Soitxkle noeud qui a laktine´dmepe-`ietitluspe.Onecl´ la variable indicatrice k A= [xiporpedercˆanreeteunstxk]. i 4. Exprimer la profondeur dexkemitsetesecirtacdiinesbliaarsvdeofcnitnonece.eranesp´rson Onvamaintenantestimerlaprobabilit´equunnoeudsoitunancˆetrepropredunautre.SoitX(i, k) repre´sentelesous-ensembledesnoeuds{xi, xi+1, . . . , xk}ou{xk, xk+1, . . . , xi}selon quei < kou k < i. 5. Montrer que pour touti6=k,xiderepropreteˆcnanutsexksi et seulement sixia la plus petite priorite´parmitouslesnoeudsdeX(i, k). 6.Calculerlaprobabilite´quunnoeudsoitunanceˆtrepropredunautreetend´eduirelahauteur moyennedunnoeudetdonclecoˆutdesop´erations. 7.Pouvez-vousende´duireunnouvelalgorithmedetrietmontrerenquoiilressemblea`quicksort?
1
n X k prof ondeur(xk) =A . i i=1
2
La profondeur d’un noeud d’un treap est Θ(n) dans le pire cas et donc dans le pire cas, toutes les op´erationsontuncouˆtenΘ(n).
si si si
si et seulement sixila`a etxksnaest-,cired`a-d i`tseralanicaque,dan
Nous allons montrer que pour touti6=k,xitseeeproprednancˆetrxk priorite´parrapport`atousnoeudsdontlacl´eestcompriseentrexi X(i, k). Pour ce faire, nous montrons que le lemme est vrai quandx
Solutions :oeud,lenvuorpsnollasuoNar1pontiesqulaeroCmmcn.eruer´rcentastduagieilsva`al racineestceluiquialapriorit´elapluspetite.CommeilsagitaussidunABR,lesnoeudsutels que cle(u)< cle(veuqsednargsull´epunectontuionueqxeectuahcrbgedtnolsnauosera-s)svsont dans le sous-arbredroit.Ensuite,commelad´enitiondunABRetduntasestre´cursive,lessous-arbresdroit etgauchesontdesABRetdestas,etnousplac¸onsdefa¸conuniquechaquenoeud.
i < k i=k i > k
Untreaprandomise´estuntreapdanslequellespriorit´essontchoisiesal´eatoirement.Nousallonsmontrer que la profondeur est en moyenne enO(logn).
plus petite l’ensemble xkstela`a
faire une insertion classique dans un ABR. Mais comme les tas,onre´ordonnelABRenutilisantdesrotationsquisatisfont maintenantlapropri´et´edetas.
Pourins´ererunnoeudz, on comme par priorite´sneformentpasn´ecessairementun toujourslaproprie´te´dABRenrepectant
Pours´epareruntreapparrapport`aunecl´eπtusli,reriafedrcteonemavudoeenrstoceedsna`taoi laracinedutreapenluimettantunepriorit´etr`esfaible.Puis,lessous-arbresgaucheetdroitforment des treap.
k A= [xieˆrtancnrpdepeoretuesxk] i estunevariableale´atoireindicatrice,cest-`a-direvalant1sixieˆrtdeeseutancnxket 0 sinon. (cf. le rappeldeprobabilit´e`alandececorrige´.)
Pourjoindredeuxtreapstelsquetouteslescle´sdupremiersontinf´erieures`acelledusecond,ilfaut rajouterunnoeudfantoˆmeavecunepriorit´elaplusfaiblepossible`alaracinedesdeuxtreaps`ajoindre ete´liminerensuitelenoeudfantˆomeavecuneop´erationdesuppression.
Poursupprimerunnoeud,onfaitdesrotationspourdescendrelenoeudsurunefeuilleoudefa¸con`ace qu’il est qu’un fils et ensuite, la suppression est simple.
LarecherchedansuntreapestlamˆemequedansunABR.Letempsestproportionnela`larecherchede cenoeud.Lecasdelarecherchesilenoeudnesetrouvepasdansletreapestlecouˆtdelarecherchede sonsuccesseuroupr´ede´cesseurimme´diat.
k Il suffit donc de calculer Pr[A= 1]. Nous allons montrer que i
n X k E[prof ondeur(xkPr[)] = Ai= 1]. i=1
1 ki+1 [i6=k] k Pr[A= 0= 1] = i |ki|+ 11 ik+1
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.