侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

数据结构--红黑树

林贤钦
2020-06-28 / 0 评论 / 10 点赞 / 530 阅读 / 0 字
温馨提示:
本文最后更新于 2021-01-29,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

红黑树

关于二叉搜索树,二叉平衡树的这些知识点,本文没有涉及,在我博客的另外几篇《树结构基础部分平衡二叉树》有详细讲,本文主要讲红黑色的性质,根据红黑树的性质,以图文的形式讲述如何通过左旋,右旋,以及变色来维持红黑树的性质,在文章的最后提供了两种红黑树的代码实现,都是笔者自己改的,一种是比较简单理解的,以递归的形式,另一种阅读起来可能吃力点,这个笔者根据HashMap的源码进而改成自己想要的结果,不过笔者都做好了注释,也不难。

一、定义

  • 红黑树是一种特定类型的二叉树,它是在计算机科学中用来组织数据比如数字的块的一种结构。若一棵二叉查找树是红黑树,则它的任一子树必为红黑树.
  • 红黑树是一种平衡二叉查找树的变体,它的左右子树高差有可能大于 1,所以红黑树不是严格意义上的平衡二叉树(AVL),但 对之进行平衡的代价较低, 其平均统计性能要强于 AVL 。
  • 由于每一颗红黑树都是一颗二叉排序树,因此,在对红黑树进行查找时,可以采用运用于普通二叉排序树上的查找算法,在查找过程中不需要颜色信息。

二、性质

红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:

【1】性质1. 节点是红色或黑色。

【2】性质2. 根节点是黑色。

【3】性质3. 每个叶节点是黑色的。

【4】性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

【5】性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点,俗称黑高。

从五大性质可推出:

  • 新加入到红黑树的节点一定为红色节点
  • 如果一个节点存在黑子节点,那么该节点肯定右两个子节点

无论是变色还是左旋右旋,都是为了保证满足上面五个性质

三、左旋过程

以某个结点作为支点(旋转结点),其右子结点变为旋转结点的父结点,右子结点的左子结点变为旋转结点的右子结点,左子结点保持不变。

说明:这个是例子,球的上面的线代表父结点,左右线代表左右结点,虚线代表左旋过程,粉球代表旋转前子树的根结点,黄球代表旋转后的根结点,白球代表根结点的父结点(可能为null)

  • 步骤一:将当前节点的右子节点的左子节点赋值 给了当前的右子节点,并且更新当前节点的右子节点的左子节点的父节点为 当前节点

    图中2的右节点变成了3,3的父节点变成了2

  • 步骤二:将当前节点的父节点(不为空时)指向当前节点的右子节点,更新当前节点的右子节点的父节点为当前节点的父节点

    图中2的父节点的子节点指向了4,4的父节点指向了2的父节点

  • 步骤三:将当前节点的右子节点的左子节点指向当前节点,更新结点当前节点的父节点为当前节点的右子节点

  • 图中4的左子节点指向了2,2的父节点指向了4

四、右旋过程

以某个结点作为支点(旋转结点),其左子结点变为旋转结点的父结点,左子结点的右子结点变为旋转结点的左子结点,右子结点保持不变

  • 步骤一:将当前节点的右子节点的左子节点 赋值 给了 当前节点的右子节点,并且更新原当前节点的左节点的右子节点的父节点为 当前节点

  • 图中5的父节点变成了6,6的左子节点变成了5

  • 步骤二:将当前节点的父节点(不为空时)指向原当前节点的左节点,更新原当前节点的左节点的父节点为当前节点的父节点

  • 图中4的父节点变成了6的父节点,6的父节点的孩子节点从6变成了4

  • 步骤三:将原当前节点的左子节点的右子节点指向当前节点,更新当前节点的父节点为原当前节点的左子节点

  • 图中4的右子节点指向了6,6的父节点指向了4

五、红黑树插入节点情景分析

情景1:红黑树为空树

最简单的一种情景,直接把插入结点作为根结点就行

处理:根据红黑树性质2:根节点是黑色。还需要把插入结点设为黑色。

情景2:插入结点的Key已存在

处理:更新当前节点的值,为插入节点的值

情景3:插入结点的父结点为黑结点

由于插入的结点是红色的,当插入结点的黑色时,并不会影响红黑树的平衡

处理:直接插入即可,无需做自平衡。

情景4:插入节点的父节点为红色

再次回想下红黑树的性质2:根结点是黑色。如果插入节点的父结点为红结点,那么该父结点不可能为根结点,所以插入结点总是存在祖父结点。

