红黑树学习笔记

Scroll Down

红黑树学习笔记

红黑树的概念

红黑树是一种二叉查找树,也是一种特殊的平衡二叉树,因为没有AVL这种很严苛的平衡条件,所以平衡的程度没有像AVL一样非常的极致,但是进行操作的效率要比AVL要高。
红黑树就像魔方一样,有各种情况,我们看到某一种情况就可以套公式进行变换,达到想要的目的

红黑树的规则/性质

1.每一个节点 必须为红色或者黑色
2.根节点是黑色的
3.空节点是黑色的
4.同一个路径下 不允许出现两个相邻的红色节点

如果这些东西要解释清楚的话,要从2-3树说起。

一个好用的网站

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

一个动态插入和删除红黑树结点的网站,对学习很有帮助

参考博客

https://blog.csdn.net/a944750471/article/details/92384553
https://segmentfault.com/a/1190000012728513
https://blog.csdn.net/qq_38412637/article/details/86548278
https://my.oschina.net/u/3737136/blog/1649433

红黑树的结点设计

采用三叉链表的二叉树结点存储红黑树,多一个颜色变量和一个指针指向其父母

public class RedBlackNode<T extends Comparable<T>> {
    public static final int RED = 0;
    public static final int BLACK = 1;
    private int color;
    public T data;
    public RedBlackNode<T> left;
    public RedBlackNode<T> right;
    public RedBlackNode<T> parent;
    public static <T extends Comparable<T>> int getColor(RedBlackNode<T> node)
    {
        if (node==null)
            return BLACK;
        return node.color;
    }
    public static <T extends Comparable<T>> boolean isRed(RedBlackNode<T> node)
    {
        //空结点为黑色
        if (node == null)
            return false;
        return node.color==RED;
    }
}

红黑树的几个操作

左旋

//左旋
private RedBlackNode<T> rotateLeft(RedBlackNode<T> node)
{
    RedBlackNode<T> x = node.right;
    RedBlackNode<T> temp = x.left;
    x.left = node;
    node.parent = x;
    node.right = temp;
    if (temp != null)
        temp.parent = node;
    return x;
}

右旋

// 右旋
private RedBlackNode<T> rotateRight(RedBlackNode<T> node)
{
    RedBlackNode<T> x = node.left;
    RedBlackNode<T> temp = x.right;
    x.right = node;
    node.parent = x;
    node.left = temp;
    if (temp != null)
        temp.parent = node;
    return x;
}

变色

把两个子节点的颜色置为黑,将自己的颜色置为红(在后文中写了适用场景)

//交换颜色
private RedBlackNode<T> flipColor(RedBlackNode<T> node)
{
    node.left.setColor(RedBlackNode.BLACK);
    node.right.setColor(RedBlackNode.BLACK);
    node.setColor(RedBlackNode.RED);
    return node;
}

红黑树的插入规则

规则比较复杂,但是我们可以分类阐述

要插入的结点是根节点

这种情况是最简单,直接插入就好,然后根据原则,我们把根节点改成黑色

插入到一个黑色结点

不需要调整,直接插入就好

插入到红色结点下

这种情况是最复杂的,需要依靠父节点的叔叔结点(sibling)来进行判断

叔叔的黑色

这种情况比较复杂

父亲是祖父的左孩子
插入到父亲的左边


在这种情况下,我们在0下插入-1
对于这种情况,我们需要对1进行右旋,并交换1和0的颜色

这种情况的操作就完成了

插入到父亲的右边


我们将7插入到5的右侧
对于这种情况,我们需要先对5进行左旋,并交换颜色

然后就变成上一种情况,我们再对10进行右旋,并交换颜色

这种情况的操作就完成了

父亲的祖父的右孩子

这种情况是父亲是祖父的左孩子的一种镜像,问题就变得简单起来

插入到父亲的右边


很明显,这是违反红黑树规则的,对于这种情况,我们只需要对其祖父进行左旋操作,并交换颜色

