C++ AVL樹實現

Question

我試圖實現AVL。這裏是我的插入，balance_tree，check_bf（平衡因子），以及單左，以旋轉功能：

BinaryNode *BinarySearchTree::insert(int x,BinaryNode *t, int dpt) throw(DuplicateItem) 
{ 
    if (t == NULL) t = new BinaryNode(x,NULL,NULL,dpt+1); 
    else if (x < t->element) t->left = insert(x, t->left, dpt+1); 
    else if (x > t->element) t->right = insert(x, t->right, dpt+1); 
    else 
     throw DuplicateItem(); 
    balance_tree(t); 
    return t; 
} 
BinaryNode* BinarySearchTree::balance_tree(BinaryNode *t) 
{ 
    double debug = check_BF(t); 
    while(check_BF(t)>1 || check_BF(t)<-1) 
    { 
     if(check_BF(t)>1) 
     { 
      if(check_BF(t->right)<-1) return doubleLeft(t); 
      else return singleLeft(t); 
     } 
     else if(check_BF(t)<-1) 
     { 
      if(check_BF(t->left)>1) return doubleRight(t); 
      else return singleRight(t); 
     } 
    } 
} 
double BinarySearchTree::check_BF(BinaryNode *t) 
{ 
    double l, r; 
    if(t->left!=NULL) l = t->height(t->left)+1; 
    else l=0; 

    if(t->right!=NULL) r = t->height(t->right)+1; 
    else r=0; 

    return r-l; 
} 
BinaryNode* BinarySearchTree::singleLeft(BinaryNode *t) 
{ 
    BinaryNode* Y = t; 
    if(Y!=NULL) 
    { 
     t = t->right; 
     Y->right = t->left; 
     t->left=Y; 
    } 
    return t; 
} 

我嘗試過了一個小的樹，只需要一條向左旋轉：

1 <----t 
\ 
    2 
    \ 
    3 

在單左旋轉函數結束時，t指向2，其中1作爲左節點，3作爲右節點，所以函數起作用。樹看起來像這樣：

2<----t 
/\ 
1 3 

但是，當它退出函數時，t指向1，沒有左或右節點。我不明白在返回t和右括號}之間會發生什麼，從而結束改變t的函數。誰能幫忙？

Answer 1

這裏缺少的是您在測試中調用該函數的行。我想我聽到你說t不變，但t點的節點發生了變化。 t點（1）改變的節點是預期的行爲。這不會改變你所期望的。你的例程返回一個值。你是把這個值分配給t，還是隻希望t被程序改變？