这一点很关键,因为后续的旋转操作肯定需要祖父结点的参与。在父节点为红色的时候,需要考虑以下情况

  • 4.1:叔叔结点存在并且为红结点

    处理:将父节点和叔叔节点变成黑色,爷爷变成红色,再以爷爷节点为当前节点进行操作

  • 4.2:叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的左子结点

    • 4.2.1:新插入节点,为其父节点的左子节点(LL红色情况)

      处理:将父节点改成黑色,爷爷节点改成红色,然后对爷爷节点进行右旋操作

    • 4.2.2:新插入节点,为其父节点的右子节点(LR红色情况)

      处理: 对父节点进行左旋,然后父节点为当前节点处理LL红色情况

  • 4.3:叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的右子结点

    • 4.3.1:新插入节点,为其父节点的右子节点(RR红色情况)

      处理:将父节点变成黑色,爷爷节点变成红色,然后对爷爷节点进行左旋操作

    • 4.3.2:新插入节点,为其父节点的左子节点(RL红色情况)

      处理:对父节点进行右旋操作,然后父节点也当前节点处理RR红色情况

六、红黑树插入节点图文过程

依次插入数据{50,25,75,15,30,28,27,26,,100,125,40,35},可展示除重复节点外的所有情况,详情在下文

红黑树为空树或父节点为黑色

插入数据{50,25,75}

情景1:红黑树为空树

最简单的一种情景,直接把插入结点作为根结点就行

注意:根据红黑树性质2:根节点是黑色。还需要把插入结点设为黑色。

情景3:插入结点的父结点为黑结点

由于插入的结点是红色的,当插入结点的黑色时,并不会影响红黑树的平衡,直接插入即可,无需做自平衡。

叔叔结点存在并且为红结点

继续插入数据{15}

4.1:父节点为红色且叔叔结点存在并且为红结点

处理:将父节点和叔叔结点变成黑色,将爷爷节点变成红色,再以爷爷节点为当前节点进行下轮操作

LL红色情况

继续插入数据{30,28,27}

插入情景4.2:父节点为红色且叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的左子结点

4.2.1:新插入节点,为其父节点的左子节点(LL红色情况)

处理:将父节点改成黑色,爷爷节点改成红色,然后对爷爷节点进行右旋操作

LR红色情况

继续插入数据{26}

插入情景4.2:父节点为红色且叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的左子结点

4.2.2:新插入节点,为其父节点的右子节点(LR红色情况)

对父节点进行左旋操作,将父节点设置为当前节点,然后按照LL红色情况处理

插入情景4.2:父节点为红色且叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的左子结点

4.2.1:新插入节点,为其父节点的左子节点(LL红色情况)

处理:将父节点改成黑色,爷爷节点改成红色,然后对爷爷节点进行右旋操作

RR红色情况

继续插入数据{100,125}

插入情景4.2:父节点为红色且叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的左子结点

4.3.1:新插入节点,为其父节点的右子节点(RR红色情况)

处理:将父节点改成黑色,爷爷节点改成红色,然后以爷爷节点进行左旋操作

RL红色情况

继续插入数据{40,35}

插入情景4.2:父节点为红色且叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的左子结点

4.3.2:新插入节点,为其父节点的右子节点(RL红色情况)

处理:对父节点进行右旋操作,然后将父节点设置为当前节点,得到RR红色情况,在根据RR情况进行操作

七、红黑树添加节点

自己改的红黑树,仅供参考~

简单递归版代码详情

红黑树的基本信息(简单版)

public class RBTree<K extends Comparable<K>,V>{
    //定义颜色常量
    private static final boolean RED = true;
    private static final boolean BLACK =  false;
    //红黑树树根
    private RBNode root;

    public RBNode getRoot(){
        return root;
    }
   /**
     * 红黑树
     * @param <K> key
     * @param <V> value
     */
    static class RBNode<K extends Comparable<K>,V>{
        //颜色
        private boolean color;
        //左子节点
        private RBNode left;
        //右子节点
        private RBNode right;
        //父节点
        private RBNode parent;
        //key
        private K key;
        //value
        private V value;  
        public RBNode() {}
    }    
}

左旋过程

private void leftRotate(RBNode node){
    RBNode right = node.right;
    //将当前节点node的右节点right的左节点 与 当前节点挂父子关系,替代node的右节点
    node.right=right.left;
    if (right!=null){
        right.left.parent=node;
    }
    //将node的父节点与node的右节点挂父子关系
    if (node.parent!=null) {
        if (node == node.parent.left) {
            node.parent.left = right;
        } else {
            node.parent.right = right;
        }
        right.parent=node.parent;
    }
    //将node和right互换身份
    node.parent=right;
    right.left=node;
}

