在AVL BST中插入

Question

我正在學習AVL樹，這讓我覺得很不舒服，但我無法讓它正常工作。

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 

#define LEFT -1 
#define BAL 0 
#define RIGHT 1 


typedef int Key; 
typedef void * Info; 


struct avltree { 
     int bal; 
     Key key; 
     Info info; 
     struct avltree *left, *right; 
}; 

typedef struct avltree *BTree; 

BTree newBTree (Key k, Info i, BTree l, BTree r) { 
     BTree n; 

     n = (BTree) malloc (sizeof (struct avltree)); 
     if (n) { 
       n->key = k; 
       n->info = i; 
       n->bal = BAL; 
       n->left = l; 
       n->right = r; 
     } 
     return n; 
} 
BTree fixLeft (BTree a); 
BTree fixRight (BTree a); 
BTree addAux (BTree a, Key k, Info i); 


BTree rotateLeft (BTree a) { 
     BTree b = a->right; 
     a->right = b->left; 
     b->left = a; 
     return b; 
} 

BTree rotateRight (BTree a) { 
     BTree b = a->left; 
     a->left = b->right; 
     b->right = a; 
     return b; 
} 

BTree add (BTree a, Key k, Info i) { 

     return (addAux (a,k,i)); 
} 


int max (int x, int y){ 
     int m = x>y ? x : y; 

     return m; 
} 

int height(BTree t){ 
     if(!t){ 
       return 0; 
     } 

     int m = max(height(t->left), height(t->right)) + 1; 

     return m; 
} 


BTree addAux (BTree a, Key k, Info i) { 
     if (a == NULL) { 
       a = newBTree (k,i,NULL,NULL); 
       a->bal = BAL; 

     } else if (a->key > k) { 
       a->left = addAux (a->left,k,i); 

           //once a->left gets his value, bellow i will compare 
           //the size of both left and right subtrees 

       int l = height(a->left); 
       int r = height(a->right); 

           //If the left one is bigger by just one unit , is ok 
           //as it gets a mark saying the left side is heavier 
           //and otherwise if it's bigger on the right 

       if(l-r == 1){ 
           a->bal = LEFT; 
       }else if(l-r == -1){ 
           a->bal = RIGHT; 
       } 

           //Here i tell that if the left side has a heavy-factor of 2 
           //i get it fixed by calling fixLeft 

       else if(l-r > 1){ 
           a->bal = LEFT; 
           fixLeft(a); 
       }else if(l-r < -1){ 
           a->bal = RIGHT; 
           fixRight(a); 
       } 

           //And vice-versa on this else 

     } else { // (a->key < k) 
       a->right = addAux (a->right,k,i); 
       int l = height(a->left); 
       int r = height(a->right); 

       if(l-r == 1){ 
           a->bal = LEFT; 
       }else if(l-r == -1){ 
           a->bal = RIGHT; 
       } 

       else if(l-r > 1){ 
           a->bal = LEFT; 
           fixLeft(a); 
       }else if(l-r < -1){ 
           a->bal = RIGHT; 
           fixRight(a); 
       } 


       } 
       return a; 
} 

BTree fixLeft (BTree a) { 
     if (a->left->bal == LEFT) { 
       a = rotateRight (a); 
       a->bal = a->right->bal = BAL; 
     } 
     else { 
       a->left = rotateLeft(a->left); 
       a = rotateRight (a); 
       a->bal = a->right->bal = BAL; 
     } 
     return a; 
} 

BTree fixRight (BTree a) { 
     if (a->right->bal == RIGHT) { 
       a = rotateLeft (a); 
       a->bal = a->left->bal = BAL; 
     } 
     else { 
       a->right = rotateRight(a->right); 
       a = rotateLeft (a); 
       a->bal = a->left->bal = a->right->bal = BAL; 
     } 
     return a; 
} 

void dumpKeys (BTree a, int level){ 
     int l; 
     if (a) { 
       dumpKeys (a->right, level+1); 
       for (l=0;l<level;l++) printf ("%5c",' '); 
       printf ("%5d\n", a->key); 
      dumpKeys (a->left, level+1); 
     } 
} 



int main(){ 
     BTree a = NULL; 

     a=add(a,10,NULL); 
     a=add(a,20,NULL); 
     a=add(a,15,NULL); 

     dumpKeys (a,0); 
     return 0; 
} 

某處我失去了指向我猜測的下一個節點的指針，它只輸出根或插入的第一個元素。調試器沒有錯誤。

謝謝！

最小，完整，可驗證例如：

http://pastebin.com/zyziTyXJ

Answer 1

的問題是非常簡單的解決時，我真是頭暈幾個小時後。

我在調用函數fixRight和fixLeft，當他們返回一個BTree，但沒有分配返回值爲空。

因此，這裏是錯誤固定：

... 
    else if(l-r > 1){ 
      a->bal = LEFT; 
      a = fixLeft(a); //HERE 
    }else if(l-r < -1){ 
      a->bal = RIGHT; 
      a = fixRight(a); //HERE 
    } 
...