AVL树插入和平衡 [英] AVL tree insertion and balancing

问题描述

我正在尝试在一个函数中执行插入，然后在另一个函数中需要时平衡树。



这是我的代码。 ..

I am trying to perform insertion in one function and then balance the tree if required in another.

Here is my code...

node* create_bst(node* tree,node* curr)
{
    if (tree==NULL)
        {
            return curr;
        }
    if(tree!=curr)
    {
    if(tree->key>=curr->key)
        {
            tree->left=create_bst(tree->left,curr);
        }
        else
            {   
                tree->right=create_bst(tree->right,curr);
            }
    }
    tree->bal_f=height(tree->left)-height(tree->right);
}

create_bst（tree，curr）将curr节点（包含密钥）添加到树简单二叉树插入，然后更新每个平衡因子构造树的节点。然后我调用平衡树的余额函数。

create_bst(tree,curr) adds curr node (that contains key) to the tree- simple binary tree insertion followed by updating of balance factor of each node of the constructed tree. Then i call the balance function that balances the tree.

node* balance(node* tree,node* curr)
{
if(tree->bal_f==2 or tree->bal_f==-2)
            {
if(tree->key>=curr->key)
    {
        balance(tree->left,curr);
        node* a=tree;
        node* b=new node;
        b=a->left;
        if(curr->key<b->key)
        {
            tree=LL_rotation(b,a);
        }   
        if(curr->key>b->key)
        {
            node* c=new node; 
            c=b->right;
            tree=LR_rotation(c,b,a);
        }   
    }
else
    {
        balance(tree->right,curr);
        node* a=tree;
        node* b=new node;
        b=a->right;
        if(curr->key>b->key)
        {
            tree=RR_rotation(b,a); 
        }
        if(curr->key<b->key)
        {
            node* c=new node; 
            c=b->left;
            tree=RL_rotation(c,b,a);  
        }   
    }
}   

curr与create_bst函数中添加的节点相同。



LL_rotation =执行左旋转并返回修改后的根节点。 LL表示curr节点已添加到节点左子节点的左侧，平衡因子为2或-2。相应地进行旋转。其余的情况也是如此。 LR_rotation =执行左旋转然后右旋转并返回修改后的根节点。



RR_rotation =执行右旋转并返回修改后的根节点。



RL_rotation =执行右旋转然后左旋转并返回修改后的根节点。



我面临的问题是旋转，虽然根节点在我的情况下改变旋转，但它保持不变。例如：如果我的输入是 - （2,0，-1）LL旋转它变为0,2，-1（预订）但我只得到2这是我的初始根。任何帮助都非常感谢。 ：）

curr is the same node that was added in the create_bst function.

LL_rotation= performs left rotation and returns the modified root node. LL means that curr node was added to the left side of the left child of the node with balance factor 2 or -2. rotations are performed accordingly. Same is the case with the rest. LR_rotation= perform left rotation followed by right rotation and returns the modified root node.

RR_rotation= performs right rotation and returns the modified root node.

RL_rotation= performs right rotation followed by left rotation and returns the modified root node.

The problem that i am facing is that with rotation that though the root node changes on rotation in my case its remaining the same. For example: if my input is -- (2,0,-1) on LL rotation it becomes 0,2,-1 (Preorder) but i am getting only 2 which was my initial root. Any help is highly appreciated. :)

推荐答案

我认为问题在于你错过了余额函数中的最终语句：

I think the problem is that you are missing the final statement in the balance function:

    ...
    return tree;
}

分配给树的语句对调用者无效：

（注释是指插入（2,0，-1）和插入最后-1节点后调用balance（）的例子。）

The statements that assign to tree have no effect that are visible from the caller:
(The comments are referring to your example of inserting (2,0,-1) and balance() is called after inserting the final -1 node.)

            // This changes the variable tree visible INSIDE the function, 
            // the callers pointer to tree remains unchanged to the 2 node as you
            // mentioned.
            tree=RL_rotation(c,b,a);  
        }   
    }
    // This now returns the pointer to the 0 node that has become the new root of the
    // balanced  tree.
    return tree;
}

这篇关于AVL树插入和平衡的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！