AVLTree实现(C++)：我是否可以将删除()描述为插入()的情况，以便重用代码？

Question

在这件事上请原谅我，因为我认为这有点难以解释：

根据R.Coleman的实现，我构建了以下AVLTree::Insert() proc：

void AVLTree::Insert(AVLTreeNode *newNode)  ///MARKER: ####### REMINDER ######
{                                           ///This implementation REQUIRES that newNode has its @left, @right and @parent pointers set to NULL *BEFORE* sending him here, as a parameter
    AVLTreeNode *temp, *prev, *ancestor;

    temp = root;                            //Our temp starts at the root, and keeps heading down the tree until it "falls out".
    prev = NULL;                            //@prev will "follow" @temp, one step behind it. It will, in the end, mark the point where we'll add newNode at.
    ancestor = NULL;                        //Ancestor marks the position of the closest @ancestor that will drop out of balance after we insert newNode.

    if(root == NULL )                       //Check if the tree is empty before you do anything else.
    {
        root = newNode;
        return;
    }
    //Looks like it isn't empty. Let's start the main loop.
    while(temp != NULL)
    {
        prev = temp;
        if(temp->balanceFactor != '=')      //We found a node that is unbalanced, it'll drop out of balance completelly when we add the new node.
        {                                   //Let's have the @ancestor variable point at it so we can restore the AVL property from the bottom to this node.
            ancestor = temp;
        }
        if(newNode->value < temp->value)    //These two ifs will throw @temp out of the tree at the end of the loop
        {                                   //while @prev will be pointing at the node below which we'll be adding newNode
            temp = temp->left;
        }
        else
        {
            temp = temp->right;
        }
    }
    ///The loop finished, @temp is now null. Time to insert newNode.
    newNode->parent = prev;
    if(newNode->value < prev->value)        //If it's smaller than @prev, place it on its left, else do it at @prev's right.
    {
        prev->left = newNode;
    }
    else
    {
        prev->right = newNode;
    }
    ///Now to restore the AVL property of the tree, starting from the inserted node up towards @ancestor, the last known unbalanced node that has now completely fallen out of balance.
    restoreAVL(ancestor,newNode);
}

注意到，在最后，调用了以newNode和祖先作为参数的RestoreAVL (最后一个节点备份了需要调整的树，因为他失去了平衡--它在while(temp!=null)循环中被指向一个节点)。

这是AVLTree::restoreAVL()：，如果您费心阅读它，它会考虑到在AVLTree 中插入一个新节点可能发生的每一种情况，并在需要时注意恢复AVL属性，同时进行旋转并重新设置平衡因子 (L、R或=)。