插入到父亲的左边


我们把6插入到父亲的左边,对于这种情况,我们需要对7进行右旋操作

再对其祖父5进行左旋,并交换颜色

叔叔是红色

这种情况比较简单,违反了相邻两个结点不能同时为红色原则,只需要进行一下变色处理,把父亲和叔叔都变为黑色,把祖父变为红色,再对祖父的祖父检查是否是红色,如果是红色,进行违约修改

进行变色操作

因为根节点必须是黑色,所以再进行变色

这种情况的操作也算完成了

祖父和曾祖父同为红色


就像这样,插入90,7和18经过变色,把8变成了红色,8和6同时为红色,这种情况下,我们应该把8视为一个刚插入的结点,并对其进行修改

插入的代码实现

现在插入的规则和方法已经阐述完了,接下来我们来看代码吧

public RedBlackNode<T> add(RedBlackNode<T> node, T t)
{
    boolean indicator = false;      //指示插入的结点为左还是为右,false是左,true是右
    if (node==null)
        return null;
    //向左子树插入
    if (node.data.compareTo(t)>0)
    {
        if (node.left==null) {
            node.left = new RedBlackNode<>(t);
            node.left.parent = node;
        }else {
            node = add(node.left, t);
            return node;
        }
        indicator = false;
    }else if (node.data.compareTo(t)<0){
        if (node.right==null) {
            node.right = new RedBlackNode<>(t);
            node.right.parent = node;
        }else {
            node = add(node.right, t);
            return node;
        }
        indicator = true;
    }
    fixViolation(node,indicator);
    this.root.setColor(RedBlackNode.BLACK);
    return node;
}

修复违约的方法

/**
* 修复插入后的违反规定的部分
* @param node  插入结点的父亲结点
* @param indicator 指示新插入结点是node的左还是右
*/
private void fixViolation(RedBlackNode<T> node,boolean indicator)
{
//父亲为红色
if (RedBlackNode.isRed(node))
{
    RedBlackNode<T> parent = node.parent;       //祖父结点
    RedBlackNode<T> uncle = null;
    //取得叔叔结点
    if (node == parent.left)
        uncle = parent.right;
    else
        uncle = parent.left;
    //如果叔叔父亲同为红色
    if (RedBlackNode.isRed(uncle))
    {
        flipColor(parent);
        if (RedBlackNode.isRed(parent.parent))
            if (parent==parent.parent.right)
                fixViolation(parent.parent,true);
            else
                fixViolation(parent.parent,false);
    }
    else {
        //叔叔为黑色
        if (node==parent.left){
            if (indicator){
                //新插入的结点在右
                parent.left = rotateLeft(node);
                parent.left.parent = parent;
            }
            if (parent.parent==null)
            {
                //如果祖父是根节点
                this.root = rotateRight(parent);
                this.root.parent = null;        //一定要写
            }else {
                RedBlackNode<T> grand = parent.parent;
                if (grand.left == parent)
                {
                    grand.left = rotateRight(parent);
                    grand.left.parent = grand;
                }else {
                    grand.right = rotateRight(parent);
                    grand.right.parent = grand;
                }
            }
        }else {
            //如果node为parent的右结点
            if (!indicator) {
                //新插入的结点在左
                parent.right = rotateRight(node);
                parent.right.parent = parent;
            }
            if (parent.parent == null) {
                //如果祖父是根节点
                this.root = rotateLeft(parent);
                this.root.parent = null;        //一定要写
            } else {
                RedBlackNode<T> grand = parent.parent;
                if (grand.left == parent) {
                    grand.left = rotateLeft(parent);
                    grand.left.parent = grand;
                } else {
                    grand.right = rotateLeft(parent);
                    grand.right.parent = grand;
                }
            }
        }
    }
}
}

红黑树的删除

红黑树的删除分为几种情况

被删结点无子结点,且被删结点为红色

这种情况不会改变其性质,直接删除即可

被删结点无子结点,且被删结点为黑色

