Le calcul du facteur d'équilibre d'un noeud dans l'arbre AVL

Question

Je veux calculer le facteur d'équilibre d'un nœud dans l'arbre AVL sans utiliser une procédure récursive. Comment puis je faire ça? S'il vous plaît me dire la méthode ou de fournir l'extrait de code C.

Answer 1

Vous pouvez enregistrer le facteur d'équilibre en tant que partie de l'information chaque nœud enregistre. Plus précisément, vous pouvez enregistrer la hauteur des sous-arbres gauche et à droite, et mettre à jour les valeurs à chaque insertion / suppression sur l'insertion / suppression de chemin.

Exemple:

class Node {
  public:
    // stuff...
    int GetBF() { return lHeight - rHeight; }
  private:
    int data;
    Node* right;
    Node* left;
    Node* parent; // optional...
    int rHeight;  // Height of the right subtree
    int lHeight;  // Height of the left subtree
};

Answer 2

Sans récursion il peut être un peu compliqué, mais vous pouvez enregistrer la hauteur du nœud dans chaque nœud. Ensuite, vous pouvez obtenir le facteur équilibré en temps constant (différence entre la hauteur de l'enfant gauche et à droite, si l'enfant est NULL, la hauteur est 0).

Il y aura une mise à jour compliquée ce numéro. Lorsque vous vous devez insérer nœud mettre à jour toutes les hauteurs sur le chemin, mais pas tout le monde. Hauteur toujours égale à max (taille de l'enfant gauche, taille de l'enfant à droite) + 1. Cette insertion est récursive et je ne sais pas si cela est un problème pour vous. Également au cours de l'équilibrage, vous devez mettre à jour des hauteurs et probablement à nouveau avec récursivité.

J'espère que cela vous aide. Sinon s'il vous plaît préciser le problème avec récursion - temps, la mémoire, ... et nous pouvons essayer de trouver une meilleure solution