平衡二叉树的删除方法

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


首页 我的博客
粤ICP备17103704号