AVL Tree insertion

Question

Comment calculer le facteur d'équilibre pour un nœud particulier, lorsque j'appelle récursivement une fonction d'insertion pour ajouter un nœud à un arbre AVL. Je n'ai pas commencé sur la logique de rotation. Je veux simplement calculer les facteurs d'équilibre.

Dans ma tentative actuelle, je suis obligé de stocker les hauteurs de & sous-arbres de droite car je ne peux pas trouver le facteur d'équilibre sans eux.

typedef struct _avlTree 
{ 
int num; 
int balFactor; 
int height[2]; // left & right subtree heights 
struct _avlTree *left,*right; 
} *avlTree; 


int avlAdd(avlTree a,avlTree aNew) 
{ 
       ... 
    if(a->left == NULL) // left subtree insertion case 
    { 
    a->left = aNew; 
    return(1); 
    } 
    else 
    { 
    a->height[0] = avlAdd(a->left,aNew); 
    a->balFactor = a->height[0] - a->height[1]; 
    return((a->height[0]>a->height[1]) ? (a->height[0]+1) : (a->height[1]+1)); 
    } 
       ... 
} 

Answer 1

Le facteur d'équilibre est la différence de hauteur entre les sous-arbres droit et gauche d'un noeud. Lors de la création d'un nouveau noeud, initialisez le facteur d'équilibrage à zéro car il est équilibré (il n'a pas de sous-arborescences).

Si vous insérez un nouveau nœud à droite, augmenter le facteur de l'équilibre par 1.

Si vous insérez un nouveau nœud à gauche, diminuer le facteur d'équilibre par 1.

Après rééquilibrage (rotation), si vous augmentez la hauteur du sous-arbre de ce noeud, propagez récursivement l'augmentation de la hauteur au noeud parent.

Answer 2

Voici une approche très simple. S'il y avait une fonction height() récursif, alors facteur d'équilibre peut être calculé simplement comme

node->balFactor = height(node->right) - height(node->left); 

Ce n'est pas la meilleure approche cependant, car la complexité de cette approche est O(h) où h est la hauteur du node dans le AVL arbre. Pour une meilleure approche, une plus grande discussion est nécessaire :)

Il existe de nombreuses ressources sur l'arbre AVL dans le web, quelques élus sont:

1. http://en.wikipedia.org/wiki/AVL_tree
2. C mise en œuvre: http://www.stanford.edu/~blp/avl/libavl.html
3. Animation: http://www.cs.jhu.edu/~goodrich/dsa/trees/avltree.html
4. animation: http://www.strille.net/works/media_technology_projects/avl-tree_2001/

BTW, la fonction avlAdd() semble incorrecte. Je ne vois pas où aNew->num est comparé à a->num. Que ce soit pour aller à sous-arbre gauche ou sous-arbre droit doit dépendre de cela. Le code donné semble ajouter à la sous-arborescence gauche inconditionnellement.