двоичное дерево — реализация AVLTree (C ++): Могу ли я описать delete () как случай insert () для повторного использования кода?

Терпите меня на этом, потому что я думаю, что это довольно сложно объяснить:

Я построил следующее AVLTree :: Insert () proc, согласно реализации R.Coleman:

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);
}

Обратите внимание, что в конце, Я вызываю RestoreAVL, который принимает в качестве параметров newNode и ancestor (последний узел резервирует дерево, которое необходимо настроить, потому что он вышел из равновесия — он указывает на узел во время цикла 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, я могу уменьшить Deletion () в случае Insertion () и вызвать RestoreAVL () с некоторым узлом, установленным как newNode, и одним, установленным как предок? Могу ли я перезапустить restoreAVL ()?

Некоторые примеры:

Результат тот же, если я думаю, что после игнорирования 00 в поддерево вставляется 20.

Но давайте добавим узел 70 на левом дереве, и попробуйте уменьшить Deletion () в диссертации.

Я не могу придумать какой-либо алгоритмический способ свести эту ситуацию к Instruction (), поэтому я знаю, кто может выступать в качестве newNode, а кто может быть предком, и вызывать restoreAVL ().

Возможно ли то, что я говорю? Есть ли надежный способ уменьшить проблему и, следовательно, уменьшить код, который я должен переписать?