AVL树节点的删除规则
三种现象
现象1
注意:q是30，而不是20，因为删除了25，节点会移动,以下现象均遵循此规律
现象2
现象3
现象1和现象2比较简单,不需要平衡化处理,现象3则比较复杂.先讨论现象1和2
现象1删除步骤
先找到节点,然后删除节点
private Node FindNode(int value)
{
currentIndex = -1;
Node node = _head;
while (node != null)
{
path[++currentIndex] = node;
if (value == node.Data)
{
return node;
}
if (value < node.Data)
{ node = node.Left;
}
else
{ node = node.Right;
}
}
return null;
}
public bool Remove(int value)
{
var node = FindNode(value);
if (node != null)
{
RemoveNode(node);
return true;
}
return false;
}
其删除节点的子节点<2个,即只有左节点或者右节点或者没节点三种可能
- 如果删除的是右节点,那么该删除节点的子节点(如果有的话)将会代替该节点,反之也则替换左节点
- 代替的节点不是左节点就是右节点(只会是其中一个,若是两个子节点的情况则另外考虑)
var tmp = node.Left;
if (tmp == null)
{
tmp = node.Right;
}
if (currentIndex > 0)
{
if (path[currentIndex - 1].Left == node)
{
path[currentIndex - 1].Left = tmp;
}
else
{
path[currentIndex - 1].Right = tmp;
}
}
else
{
_head = tmp;
}
现象2删除步骤
即该节点的平衡因子为0，说明其左子树和右子树的高度是相同的
删除该节点后,其左节点代替父节点
但程序的做法没有我们看到这么简单
将左节点的值赋给父节点,然后将父节点的左节点以其原有左节点的左节点进行替换(即将15的值换成12,将15的左子节点换成12的左子节点，由于12没有左子节点,所以12的左子节点为空),程序如下
private void RemoveNode(Node node)
{
Node tmp = null;
if (node.Left != null && node.Right != null)
{
tmp = node.Left;
node.Data = tmp.Data; node.Left = tmp.Left;
}
}
现象3删除步骤
现象3和现象2方式前期处理方式相同,但是由于其左子树和右子树的高度不同导致了平衡因子出现2或-2的情况,后期还要进行处理,即是对于平衡因子的处理
平衡因子的处理
还是一样,当删除左节点时(父节点和某些祖父节点的)平衡因子-1，反之则+1
- 现象1则+1
- 现象2则-1
- 现象3则是父和祖父均-1
当平衡因子绝对值变成2了，则进行旋转
