c++ - AVL树中的删除

Question

如您所知，删除节点后应如何平衡 avl，我将进入正题。首先，我考虑删除一个没有子节点的节点。

例如一棵树:

        10
      /     \
     5      17
   /  \    /  \ 
   2  9   12  20
    \           \
     3          50

让我们说 deletevalue(12);

那么删除后的树应该是:

        10
      /     \
     5      17
   /  \       \ 
   2  9       20
    \           \
     3          50

现在，我们看到树在节点 17 处是平衡的，因为根据公式，它的平衡因子 = 高度(左子树 [左子树为空所以 -1] )- 高度(右子树)= -2

所以我们通过检查它的右-右情况还是右-左情况来平衡树。

If BalanceFactor(17's right) = -1
    perform SingleLeftRotation(17);
else if BalanceFactor(17's right) = -1
    perform DoubleRightLeftRotation(17);

类似的情况是，如果 17 的平衡因子为 2，即它保持高电平，则其各自的旋转。//对于 bF(17) = 2

If BalanceFactor(17's left) = 1
    perform SingleLeftRotation(17);
else if BalanceFactor(17's left) = -1
    perform DoubleLeftRightRotation(17);

平衡后树应该变成这样:

          10
      /     \
     5      20
   /  \    /  \ 
   2  9   17  50
    \           
     3  

这是我设计的删除

从主函数调用

bool deletevalue(WA value)
{
    AvLNode<WA> *temp = search(root, value);    //calling search function to find node which has user-specified data & stored its address in temp pointer
    if(temp!=0) //if temp node is not null then
    {
        if(temp->left==0 && temp->right==0) //if temp node don't have any children
        {   deletewithNochild(root, value); }   //call to respective function
        else if( (temp->left!=0 && temp->right==0) || (temp->left==0 && temp->right!=0) )   //if temp node has any 1 child, left or right
        {   deletewithOneChild(temp);   }   //call to respective function
        else if(temp->left!=0 && temp->right!=0)    //if temp node has 2 children
        {   deletewith2Child(temp);     }   //call to respective function

        return true;    //for prompting respective output message
    }
    else
        return false;   //for prompting respective output message
}

由于我们所需的节点没有子节点，因此调用了以下函数。

void deletewithNochild(AvLNode<WA> *temp, WA value) //temp is node which is to be deleted
{
    if(value == root->key)  //if temp is root node then
    {
        delete root;    //free memory of root node
        root = 0;   //nullify root
    }
    else    //if temp is some other node 
    {
        if (value < temp->key)
        {
            deletewithNochild(temp->left, value);
        }
        else if (value > temp->key)
        {
            deletewithNochild(temp->right, value);
        }
        else if (value == temp->key)
        {
            AvLNode<WA> *father = findfather(temp, root);   //calling findfather func to find father of temp node & store its address in father node pointer

            if(father->left==temp)  //if temp is left child of its father
            {
                delete temp;    //free memory of temp node
                father->left=0; //nullify father's left
            }
            else if(father->right==temp)    //if temp is right child of its father
            {
                delete temp;    //free memory of temp node
                father->right=0;//nullify father's right
            }
            return;
        }
        cout<<"\nBalancing";
        if ( balancefactor(temp) == 2)  //if temp is left higher, ie. temp's Balance Factor = 2, then
        {
            cout<<"\t2 ";
            if ( balancefactor(temp->left) == 1 ) //if temp's left node has Balance Factor 1 then
            {
                SingleRightRotation(temp);  //send temp node for rotation because temp is unbalance
            }
            else if ( balancefactor(temp->left) == -1 ) //if temp's left node has Balance Factor -1, then
            {
                DoubleLeftRightRotation(temp);  //send temp for double rotation because temp is unbalance
            }
        }
        else if ( balancefactor(temp) == -2 )   //if temp is right higher, ie. temp's Balance Factor = -2, then
        {
            cout<<"\t-2 ";
            if ( balancefactor(temp->right) == -1 ) //if temp's left node has Balance Factor -1 then
            {
                SingleLeftRotation(temp);   //send temp node for rotation because temp is unbalance
            }
            else if ( balancefactor(temp->right) == 1 ) //if temp's right node has Balance Factor 1, then
            {
                DoubleRightLeftRotation(temp);  //send temp for double rotation because temp is unbalance
            }
        }

    }
}

这里有节点的HEIGHT和节点的BALANCE FACTOR这两个效用函数

int heightofnode(AvLNode<WA> *temp) const
{
    return temp==NULL ? -1 : temp->height;
}


int balancefactor(AvLNode<WA> *temp) const
{
    return ( heightofnode(temp->left) - heightofnode(temp->right) );
}

我的输出，当我删除 12 时变成(广度优先遍历)-->> [10] [9] [17]

请帮帮我，递归有什么问题吗？我一次又一次试运行，但无法理解。删除必须通过递归完成，否则平衡树将是一个更大的 hell 。提前感谢您抽出时间。 :-)

Answer 1

为什么 deletewithNochild() 会调用任何其他 delete* 方法？如果调用 deletewithNochild，则您位于要删除的节点。简单地删除它，向上移动到它的父级，并检查父级平衡因子并在需要时旋转。对每个节点的父节点重复重新平衡，直到到达根。

如果有帮助，我已经实现了 AVL tree in Java ，如果您需要引用。