void AVLTree::restoreAVL(AVLTreeNode *ancestor, AVLTreeNode *newNode)
{   ///This process restores the AVL property in the tree, from the bottom
    //-------------------------------------------------------
    // Case 1: ancestor is NULL, that means the balanceFactor of all ancestors is '='
    //-------------------------------------------------------
    if(ancestor == NULL)
    {
        if(newNode->value < root->value)
        {
            root->balanceFactor = 'L';  //newNode was inserted at the left of our root
        }                               //during our previous Insert
        else
        {
            root->balanceFactor = 'R';  //Here it's on our right
        }
        ///Adjust the balanceFactor for all nodes from newNode back up to root
        adjustBalanceFactors(root, newNode);
    }
    //-------------------------------------------------------
    // Case 2: Insertion in opposite subtree of ancestor's balance factor, i.e.
    // ancestor.balanceFactor == 'L' AND Insertion made in ancestor's RIGHT subtree
    // OR
    // ancestor.balanceFactor == 'R' AND Insertion made in ancestor's LEFT subtree
    // (In short, the insertion "neutralises" the balance of ancestor.)
    //-------------------------------------------------------
    else if(    ( (ancestor->balanceFactor == 'L') && (newNode->value > ancestor->value) )
                ||
                ( (ancestor->balanceFactor == 'R') && (newNode->value < ancestor->value) )
           )
    {
        ancestor->balanceFactor = '=';  //Ancestor's balance factor is now neutralised.
        ///Adjust the balanceFactor for all nodes up to the ancestor,
        ///not up to the root like we did in Case 1.
        adjustBalanceFactors(ancestor,newNode);
    }
    //-------------------------------------------------------
    // Case 3: @ancestor's balance is 'R' and the new node was inserted in the right subtree of @ancestor's right child.
    // As expected, the balance is now broken and we need to rotate left, once.
    //-------------------------------------------------------
    else if( (ancestor->balanceFactor == 'R') && (newNode->value > ancestor->right->value) )
    {
        ancestor->balanceFactor = '=';  //We reset @ancestor's balance, it will be adjusted by @adjustBalanceFactors()
        rotateLeft(ancestor);           //Single left rotation with ancestor as the pivot.
        ///Let's adjust the balanceFactor for all nodes up to @ancestor's PARENT.
        adjustBalanceFactors(ancestor->parent, newNode);
    }
    //-------------------------------------------------------
    // Case 4: @ancestor's balance is 'L' and the node inserted is in the left subtree of @ancestor's left child.
    // Here we have to rotate right, once. (Mirror case of Case 3 - See above)
    //-------------------------------------------------------
    else if( (ancestor->balanceFactor == 'L') && (newNode->value < ancestor->left->value) )
    {
        ancestor->balanceFactor = '=';  //As before, @ancestor's balance needs to be reset.
        rotateRight(ancestor);
        ///Again, we adjust the balanceFactor for all nodes up to @ancestor's PARENT.
        adjustBalanceFactors(ancestor->parent, newNode);
    }
    //-------------------------------------------------------
    // Case 5: @ancestor's balance factor is "L" and the new node is inserted
    // in the RIGHT subtree of ancestor's LEFT child
    //-------------------------------------------------------
    else if( (ancestor->balanceFactor == 'L') && (newNode->value > ancestor->left->value) )
    {
        rotateLeft(ancestor->left);
        rotateRight(ancestor);
        adjustLeftRight(ancestor,newNode);
    }
    //-------------------------------------------------------
    // Case 6 (final case): @ancestor's balance factor is "R" and the new node is inserted
    // in the LEFT subtree of ancestor's RIGHT child
    //-------------------------------------------------------
    else
    {
        rotateRight(ancestor->right);
        rotateLeft(ancestor);
        adjustRightLeft(ancestor,newNode);
    }
}

所以我的问题是:我想实现AVLTree::Delete(AVLTreenode *n)。如果您删除AVLTree中的一个节点，我可以将删除()减少为插入()情况，并调用restoreAVL()，其中一些节点集为newNode，一个节点集为祖先？，我可以回收RestoreAVL()，而不是绞尽脑汁地思考每一个可能的结果吗？

下面是一些例子：

​

​

如果我认为忽略00之后，在子树中插入20，结果是相同的。

但是，让我们在左边的树上添加节点70，并尝试将删除()减少到Insertation中。

​

​

我想不出任何算法方法来将这种情况简化为Insertation()，因此我知道谁可以充当newNode，谁可以是祖先，并调用restoreAVL()。

我说的是可行的吗？是否有一种减少问题从而减少我必须重写的代码的故障安全方法？

Answer 1

显然，您可以找到一些常见的删除和插入操作(例如搜索)，但我认为这不值得尝试。这些算法之间仍然有很多不寻常的地方。您肯定会重用restoreAVL进行AVL属性恢复。

正如我所理解的，您的示例中的问题是，当您从一个子树中删除节点时，您希望平衡从根到已删除节点的路径上的最后一个平衡节点的另一个子树(其中平衡节点是具有balancedFactor=‘=’‘的节点)。对我来说，这是没有意义的，因为它一开始是不正确的，而且代码要复杂得多。

Answer 2

如果可以编写代码插入运算符，则可以对其进行代码删除。因为删除比插入简单。这是真的，因为您不需要在删除操作符中重新平衡。对于每个查询，复杂性仍然是O(log )。

我的代码不太高效，但它足够短，足以编写代码。

void doDelete(node* a){
    if (a==0) return ;
    if (a->ll==0) {
        if (a->pp==0 || a->pp->ll==a)
        lljoin(a->rr, a->pp);
        else rrjoin(a->rr, a->pp);
        delete a;
    }
    else if (a->rr==0){
        if (a->pp==0 || a->pp->ll==a)
        lljoin(a->ll, a->pp);
        else rrjoin(a->ll, a->pp);
        delete a;
    }
    else {
        node *b = rightMost(a->ll);
        swap(b->value, a->value);
        doDelete(b);
    }
}