1

我正在尝试实现 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，没有左节点或右节点。我不明白 return t 和右括号 } 之间会发生什么，它结束了更改 t 的函数。任何人都可以帮忙吗？

4

1 回答 1

1

这里缺少的是您在测试中调用该函数的行。我想我听到你说 t 没有改变，但是 t 指向的节点发生了变化。t 指向的节点（1）被改变是预期的行为。t 不变不是您所期望的。您的例程返回一个值。您是将该值分配给 t，还是只是期望 t 被例程更改？

于 2012-04-07T19:33:57.673 回答