J'ai écrit un code AVL-tree mais comment puis-je écrire un code pour trouver si mon arbre est déséquilibré et qu'il trouve le type déséquilibré Gauche de gauche, Droite de gauche, Gauche de droite et droite de droite?comment trouver le type d'arbre AVL déséquilibré?
0
A
Répondre
0
Vous pouvez faire un DFS traversal
normal et à chaque nœud trouver les max height of the left subtree
et max height of the right subtree
.
Ensuite, l'arbre est équilibré si abs(height_left - height_right) <= 1
pour tous les nœuds.
Pour trouver le type d'arbre déséquilibré (par lequel je pense que vous voulez dire le type de rotation nécessaire pour réparer l'arbre), vous pouvez utiliser les pointeurs enfants gauche et droite pour déduire le type de rotation nécessaire.