AVL Tree Code - Je ne comprends pas

Question

void insert(const Comparable & x, AvlNode * & t) 
{ 
    if(t == NULL) 
      t = new AvlNode(x, NULL, NULL); 
    else if(x < t->element) 
    { 
      insert(x, t->left); 
      if(height(t->left) - height(t->right) == 2) 
        if(x < t->left->element) 
          rotateWithRightChild(t); 
        else 
          doubleWithLeftChild(t); 
    } 
    else if(t->element < x) 
    { 
      insert(x, t->right); 
      if(height(t->right) - height(t->left) == 2) 
        if(x < t->left->element) 
          rotateWithRightChild(t); 
        else 
          doubleWithLeftChild(t); 
    } 
    else 
      ; // Duplicate; do nothing 
    t->height = max(height(t->left), height(t->right)) + 1; 

} 

int height(AvlNode *t) const { return t == NULL ? -1 : t->height; } 

Comment peuvent-ils caler la hauteur de l'arbre?

 1 
    0 
    -1 

hauteur

(-1) - hauteur (null) = 1 ?? Pas d'équilibre?

Answer 1

Ce n'est pas clair à 100% ce que vous demandez. Le code

AvlNode * & t 

déclare que t est une référence à un pointeur non const. Ainsi, la fonction insert peut changer l'objet pointeur de l'appelant. Étant donné que les pointeurs peuvent être le code nul utilise probablement une fonction appelé height comme raccourci pour traiter le cas particulier de pointeurs nuls:

inline int height(AvlNode * tree) { 
    return tree ? tree->height : 0; 
} 

(juste ma supposition de quelle hauteur pourrait ressembler)

Ajouté après avoir édité votre question: Il semble que chaque nœud possède un membre appelé height qui est synchronisé et reflète la longueur maximale du chemin du nœud actuel vers une feuille. Comme un pointeur nul ne pointe pas vers un nœud, le sous-arbre serait vide, ce qui explique le cas particulier de height() qui renvoie -1.