右旋过程

private void rightRotate(RBNode node){
    RBNode left = node.left;
    //将left的右子树和node挂父子关系,代替node和left的位置
    node.left=left.right;
    if (left.right!=null){
        left.right.parent=node;
    }
    //将node的父节点挂到left上面
    left.parent=node.parent;
    if (node.parent!=null){
        if (node==node.parent.left){
            node.parent.left=left;
        }else {
            node.parent.right=left;
        }
    }
    //更新node和left的关系
    node.parent=left;
    left.right=node;
}

插入后修复红黑树平衡的方法

  • |---情景1:红黑树为空树
  • |---情景2:插入节点的key已经存在
  • |---情景3:插入节点的父节点为黑色
  • 情景4 需要咱们去处理
  • |---情景4:插入节点的父节点为红色
  • |---情景4.1:叔叔节点存在,并且为红色(父-叔 双红)
  • |---情景4.2:叔叔节点不存在,或者为黑色,父节点为爷爷节点的左子树
  • |---情景4.2.1:插入节点为其父节点的左子节点(LL情况)
  • |---情景4.2.2:插入节点为其父节点的右子节点(LR情况)
  • |---情景4.3:叔叔节点不存在,或者为黑色,父节点为爷爷节点的右子树
  • |---情景4.3.1:插入节点为其父节点的右子节点(RR情况)
  • |---情景4.3.2:插入节点为其父节点的左子节点(RL情况)

情景1 ,2 在添加节点过程都已经处理,而情景3是不需要处理的,

所以,这个方法是处理情景4的六种情况,有个必要条件就是父节点不为空,且父节点为红色,而父节点为红色,那必定有爷爷节点

private void insertFitUp(RBNode node) {
    //获取当前节点的父节点,前面判空,这里不用判空
    RBNode parent = node.parent;
    //必要条件,父节点不为空,且父节点为红色
    if (parent!=null&&parent.color==RED){
        //获取爷爷节点
        RBNode gParent= parent.parent;
        //分两种情况,父亲节点是爷爷节点的左节点还是右节点
        if (parent==gParent.left){//父亲节点是爷爷节点的左节点
            RBNode uncle = parent.right;
            //第一种情况,叔叔节点不为空,且叔叔节点为红色
            if (uncle!=null&&uncle.color==RED){
                //将父节点,叔叔节点变成黑色,爷爷节点变成红色,然后以爷爷节点为当前节点递归
                uncle.color=BLACK;
                parent.color=BLACK;
                gParent.color=RED;
                insertFitUp(gParent);
                return;
            }else {//叔叔节点为空,或者叔叔节点为黑色
                //这里分两种情况,一是当前节点是父节点的左节点,二是当前节点是父节点的右节点
                if (node==parent.left){//ll情况
                    //将父节点变成黑色,爷爷几点变成红色,然后右旋爷爷节点
                    parent.color=BLACK;
                    gParent.color=RED;
                    //TODO: 右旋
                    rightRotate(gParent);
                }else {//lr情况
                    //左旋父节点
                    leftRotate(parent);
                    //然后以父节点进行递归
                    insertFitUp(parent);
                    return;
                }
            }
        }else {//父亲节点是爷爷节点的右节点
            RBNode uncle = gParent.right;
            if (uncle!=null&&uncle.color==RED){
                parent.color=BLACK;
                uncle.color=BLACK;
                gParent.color=RED;
                insertFitUp(gParent);
            }else {
                if (node==parent.left){
                    //RL情况,右旋父节点
                    rightRotate(parent);
                    insertFitUp(parent);
                    return;
                }else {
                    parent.color=BLACK;
                    gParent.color=RED;
                    leftRotate(gParent);
                }
            }
        }
    }
    this.root.color=BLACK;
}

添加节点的方法

