C++ AVL 트리 구현

Question

AVL을 구현하려고합니다. 여기 내 삽입, balance_tree, check_bf (균형 요인), 그리고 하나의 왼쪽 순서대로 기능을 회전 :

1 <----t 
\ 
    2 
    \ 
    3 

에서 : 나는 하나의 왼쪽 회전을 필요로하는 작은 나무와 그것을 밖으로 시도

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; 
} 

단일 왼쪽 회전 함수의 끝, t는 2로 1을 왼쪽 노드로, 3을 오른쪽 노드로 가리키고 함수가 작동합니다. 이 트리는 다음과 같습니다.

2<----t 
/\ 
1 3 

그러나 함수를 종료하면 t는 왼쪽 또는 오른쪽 노드없이 1을 가리 킵니다. 그 반환 t와 오른쪽 대괄호 사이에 무슨 일이 일어나는지 이해하지 못한다.}는 t를 변경하는 함수를 끝낸다. 누구든지 도와 줄 수 있습니까?

Answer 1

여기서 누락 된 부분은 테스트에서 함수를 호출 한 행입니다. 나는 당신이 t가 변하지 않았다고 말하지만, t 점이 변하는 노드를 바꾸 었다고 들었습니다. t 점 (1)이 변경된 노드가 예상되는 동작이라는 것입니다. t는 변하지 않습니다. 당신이 기대하는 바가 아닙니다. 루틴은 값을 반환합니다. 당신은 그 값을 t로 할당하고 있습니까, 아니면 단순히 t가 루틴에 의해 변경 될 것으로 기대하고 있습니까?