Please enable JavaScript.
Coggle requires JavaScript to display documents.
Arbres binaires de recherche (Implémentations par chaînage (:warning:…
Arbres binaires de recherche
Rappel
Les arbres binaires sont utilisés pour implémenter les dictionnaires
Dictionnaires
Conteneur d'éléments devant supporter les opérations suivantes
Insertion d’un élément
Suppression d’un élément
Trouver un élément (déterminer si un élément est présent)
:timer_clock: Toutes ses opérations s'effectuent en O(log n) lorsque l’arbre de n éléments est équilibré
Implémentations par chaînage
:warning: Puisque chaque noeud possède au maximum deux noeuds fils, on maintient un
pointeur sur chacun d’eux
:check: La taille de l’arbre est dynamique
:red_cross: On doit éviter les fuites de mémoire et les doubles références
:red_cross: La parcours explicite de l’arbre ne se fait que de la racine vers les
feuilles (mais il est possible de remonter vers la racine grâce aux retours
d’appels récursifs)
:check: Facile d’opérer sur des pointeurs
Enlèevement dans un arbre AVL
Cas simples
Le noeud à supprimer est une feuille
Il suffit de le supprimer directement
Le noeud à supprimer possède un seul enfant
Il suffit de le remplacer par son seul enfant
Cas compliqués
Le noeud à supprimer possède deux enfants
Il faut d’abord échanger ce noeud avec son
successeur minimal à droite, ce qui nous mènera nécessairement
à l’un des deux cas simples car ce successeur minimal à droite n’a
pas d’enfant à gauche!
Rappel
Un arbre de tri est dit équilibré lorsq e la valeur absolue de la différence de la hauteur des fils gauche et droit de tout noeud n’excède pas k (Cette différence de hauteur est appelée facteur d’équilibre du noeud)
|hauteur(sous-arbre droit) - hauteur(sous-arbre gauche)| ≤ k
Arbres AVL = HB[1] (arbres Adelson-Velski et Landis): on est toujours assuré d’avoir un arbre dont la hauteur est en Θ(log n), on évite donc le pire cas
Un arbre binaire de recherche (de tri) doît être équilibré pour supporter efficacement les opérations de recherche, d’insertion et de suppression
Noeud critique
Quand il y a un déséquilibre, le noeud le plus bas à partir duquel il y a une différence de 2 ou plus est appelé le noeud critique.
Il peut parfois y avoir plusieurs noeuds débalancés. Dans ce cas, on s’occupe d’abord du plus bas de tous, c’est le noeud critique