public void insert(K key,V value){
    //创建节点的基本信息
    RBNode node = new RBNode();
    node.key=key;
    node.value=value;
    //新节点一定为红色
    node.color=RED;
    insert(node);
}
private void insert(RBNode node){
    //如果节点为空,直接return
    if (node==null){
        return;
    }
    if (this.root==null){
        //根节点为null,将节点设置为黑色,直接添加在根节点上,然后直接return
        this.root=node;
        this.root.color=BLACK;
        return;
    }
    RBNode parent =null;
    RBNode x = this.root;
    while (x!=null){
        parent=x;
        int cmp = node.key.compareTo(parent.key);
        if (cmp<0){
            //比parent小
            x=x.left;
        }else if (cmp==0){
            //找到key相等,改变值,然后直接return
            x.value=node.value;
            return;
        }else {
            x=x.right;
        }
    }
    //找到了最后结果,x为要插入的点,parent为x的父节点,设置x和parent的关系
    node.parent=parent;
    if (node.key.compareTo(parent.key)<0){
        parent.left=node;
    }else {
        parent.right=node;
    }
    //最后就是维护红黑树。
    insertFitUp(node);
}

非递归版代码详情

1、红黑树基本信息

public class RBTree<K,V> {
    private Node<K,V> root;
    public Node<K, V> getRoot() {
        if (root==null){
            return null;
        }
        return root.root();
    }
    static class Node<K,V>{
        Node<K,V> parent;//父节点
        Node<K,V> left;//左节点
        Node<K,V> right;//右节点
        boolean red;//颜色,true红色,false黑色
        K key; //建
        V value; // 值
        int hash; // hash,比较用

        Node(K key,V value){
            this.key=key;
            this.value=value;
            this.hash=hashCode();
        }
        @Override
        public final int hashCode() {
            return Objects.hashCode(key);
        }
        @Override
        public final String toString() { return key + "=" + value+",hash="+hash; }
        //获取根节点
        Node<K,V> root(){
            for (Node<K,V> r=this,p;;){
                if ((p=r.parent)==null)
                    return r;
                r=p;
            }
        }
    }
}

2、左旋过程

//左旋
private <K,V>Node<K,V> rotateLeft(Node<K,V> root,Node<K,V>p){
    //定义当前p节点的右节点r,右节点r的左节点rl,当前节点p的父节点pp
    Node<K,V>r,rl,pp;
    //->1.如果当前节点p不为null;2.r=p.right 3.p节点的右节点r不为空!;
    if (p!=null&&(r=p.right)!=null){
        //1.rl=r.left;2.当前节点的右节点指向r的左节点p.right=r.left;3.rl!=null如果不为空,走里面
        if ((rl=p.right=r.left)!=null)
            //不为空就将rl的父节点指向p
            rl.parent=p;
        //1.pp=r.parent;2.r.parent=p.parent3.如果pp为空,走里面
        if ((pp=r.parent=p.parent)==null)
            //如果pp为空,根节点指向r,2.颜色定义为false,也就是黑色
            (root=r).red=false;
            //如果p是pp的左节点,pp的左节点指向r
        else if (pp.left==p)
            pp.left=r;
            //如果p是pp的右节点,pp的右节点指向r
        else
            pp.right=r;
        //r的左节点指向p
        r.left=p;
        //p的父节点指向r
        p.parent=r;
    }
    return root;
}

3、右旋过程

//右旋
private  <K,V>Node<K,V> rotateRight(Node<K,V>root,Node<K,V>p){
    Node<K,V> l,lr,pp;
    if (p!=null&&(l=p.left)!=null){
        if ((lr=p.left=l.right)!=null)
            lr.parent=p;
        if ((pp=l.parent=p.parent)==null)
            (root=l).red=false;
        else if (pp.left==p)
            pp.left=l;
        else
            pp.right=l;
        l.right=p;
        p.parent=l;
    }
    return root;
}

4、维护红黑树过程

