Ecole normale superieure Departement d'informatique

Description

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

Sujets

• Arbre binaire de recherche
• Insertion

Informations

• Publié par: pefav
• Nombre de lectures: 68
• Langue: Français

Extrait

´ Ecolenormalesup´erieure D´epartementd’informatique

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´eparordreinfixeetlapriorite´d’unnoeudestpluspetitequecelledesesfils. End’autretermeuntreapestsimultan´ementunarbrebinairederecherchepourlescle´setuntas(min) pourlespriorite´s.

1.Montrerquelastructuredel’arbredutreapestcomple`tementde´termine´eparlescle´setlespriorit´es. 2.Montrerqu’untreapestl’arbrebinairederecherchequire´sultedesinsertionsdescle´sdansl’ordre despriorit´escroissante. 3.Montrercommentr´ealiserlesop´erationsetestimerleurcouˆtenfonctiondelaprofondeurd’un 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). Soitx k le noeud qui a laktinfie´dmepe-`ietitluspe.Onecl´ la variable indicatrice k A= [x i porpedercˆanreeteunstx k ]. i 4. Exprimer la profondeur dex k emitsetesecirtacdiinesbliaarsvdeofcnitnonece.eranesp´rson Onvamaintenantestimerlaprobabilit´equ’unnoeudsoitunancˆetrepropred’unautre.SoitX(i, k) repre´sentelesous-ensembledesnoeuds{x i , x i+1 , . . . , x k }ou{x k , x k+1 , . . . , x i }selon quei < kou k < i. 5. Montrer que pour touti6=k,x i derepropreteˆcnanutsex k si et seulement six i a la plus petite priorite´parmitouslesnoeudsdeX(i, k). 6.Calculerlaprobabilite´qu’unnoeudsoitunanceˆtrepropred’unautreetend´eduirelahauteur moyenned’unnoeudetdonclecoˆutdesop´erations. 7.Pouvez-vousende´duireunnouvelalgorithmedetrietmontrerenquoiilressemblea`quicksort?

1