Facteur d'équilibrage des nœuds dans l'arbre AVL

Question

Pour calculer le facteur d'équilibre d'un nœud dans un arbre AVL, nous devons trouver la hauteur de son sous-arbre gauche et la hauteur de son sous-arbre droit. Ensuite, nous soustrayons la hauteur du sous-arbre droit de la hauteur de son sous-arbre gauche:

balancefactor = leftsubtreeheigh - rightsubtreeheight

Ma question est: Comment calculer la hauteur du sous-arbre gauche ou le sous-arbre droit?

Par exemple, dans la figure donnée la hauteur du sous-arbre gauche du noeud de racine 40 est 4 et la hauteur de la sous-arbre droit de 40 est égal à 2 de sorte que la différence des hauteurs est égal à 2.

Comment faire cela en C++? Je ne veux pas utiliser la récursivité parce que c'est très déroutant. L'utilisation d'une pile explicite au lieu de la récursivité est beaucoup plus compréhensible.

---

La figure a été supprimée à partir des serveurs Imgour.

Answer 1

La profondeur d'un nœud est 1 de plus que la profondeur de son enfant le plus profond.

Vous pouvez le faire tout simplement avec la récursivité.

unsigned int depth(node *n) 
{ 
    if (n == NULL) 
     return 0; 
    else 
     return MAX(depth(n->left), depth(n->right)) + 1; 
} 

Answer 2

-1, 0 et +1 sont l'état de trois équilibre d'un arbre AVL.

Le facteur d'équilibre est left height - right height de l'arbre.