C++ AVL Tree Implementierung

Question

Ich versuche AVL zu implementieren. Hier ist mein Einsatz, balance_tree, check_bf (Ausgleichsfaktor) und einzelne links drehen Funktionen um:

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

ich es ausprobiert mit einem kleinen Baum, der einen einzigen Linkslauf erfordert:

1 <----t 
\ 
    2 
    \ 
    3 

Bei Das Ende der einzelnen linken Drehfunktion, t zeigt auf 2 mit 1 als linker Knoten und 3 als rechter Knoten, also funktioniert die Funktion. Der Baum sieht wie folgt aus:

2<----t 
/\ 
1 3 

Wenn es jedoch um die Funktion verlässt, t bis 1 ohne nach links oder rechts Knotenpunkte. Ich verstehe nicht, was zwischen dieser Rückgabe t und der rechten Klammer} passiert, die die Funktion beendet, die t ändert. Kann jemand helfen?

Answer 1

Hier fehlt die Zeile, in der Sie die Funktion in Ihrem Test aufrufen. Ich glaube, ich höre, dass t unverändert ist, aber der Knoten, auf den t zeigt, ist verändert. Der Knoten, auf den t (die 1) zeigt, ist das erwartete Verhalten. Das t ist unverändert, ist nicht das, was Sie erwarten. Ihre Routine gibt einen Wert zurück. Weisen Sie diesen Wert t zu oder erwarten Sie nur, dass t von der Routine geändert wird?