La meilleure façon de calculer la hauteur dans un arbre de recherche binaire ? (équilibrer un arbre AVL)

Question

Je cherche la meilleure façon de calculer un solde de nœuds dans un système de gestion de l'information. Arbre AVL . Je pensais l'avoir fait fonctionner, mais après quelques insertions et mises à jour importantes, je constate qu'il ne fonctionne pas correctement (du tout).

Il s'agit d'une question en deux parties, la première étant comment calculer la hauteur d'un sous-arbre, je connais la définition. "La hauteur d'un nœud est la longueur du plus long chemin descendant vers une feuille à partir de ce nœud." et je le comprends, mais je n'arrive pas à le mettre en œuvre. Et pour m'embrouiller encore plus, cette citation se trouve sur wikipedia sur la hauteur des arbres "Par convention, la valeur -1 correspond à un sous-arbre ne comportant aucun nœud, tandis que zéro correspond à un sous-arbre comportant un nœud."

Et la deuxième partie consiste à obtenir le facteur d'équilibre d'un sous-arbre dans un arbre AVL, je n'ai aucun problème à comprendre le concept, "obtenir la hauteur de votre L y R sous-arbres et soustraire R de L " . Et ceci est défini comme quelque chose comme ceci : BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

La lecture sur wikipedia dit ceci sur les premières lignes décrivant les insertions dans un arbre AVL : "Si le facteur d'équilibre devient -1, 0 ou 1, alors l'arbre est toujours sous forme AVL, et aucune rotation n'est nécessaire."

Il poursuit ensuite en disant ceci "Si le facteur d'équilibre devient 2 ou -2, alors l'arbre enraciné à ce nœud est déséquilibré, et une rotation de l'arbre est nécessaire. Au maximum, une rotation simple ou double sera nécessaire pour équilibrer l'arbre." - ce que je n'ai aucun mal à comprendre.

Mais (oui, il y a toujours un mais).

C'est là que ça devient confus, le texte dit "Si le facteur d'équilibre de R est égal à 1, cela signifie que l'insertion a eu lieu sur le côté droit (externe) de ce nœud et qu'une rotation vers la gauche est nécessaire". . Mais d'après ce que j'ai compris, le texte disait (comme je l'ai cité) que si le facteur d'équilibre se situait dans les limites de l'UE, il n'y avait pas de problème. [-1, 1] alors il n'y avait pas besoin d'équilibrage ?

J'ai l'impression d'être si proche de la compréhension du concept, j'ai mis au point les rotations d'arbres, implémenté un arbre de recherche binaire normal, et je suis sur le point de comprendre les arbres AVL, mais il me semble qu'il me manque cette épiphanie essentielle.

Editar: Je préfère les exemples de code aux formules académiques, car j'ai toujours eu plus de facilité à comprendre quelque chose en code, mais toute aide est la bienvenue.

Editar: J'aimerais pouvoir marquer toutes les réponses comme "acceptées", mais pour moi, la réponse de NIck est la première qui m'a fait "aha".

Answer 1

Partie 1 - hauteur

Comme le dit starblue, la hauteur est juste récursive. En pseudo-code :

height(node) = max(height(node.L), height(node.R)) + 1

La taille peut être définie de deux façons. Il peut s'agir du nombre de nœuds dans le chemin allant de la racine à ce nœud, ou du nombre de liens. Selon le page à laquelle vous avez fait référence La définition la plus courante est celle du nombre de liens. Dans ce cas, le pseudo-code complet serait :

height(node): 
   if node == null:
        return -1
   else:
        return max(height(node.L), height(node.R)) + 1

Si vous vouliez le nombre de nœuds, le code serait le suivant :

height(node): 
   if node == null:
        return 0
   else:
        return max(height(node.L), height(node.R)) + 1

Dans tous les cas, l'algorithme de rééquilibrage devrait fonctionner de la même manière.

Cependant, votre arbre sera beaucoup plus efficace ( O(ln(n)) ) si vous stockez et mettez à jour les informations relatives à la hauteur dans l'arbre, plutôt que de les calculer à chaque fois. ( O(n) )

Partie 2 - équilibrage

Quand il est dit "Si le facteur d'équilibre de R est de 1", il s'agit du facteur d'équilibre de la branche droite, lorsque le facteur d'équilibre au sommet est de 2. Il vous indique comment choisir de faire une simple rotation ou une double rotation. En (python like) Pseudo-code :

