Cette publication est accessible gratuitement
Télécharger
´ 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