如你所知，在删除节点后应如何平衡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]
请帮帮我，递归有什么问题吗？我又一次又干又乱，却无法理解。删除必须通过递归完成，否则平衡树将是一个更大的地狱。提前谢谢你给予时间。 :-)
为什么deletewithNochild（）调用任何其他delete *方法？如果调用了deletewithNochild，则表示您处于要删除的节点。只需删除它，向上移动到它的父级，然后检查父级平衡因子并根据需要旋转。为每个节点的父节点重复重新平衡，直到到达根节点。
如果它有帮助，我已经实现了AVL tree in Java，如果你想要一个参考。