if balance factor(top) = 2: // right is imbalanced
     if balance factor(R) = 1: // 
          do a left rotation
     else if balance factor(R) = -1:
          do a double rotation
else: // must be -2, left is imbalanced
     if balance factor(L) = 1: // 
          do a left rotation
     else if balance factor(L) = -1:
          do a double rotation

J'espère que cela a un sens

Answer 2

Vous n'avez pas besoin de calculer la profondeur des arbres à la volée.

Vous pouvez les gérer au fur et à mesure que vous effectuez des opérations.

En outre, il n'est pas nécessaire de tenir compte des profondeurs ; il suffit de tenir compte de la différence entre les profondeurs des arbres gauche et droit.

http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx

Je trouve que c'est plus facile du point de vue de la programmation de garder la trace du facteur d'équilibre (différence entre les sous-arbres gauche et droit), sauf que le tri du facteur d'équilibre après une rotation est un PITA...

Answer 3

• La hauteur est facilement implémentée par récursion, prenez le maximum de la hauteur des sous-arbres plus un.

• Le "facteur d'équilibre de R" fait référence au sous-arbre droit de l'arbre qui est déséquilibré, je suppose.

Answer 4

C'est là que ça devient confus, le texte dit "Si le facteur d'équilibre de R est 1, il signifie que l'insertion a eu lieu sur le côté droit (externe) de ce noeud et qu'une rotation gauche est nécessaire". Mais d'après ce que j'ai compris, le texte dit (comme je l'ai cité) que si le facteur d'équilibre est compris entre [-1] et [-1]. que si le facteur d'équilibrage était compris entre [-1, 1], il n'y avait pas besoin d'équilibrage ?

Ok, c'est l'heure de la révélation.

Considérez ce que fait une rotation. Réfléchissons à une rotation vers la gauche.

 P = parent
 O = ourself (the element we're rotating)
 RC = right child
 LC = left child (of the right child, not of ourself)

 P              10
  \               \
   O               15
    \                \
     RC               20
    /                /
   LC               18

 P              10
   \               \
     RC              20
   /               /
  O              15
   \               \
   LC              18

 basically, what happens is;

 1. our right child moves into our position
 2. we become the left child of our right child
 3. our right child's left child becomes our right

Maintenant, la grande chose que vous devez remarquer ici - cette rotation vers la gauche N'A PAS CHANGÉ LA PROFONDEUR DE L'ARBRE. Nous ne sommes pas plus équilibrés pour l'avoir fait.

Mais - et c'est là que réside la magie de l'AVL - si nous faisions pivoter le bon enfant vers le bon PREMIER, nous aurions ceci...

 P
  \
   O
    \
     LC
      \
       RC

Et maintenant, si on fait tourner O à gauche, on obtient ceci...

 P
   \
     LC
    /  \
   O   RC

Magique ! Nous avons réussi à nous débarrasser d'un niveau de l'arbre - nous avons rendu l'arbre équilibré .

Pour équilibrer l'arbre, il faut se débarrasser de l'excès de profondeur et remplir plus complètement les niveaux supérieurs, ce qui est exactement ce que nous venons de faire.

Toute cette histoire de rotations simples/doubles signifie simplement que votre sous-arbre doit ressembler à ceci ;

 P
  \
   O
    \
     LC
      \
       RC

avant de faire une rotation - et vous devrez peut-être faire une rotation à droite pour atteindre cet état. Mais si vous êtes déjà dans cet état, il vous suffit de faire une rotation à gauche.

Answer 5

Voici une autre façon de trouver la hauteur. Ajoutez un attribut supplémentaire à votre nœud appelé hauteur :

class Node
{
data value; //data is a custom data type
node right;
node left;
int height;
}

Maintenant, nous allons faire une simple traversée de l'arbre en largeur d'abord, et continuer à mettre à jour la valeur de la hauteur pour chaque nœud :

int height (Node root)
{
Queue<Node> q = Queue<Node>();
Node lastnode;
//reset height
root.height = 0;

q.Enqueue(root);
while(q.Count > 0)
{
   lastnode = q.Dequeue();
   if (lastnode.left != null){
      lastnode.left.height = lastnode.height + 1; 
      q.Enqueue(lastnode.left);
   }

   if (lastnode.right != null){
      lastnode.right.height = lastnode.height + 1;
      q.Enqueue(lastnode.right);
   }
}
return lastnode.height; //this will return a 0-based height, so just a root has a height of 0
}

A la vôtre,