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，还是只是期望 t 会被例程更改？