private <K,V>Node<K,V> balanceInsertion(Node<K,V>root,Node<K,V>x){
    //新加入节点都是红色
    x.red=true;
    // 这些变量名不是作者随便定义的都是有意义的。
    // xp:x parent,代表x的父节点。
    // xpp:x parent parent,代表x的祖父节点
    // xppl:x parent parent left,代表x的祖父的左节点。
    // xppr:x parent parent right,代表x的祖父的右节点。
    for (Node<K,V>xp,xpp,xppl,xppr;;){
        //如果x的父节点为null,说明只有一个节点,该节点为根节点,根节点为黑色,red=false;
        if ((xp=x.parent)==null){
            x.red=false;
            return x;
        }else if (!xp.red||(xpp=xp.parent)==null){
            // 如果父节点是黑色,红色的x节点可以直接添加到黑色节点后面,返回根就行了不需要任何多余的操作。
            return root;
        }
        // 判断如果父节点是否是祖父节点的左节点
        if (xp==(xppl=xpp.left)){
            //如果叔叔节点不为空,且叔叔节点为红色,父节点,叔叔节点变黑,爷爷变红,令爷爷节点为当前节点,进入下轮for循环
            if ((xppr=xpp.right)!=null&&xppr.red){
                xp.red=false;
                xppr.red=false;
                xpp.red=true;
                x=xpp;
            }else {
                //进入这个else的条件就是,叔叔节点为空,或者叔叔节点为黑色,但是这里都不需要操作叔叔节点
                //这里需要判断是ll情况还是lr情况
                if (x==xp.right){
                    //lr情况,将父节点左旋,再以父节点作为当前节点往下走
                    root=rotateLeft(root,x=xp);
                    //更新关系
                    xpp=(xp=x.parent)==null?null:xp.parent;
                }
                //ll情况,针对本身就是xpp左->xp左->x的结构或者由于上面的旋转造成的这种结构进行一次旋转。
                //将父节点变成黑色,爷爷节点变成红色,然后以爷爷节点右旋,这样父节点就变成了根节点,保持平衡
                if (xp!=null){
                    xp.red=false;
                    if (xpp!=null){
                        xpp.red=true;
                        root=rotateRight(root,xpp);
                    }
                }
            }
        }else {
            //爷爷几点不为空,且叔叔节点为红色
            if (xpp!=null&&xppl.red){
                xp.red=false;
                xppl.red=false;
                xpp.red=true;
                x=xpp;
            }else {
                //rl情况
                if (x==xp.left){
                    root = rotateRight(root, x = xp);
                    xpp=(xp=x.parent)==null?null:xp.parent;
                }
                if (xp!=null){
                    xp.red=false;
                    if (xpp!=null){
                        xpp.red=true;
                        root=rotateLeft(root,xpp);
                    }
                }
            }
        }
    }
}

5、添加节点方法

public Node<K,V> putTreeVal(K key,V value){
    Node<K,V> node = new Node<>(key,value);
    if (node==null){
        return null;
    }
    if ((root=getRoot())==null){
        root=node;
        root.red=false;
        return root;
    }
    return putTreeVal(root, node);
}
private<K,V>Node<K,V> putTreeVal(Node<K,V>root,Node<K,V>x){
    for (Node<K,V>p=root;;){
        // dir:directory,比较添加项与当前树中访问节点的hash值判断加入项的路径,-1为左子树,+1为右子树。
        int dir;
        K pk,xk;
        if (p.hash>x.hash){
            dir=-1;
        } else {
            dir = 1;
        }
        //键相等,更新p节点为传入节点
        if ((pk=p.key)==(xk=x.key)||(xk!=null&&xk.equals(pk))){
            return p=x;
        }
        // xp:x parent。
        Node<K, V> xp = p;
        //找到符合x的节点位置,p就是x要插入的位置
        if ((p=(dir<=0)?p.left:p.right)==null){
            if (dir<=0) {
                xp.left = x;
            } else {
                xp.right = x;
            }
             x.parent=xp;
            // 维护添加后红黑树的红黑结构。
            return balanceInsertion(root,x);
        }
    }
}

6、中序遍历打印红黑树

public class RBTree<K,V> {
    //TODO 中序遍历
    public void infixOrder(){
        if ((this.root=getRoot())!=null){
            this.root.infixOrder();
        }else{
            System.out.println("红黑树为空,无法遍历");
        }
    }
    static class Node<K,V>{
        //中序打印
        void infixOrder(){
            //递归向左子树前序遍历
            if (this.left!=null){
                this.left.infixOrder();
            }
            //输出父节点
            System.out.println(this);
            //递归向右子树前序遍历
            if (this.right!=null){
                this.right.infixOrder();
            }
        }
    }
}

7、打印测试结果

class Test{
    public static void main(String[] args) {
        RBTree rbTree = new RBTree();
        rbTree.putTreeVal("50","it小林");
        rbTree.putTreeVal("25","it小林");
        rbTree.putTreeVal("75","it小林");
        rbTree.putTreeVal("15","it小林");
        rbTree.putTreeVal("30","it小林");
        rbTree.putTreeVal("28","it小林");
        rbTree.putTreeVal("27","it小林");
        RBTree.Node root = rbTree.getRoot();
        rbTree.infixOrder();
    }
}

打印结果:颜色对应是正确的

key=15,value=it小林,hash=1572,黑色
key=25,value=it小林,hash=1603,红色
key=27,value=it小林,hash=1605,红色
key=28,value=it小林,hash=1606,黑色
key=30,value=it小林,hash=1629,红色
key=50,value=it小林,hash=1691,黑色
key=75,value=it小林,hash=1758,黑色

10

评论区