对于平衡二叉树的删除方法是一样需要照顾平衡二叉书的平衡的,删除结点会导致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,然后把左边删了,那就不平衡了,需要右平衡调整一下。