被删结点的兄弟是黑色,且有个与其同方向的红色孩子(无关父亲结点的颜色)


例如,我要删除7
这种情况,我们需要先对8进行左旋,被删结点在哪就往哪里旋转,旋转完删除,并尝试重新着色,把8和18的颜色对调(父亲和兄弟的颜色对调),然后将父亲置为黑色,其兄弟的儿子置为黑色

最后删除7结点

被删除结点的兄弟为黑色,且其兄弟有一个与其方向不一致的红色子结点


同样删除7,我们要把18和90旋转,就变成了上一种情况(被删结点的兄弟是黑色,且有个与其同方向的孩子),同样无关父亲的颜色

被删除结点的兄弟为黑色,且兄弟无红色子结点

此时需要看父亲的颜色,分两种情况

如果父亲的颜色为红色


删除7,其兄弟90的子节点都为黑色,这种情况比较简单,把父亲和兄弟交换颜色即可

如果父亲结点是黑色

这种情况

我们删除1或者3都是这导致情况,假设要删除1,我们要做的就是删除1,并假设删除其父节点2,然后一直向上传递到根结点

被删除结点的兄弟为红色

这种情况下,其父亲必为黑色
我们只需要将兄弟和父亲旋转


并把当前父亲和侄子结点染黑

被删结点有一个子结点,且被删结点为黑色

这种情况比较简单,直接将被删结点的孩子结点来取代被删结点的位置,并将其置为黑色

删除1,让0取代1的位置,并将0置为黑色

被删结点有两个子结点,且被删结点为黑色或红色

这种情况和二叉搜索树中的一种删除情况比较类似,我们去找其右子树中的最小值,然后进行值上的替代,删除最小值

比如说这张图中,我要删除8,我就要去找右子树中的最小值,找到90,将90替代8的位置,删除90

删除的代码实现

这是一些小的包装方法,放上来

/**
 *  删除方法,根据值删除
 * @param t
 * @return
 */
public RedBlackNode<T> delete(T t)
{
    //找到要删除的那个结点
    RedBlackNode<T> tNode = find(t);
    remove(tNode);
    return tNode;
}
public RedBlackNode<T> remove(RedBlackNode<T> node){
    fixViolationBeforeRemove(node);
    return delete(node);
}
/**
 * 根据值找到某个结点
 * @param t
 * @return  返回被找到的那个结点
 */
public RedBlackNode<T> find(T t)
{
    RedBlackNode<T> p = this.root;
    while (p!=null && !p.data.equals(t))
    {
        if (p.data.compareTo(t)>0)
            p = p.left;
        else if (p.data.compareTo(t)<0)
            p = p.right;
    }
    return p;
}
/**
 * 删除某个结点,断开父母和他的关系,以及断开和父母的关系
 * @param node
 * @return  返回被删除的那个结点
 */
private RedBlackNode<T> delete(RedBlackNode<T> node)
{
    //如果node的父亲没有指针指向node就不进行指针的置空
    if (node.parent!=null&&node.parent.left==node)
        node.parent.left=null;
    else if (node.parent!=null&&node.parent.right==node)
        node.parent.right=null;
    node.parent=null;
    return node;
}

最后是最重要的调整方法

/**
 * 在删除前修复二叉树的结构
 * node是假设要删除的结点
 * @param tNode
 */
