Exercice 3 (20pts): Soit T un arbre AVL de n sommets - UQAC
Quelle est la complexité de la recherche de la valeur maximale. Exercice 3 (
10pts). Un d-tas est comme un tas classique où chacun de ses sommets possède
d ...
part of the document
DIM, UQAC mercredi 17 octobre 2007.
8INF805
Devoir 2
À rendre au plus tard le 7 novembre
avant 18h45 (en classe) ou ma boite aux lettres
Exercice 1 (10pts). Insérer, dans cet ordre, 73, 41, 83, 37, 61 et 50 pour former un arbre de type AVL.
Exercice 2 (15pts). Soit le tableau de nombres suivants : 3, 5, 1, 6, 8, 11, 2, 4, 9 et 10.
Construire le min-tas obtenu en insérant dans cet ordre les nombres du tableau ci-dessus. Représentez graphiquement le min-tas obtenu après chaque insertion.
la valeur 1 est supprimée de ce tableau. Représentez graphiquement chacune des itérations correspondant à cette suppression et à la structuration du min-tas.
Quelle est la complexité de la recherche de la valeur maximale.
Exercice 3 (10pts). Un d-tas est comme un tas classique où chacun de ses sommets possède d enfants. Soit un d-tas implanté dans un tableau A où la racine est stockée dans A[1], ses d enfants sont stockés dans A[2],
, A[d+1], et ainsi de suite. Dites comment retrouver le parent et le kème enfant de A[i].
Exercice 4 (10pts): Un arbre binaire étendu est un arbre binaire dans lequel nous remplaçons tout descendant vide par un nud spécial appelé nud étendu, noté par le carré noir foncé dans lexemple de la figure ci-dessous.
Montrer que pour tout arbre A de n nuds, le nombre de nuds étendus est EMBED Equation.3 .
Le cheminement interne d'un arbre binaire est la somme des profondeurs de tous les noeuds de l'arbre. Dans l'exemple précédent le cheminement interne est égal à 8.
Le cheminement externe d'un arbre binaire est la somme des profondeurs des nuds étendus. Dans l'exemple précédent le cheminement externe est égal à 17.
Ces deux quantités sont liées respectivement au coût de la recherche avec succès et sans succès d'un nud dans un arbre binaire. Le cheminement interne divisé par n (le nombre de recherches) est le coût moyen de recherche d'un nud présent dans un arbre binaire ordonné. Le cheminement externe divisé par n est le coût moyen de recherche pour un nud non présent dans un arbre binaire ordonné. Démontrer par récurrence sur le nombre de nuds que si E est le cheminement externe et I le cheminement interne, alors on a :
EMBED Equation.3
Exercice 5 (20pts): Soit T un arbre AVL de n sommets. Chaque sommet contient une valeur, un champ déquilibre, deux pointeurs vers les fils gauche et droite. Quel champs devrait-on y ajouter pour trouver le kème plus petit élément de T en O(log n). Écrire cet algorithme.
Exercice 6 (Bonus de 15pts): Montrer par récurrence que lopération de suppression dans un arbre AVL de hauteur h peut générer jusquà EMBED Equation.3 rotations.
Exercice 7 (15pts): Soit le B-arbre ci-dessous dordre 2.Supprimer lélément C de cet arbre INCLUDEPICTURE "http://cis.stvincent.edu/carlsond/swdesign/btree/btreen.gif" \* MERGEFORMATINET
Exercice 8 (10pts): Colorier larbre ci-dessous de façon à ce quil soit un arbre rouge et noir
Exercice 9 (10pts): Insérer les 10, 2, 9 3, 8, 4, et 7, dans cet ordre, pour former un arbre rouge et noir.
Montrer larbre après chaque insertion.
PAGE
PAGE 1
1
3
4
2
1
3
4
2
est étendu en
