7 jours d'essai offerts
Cet ouvrage et des milliers d'autres sont disponibles en abonnement pour 8,99€/mois
´ 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