private void fixViolationBeforeRemove(RedBlackNode<T> tNode)
{
    //到根节点递归终止
    if (tNode==null)
        return;
    //第一种情况,tNode是红色叶子结点,不需要修复,直接删除
    //被删结点有一个子结点,且被删结点为黑色
    //直接将被删结点的孩子结点来取代被删结点的位置,并将其置为黑色
    if (!RedBlackNode.isRed(tNode) && !(tNode.left!=null && tNode.right!=null) && !RedBlackNode.isLeaf(tNode))
    {
        //获取孩子结点
        RedBlackNode<T> child = null;
        if (tNode.left!=null)
            child = tNode.left;
        else
            child = tNode.right;
        //进行替换
        if (tNode == tNode.parent.left)
            tNode.parent.left = child;
        else
            tNode.parent.right = child;
        child.setColor(RedBlackNode.BLACK);
        child.parent = tNode.parent;
    }
    //被删结点有两个子结点,且被删结点为黑色或红色
    else if (tNode.left!=null && tNode.right!=null)
    {
        //我们去找其右子树中的最小值,然后进行值上的替代
        RedBlackNode<T> temp = tNode.right;
        //寻找最小值
        while(!RedBlackNode.isLeaf(temp) && temp.left!=null)
            temp = temp.left;
        RedBlackNode<T> remove = remove(temp);
        temp.parent=tNode.parent;
        if (tNode.parent!=null) {
            if (tNode.parent.left==tNode)
                tNode.parent.left=temp;
            else
                tNode.parent.right=temp;
        }else
            this.root = temp;
        temp.left = tNode.left;
        temp.right = tNode.right;
    }
    //被删结点无子结点,且被删结点为黑色
    else if (!RedBlackNode.isRed(tNode) && RedBlackNode.isLeaf(tNode)) {
        RedBlackNode<T> parent = tNode.parent;
        RedBlackNode<T> sibling = null;     //兄弟结点
        if (parent.left == tNode)
            sibling = parent.right;
        else
            sibling = parent.left;

        if (sibling.isRed()) {
            //我们只需要将兄弟和父亲旋转,并把当前父亲和侄子结点染黑
            if (sibling == parent.left)
                rotateRight(parent);
            else
                rotateLeft(parent);
            //进行染色
            parent.setColor(RedBlackNode.BLACK);
            if (sibling.left != null)
                sibling.left.setColor(RedBlackNode.BLACK);
            else if (sibling.right != null)
                sibling.right.setColor(RedBlackNode.BLACK);
        } else {
            if (!RedBlackNode.isLeaf(sibling)) {
                //兄弟有子结点
                //兄弟是黑色的情况
                RedBlackNode<T> previousSibling = sibling;
                if (parent.left == sibling && !RedBlackNode.isRed(sibling.left) && RedBlackNode.isRed(sibling.right))
                    //兄弟有一个方向和父亲不方向相同的红色子结点,兄弟方向向父亲的左
                    sibling = rotateLeft(sibling);
                else if (parent.right == sibling && RedBlackNode.isRed(sibling.left) && !RedBlackNode.isRed(sibling.right))
                    //兄弟有一个方向和父亲不方向相同的红色子结点,兄弟方向向父亲的右
                    sibling = rotateRight(sibling);
                RedBlackNode<T> grandParent = parent.parent;
                RedBlackNode<T> previousParent = parent;
                if (parent.left == previousSibling) {
                    if (sibling.left!=null)
                        sibling.left.setColor(RedBlackNode.BLACK);
                    parent = rotateRight(parent);
                } else {
                    if (sibling.right!=null)
                        sibling.right.setColor(RedBlackNode.BLACK);
                    parent = rotateLeft(parent);
                }
                if (grandParent.left == previousParent)
                    grandParent.left = parent;
                else
                    grandParent.right = parent;
                previousParent.setColor(RedBlackNode.BLACK);
            } else if (!RedBlackNode.isRed(sibling.left) && !RedBlackNode.isRed(sibling.right)) {
                //兄弟没有红色子结点,这种情况比较麻烦,需要根据父亲的颜色确定
                if (RedBlackNode.isRed(parent)) {
                    //如果父亲的颜色为红色
                    //交换父亲和兄弟的颜色
                    parent.setColor(RedBlackNode.BLACK);
                    sibling.setColor(RedBlackNode.RED);
                } else {
                    //如果父亲的颜色为黑色
                    sibling.setColor(RedBlackNode.RED);
                    //修复工作
                    fixViolationBeforeRemove(tNode.parent);
                }
            }
        }
    }
}