对于平衡二叉树的删除方法是一样需要照顾平衡二叉书的平衡的,删除结点会导致bf的值改变,对于不平衡的需要平衡一下。
static bool DeleteElement(ref Node node, int data, ref bool lower)
{
bool L = false, R = false;
if (node == null) return false;
if (node.data == data)
{
Node p, s;
p = node.cRight;
s = p;
lower = true;
if (node.cRight == null)
{
p = node;
node = node.cLeft;//右边为空,直接把左边替换上去
lower = true;
return true;
}
else
{
while (s != null)
{
p = s;//找到的最左结点
s = s.cLeft;
}
node.data = p.data;//替换数据,引用保留
DeleteElement(ref node.cRight, data, ref lower);//删除那个最小结点
R = true;//往右走
}
}
else if (data < node.data)
{
DeleteElement(ref node.cLeft, data, ref lower);
L = true;
}
else
{
DeleteElement(ref node.cRight, data, ref lower);
R = true;
}
if (lower)
{
if (L)
{
switch (node.bf)
{
case LH:
node.bf = EH;
lower = true;
break;
case RH://本来右边高了,又删了个左边,所以要右平衡一下
RightBalance(ref node);
lower = false;
break;
case EH:
node.bf = RH;
lower = false;
break;
}
}
else
{
switch (node.bf)
{
case EH:
node.bf = LH;
lower = false;
break;
case RH:
node.bf = EH;
lower = true;
break;
case LH:
LeftBalance(ref node);
lower = false;
break;
}
}
}
return true;
}采用递归的方式,同样的有一个标志位lower来去判断是否需要平衡的检查。删除结点的操作是一样的,发现小的数据往左边,发现大的往右边,当相等的时候就是要删除的数据了。
同样分两种情况,右边为空,则直接将左边结点替换根。如果右边不为为空,则找到右边的最小(左)结点,替换调根的数值但保留根的左右结点,再删除最小结点。
平衡判断也是看情况的,比如说本来右边高的1,然后把左边删了,那就不平衡了,需要右平衡调整一下。