红黑树分析

朱雀 2022-11-21 01:16 164阅读 0赞

# 二分查找法 #

我们如果要在一串数字之中去寻找一个书，比如1,2,3,4,5,6,7,8,9,10,11,12，如果我们需要寻找数字3，通过二分查找法也就是折半法，会先和6比较如果小于6则继续在1到6的范围内查找，如果大于6则通过右边进行查找，这就是二分查找法。二分查找法复杂度为O(log2n)，和二叉查找树一样。

通过二分查找法我们引出二叉查找树。

### 下面我们进行分析二叉查找树 ###

# ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3MDI2NjAz_size_16_color_FFFFFF_t_70][] #

可以把二叉树看作为树的倒影，而树根就是二叉树的根节点，子节点就是树的分支。

# 二叉查找树 #

二叉排序树（Binary Sort Tree），又称[二叉查找树][Link 1]（Binary Search Tree），亦称[二叉搜索树][Link 2]。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

定义：

1.  树的左边叶子节点必须小于父辈节点
2.  树的右边叶子节点必须大于父辈节点
3.  左边子树也必须都是二叉查找树

结合以下的图就是看起来约束的很好，不存在什么问题，左边是小于的数，右边是大于的数。查找元素也是效率快的，复杂为O(Log2n)，这种二叉查找树是属于平衡的，当有特殊的一种情况，如果二叉查找树不平衡的情况，时间复杂度就是O(n），退化为顺序查找了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3MDI2NjAz_size_16_color_FFFFFF_t_70 1][]

以下的图就很好看明白了

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3MDI2NjAz_size_16_color_FFFFFF_t_70 2][]

如果一直这样排序下去，那么查找的速度也就降为很低了，那么就会引出红黑树的概念了。

# 什么是红黑树？ #

1.  红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在[计算机][Link 3]科学中用到的一种[数据结构][Link 4]，典型的用途是实现[关联数组][Link 5]。 
2.  红黑树是一种特化的AVL树（[平衡二叉树][Link 6]），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。 
3.  它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。 
4.  jdk1.8中map和set都是用红黑树实现的。

# 红黑树的特征？ #

1.  节点是红色或黑色。 
2.  根节点是黑色。
3.  所有叶子都是黑色。（叶子是NUIL节点）
4.   每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）
5.  从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

特征的话不需要去死记硬背，通过图理解和文字结合好理解很多。

# 红黑树操作 #

红黑树的基本操作就是添加和删除，而为了保持红黑树的特性，则通过左旋和右旋进行保持。

### 左旋操作（如下图） ###

我们可以很清晰看到，当节点数大于不满足红黑树的规则后，会通过旋转和变换颜色来达到规则，比节点大的在右边，比节点小的在左边，当前的节点数已经超过了2个，以0011位节点进行左旋，由于根节点是黑色，然后把根节点改为黑色。

![20201029151852845.gif][]

### 右旋1 操作（如下两图） ###

首先我们添加0008号元素，添加的进来的元素都为红色，当0008,0010，0012都为红色时，也就是0008的父亲，还有叔叔都为红色，那么不满足红黑树规则，不可以有连续2个相连的红色节点，次数0010和0012将改变从黑色，0011转为红色，但是由于根节点必须为黑色，所以0011变为黑色。

![20201029152634588.gif][]

然后我们再次添加0007号选择，依次比较大小，添加在0008的左侧，当当前最低的叶子节点已经超过了2个节点，此时需要右旋来达到红黑树的平衡，那么就以0008为节点头进行右旋，在把0008变为黑色，此时才能达到红黑树的平衡。

![20201029152650533.gif][]

### 右旋2 操作（如下图） ###

插入元素0006号，插入进来的都为红色，当0006和0007都为红色，把0007和0003转为黑色，0005在转为红色，那么0005和0008都为红色，以0008为中心节点，进行右旋，达到红黑树特征且平衡。

![20201030171650213.gif][]

## ##

### 左右操作（如下图） ###

之前我们预添加了个0003号元素进去，为了进一步测试，在添加了0005号元素，刚好挂在0003号元素的右边，由于不满足红黑树的特征，先把0005号元素进行左转，在把0005号元素进行有右旋，再把0005号元素变为黑色，0007号变为红色元素，这样就满足了红黑树的特征，并且达到了树的平衡。

![20201030170120244.gif][]

### 右左操作（如下图） ###

我们添加0018号元素，在0022的左子节点，为了达到红黑树平衡规则，及颜色特征，先把0018进行右转，在以0018位中心进行左旋，最后把0018改为黑色，整个旋转过程就已经完成了。

![20201030172412347.gif][]

**提供一个红黑树的网站进行测试，大家可自行添加和删除元素进行测试**

**[https://www.cs.usfca.edu/~galles/visualization/RedBlack.html][https_www.cs.usfca.edu_galles_visualization_RedBlack.html]**

### 红黑树具体代码实现 ###

package redblacktree;
    
    /***
     *  节点颜色
     */
    public class NodeColor {
        public static String Red = "red";
        public static String Black = "black";
    }

package redblacktree;
    
    public class RedBlackTree {
        private static RedBlackTreeNode nil = new RedBlackTreeNode();
        private RedBlackTreeNode root = new RedBlackTreeNode();
        //构造空红黑树
        public RedBlackTree(){
            root = nil;
        }
        //创建结点
        public RedBlackTreeNode RB_NODE(int key){
            RedBlackTreeNode node = new RedBlackTreeNode(NodeColor.Red, key, nil, nil, nil);
            return node;
        }
        //判断是否为Nil结点
        public boolean IsNil(RedBlackTreeNode node){
            if( node == nil){
                return true;
            }else{
                return false;
            }
        }
        //获取根结点
        public RedBlackTreeNode getRoot() {
            return root;
        }
        //设置根结点
        public void setRoot(RedBlackTreeNode root) {
            this.root = root;
        }
        //插入结点
        public void RB_INSERT(RedBlackTree T, RedBlackTreeNode z){
            //临时变量结点y，存储临时结点，默认为Nil
            RedBlackTreeNode y = T.nil;
            //x初试为根结点
            RedBlackTreeNode x = T.getRoot();
            //循环二查找合适的插入点
            while( IsNil(x) == false ){
                //保存当前结点，作为结果的根结点
                y = x;
                if( z.getKey() < x.getKey() ){
                    //查找左子树
                    x = x.getLeft();
                }else{
                    //查找右子树
                    x = x.getRight();
                }
            }
            //临时结点y设置为插入点的父结点
            z.setParent(y);
    
            if(  IsNil(y) == true ){
                //空树时设置z为根结点
                T.setRoot(z);
            }else if( z.getKey() < y.getKey() ){
                //插入为左子树
                y.setLeft(z);
            }else{
                //插入为右子树
                y.setRight(z);
            }
            //将插入结点的左右子树设为Nil，颜色为红色，已经在构造时设置过，可以省略
            z.setLeft(T.nil);
            z.setRight(T.nil);
            z.setColor(NodeColor.Red);
            //插入调整
            RB_INSERT_FIXUP(T, z);
        }
        //插入调整
        public void RB_INSERT_FIXUP(RedBlackTree T, RedBlackTreeNode z){
            //当z的父结点为红色时，插入结点和父结点同为红色，需要调整
            while( z.getParent().getColor() == NodeColor.Red ){
                //插入结点的父结点是祖父节点的左子树
                if( z.getParent() == z.getParent().getParent().getLeft() ){
                    //y定义为叔叔结点
                    RedBlackTreeNode y = z.getParent().getParent().getRight();
                    //case1：如果叔叔结点为红色，上层父结点和叔叔结点设为黑色，祖父节点设为红色
                    if( y.getColor() == NodeColor.Red ){
                        z.getParent().setColor(NodeColor.Black);
                        y.setColor(NodeColor.Black);
                        z.getParent().getParent().setColor(NodeColor.Red);
                        //祖父结点设为z
                        z = z.getParent().getParent();
                    }
                    //case2：插入结点为父结点的右子树，（叔叔结点一定为黑色）,父结点设为z，对z左旋
                    else if( z == z.getParent().getRight() ){
                        //对父结点左旋
                        z = z.getParent();
                        LEFT_ROTATE(T, z);
                    }
                    //case3：插入结点为父结点的左子树，（叔叔结点一定为黑色），父结点设为黑色，祖父结点设为红色，对祖父结点右旋
                    z.getParent().setColor(NodeColor.Black);
                    z.getParent().getParent().setColor(NodeColor.Red);
                    RIGHT_ROTATE(T, z.getParent().getParent());
                }
                //插入结点的父结点是祖父节点的右子树，同理，方向交换
                else{
                    RedBlackTreeNode y = z.getParent().getParent().getLeft();
                    if( y.getColor() == NodeColor.Red ){
                        z.getParent().setColor(NodeColor.Black);
                        y.setColor(NodeColor.Black);
                        z.getParent().getParent().setColor(NodeColor.Red);
                        z = z.getParent().getParent();
                    }
                    else if( z == z.getParent().getLeft() ){
                        z = z.getParent();
                        RIGHT_ROTATE(T, z);
                    }
                    z.getParent().setColor(NodeColor.Black);
                    z.getParent().getParent().setColor(NodeColor.Red);
                    LEFT_ROTATE(T, z.getParent().getParent());
                }
            }
            T.getRoot().setColor(NodeColor.Black);
        }
        //删除结点子函数，把根结点为u的子树替换为根结点为v的子树
        public void RB_TRANSPLANT( RedBlackTree T, RedBlackTreeNode u, RedBlackTreeNode v){
            //u为根结点
            if( IsNil(u.getParent()) ){
                T.root = v;
            }
            //u为左子树
            else if( u == u.getParent().getLeft() ){
                u.getParent().setLeft(v);
            }
            //u为右子树
            else{
                u.getParent().setRight(v);
            }
            //父结点交换
            v.setParent(u.getParent());
        }
        //查找后继
        public RedBlackTreeNode TREE_MINIMUM(RedBlackTreeNode x){
            //不断查找左子树
            while( IsNil(x.getLeft()) == false ){
                x = x.getLeft();
            }
            return x;
        }
        //删除结点
        public void RB_DELETE(RedBlackTree T, RedBlackTreeNode z){
            //临时结点y保存即将删除的结点z信息
            RedBlackTreeNode y = z;
            //在结点删除或者移动前必须保存结点的颜色
            String yOriginColor = y.getColor();
            //临时结点x，用于记录y的位置
            RedBlackTreeNode x = null;
            //case1：z无左子树，直接将右子树置于z位置
            if( IsNil(z.getLeft()) == true ){
                x = z.getRight();
                RB_TRANSPLANT(T, z, z.getRight());
            }
            //case2：z无右子树，直接将左子树置于z位置
            else if( IsNil(z.getRight()) == true ){
                x = z.getLeft();
                RB_TRANSPLANT(T, z, z.getLeft());
            }
            //case3：z有左右子树
            else{
                //找到右子树中最小的结点，即z的后继
                y = TREE_MINIMUM(z.getRight());
                //删除的实际是y的位置的结点，要记录y的颜色
                yOriginColor = y.getColor();
                //y可能有右孩子，一定无左孩子，保存右孩子
                x = y.getRight();
                //若y为z的右孩子，直接相连
                if( y.getParent() == z ){
                    x.setParent(y);
                }
                //若不相连
                else{
                    RB_TRANSPLANT(T, y, y.getRight());
                    y.setRight(z.getRight());
                    y.getRight().setParent(y);
                }
                RB_TRANSPLANT(T, z, y);
                y.setLeft(z.getLeft());
                y.getLeft().setParent(y);
                y.setColor(z.getColor());
            }
            //删除结点为黑色时需要调整
            if( yOriginColor == NodeColor.Black ){
                RB_DELETE_FIXUP(T, x);
            }
        }
        //删除调整
        public void RB_DELETE_FIXUP(RedBlackTree T, RedBlackTreeNode x){
            //临时结点
            RedBlackTreeNode w = null;
            //非根结点且为黑色
            while( x != T.getRoot() && x.getColor() == NodeColor.Black ){
                //x为父结点左孩子
                if( x == x.getParent().getLeft() ){
                    //w为兄弟结点
                    w = x.getParent().getRight();
                    //case1：w兄弟结点为红色
                    if( w.getColor() == NodeColor.Red ){
                        //w设为黑色
                        w.setColor(  NodeColor.Black );
                        //被删结点的父结点设为黑色
                        x.getParent().setColor( NodeColor.Red );
                        //对x的父结点左旋
                        LEFT_ROTATE(T, x.getParent());
                        //更新x的兄弟结点
                        w = x.getParent().getRight();
                    }
                    //case2：w兄弟结点和两个孩子结点都为黑
                    if( w.getLeft().getColor() == NodeColor.Black && w.getRight().getColor() == NodeColor.Black ){
                        //w设为黑色
                        w.setColor(NodeColor.Red);
                        //重设x为x的父结点
                        x = x.getParent();
                    }
                    //case3：w兄弟结点为黑，w的左孩子为红，右孩子为黑
                    else if( w.getRight().getColor() == NodeColor.Black ){
                        //w的左孩子设为黑
                        w.getLeft().setColor(NodeColor.Black);
                        //w设为红
                        w.setColor(NodeColor.Red);
                        //右旋
                        RIGHT_ROTATE(T, w);
                        //更新w
                        w = x.getParent().getRight();
                    }
                    //case4：w兄弟结点为黑，w的右孩子为红
                    w.setColor(x.getParent().getColor());
                    x.getParent().setColor(NodeColor.Black);
                    w.getRight().setColor(NodeColor.Black);
                    LEFT_ROTATE(T, x.getParent());
                    x = T.getRoot();
                }
                //x为父结点右孩子
                else{
                    w = x.getParent().getLeft();
                    if( w.getColor() == NodeColor.Red ){
                        w.setColor(  NodeColor.Black );
                        x.getParent().setColor( NodeColor.Red );
                        RIGHT_ROTATE(T, x.getParent());
                        w = x.getParent().getLeft();
                    }
                    if( w.getRight().getColor() == NodeColor.Black && w.getLeft().getColor() == NodeColor.Black ){
                        w.setColor(NodeColor.Red);
                        x = x.getParent();
                    }
                    else if( w.getLeft().getColor() == NodeColor.Black ){
                        w.getRight().setColor(NodeColor.Black);
                        w.setColor(NodeColor.Red);
                        LEFT_ROTATE(T, w);
                        w = x.getParent().getLeft();
                    }
                    w.setColor(x.getParent().getColor());
                    x.getParent().setColor(NodeColor.Black);
                    w.getLeft().setColor(NodeColor.Black);
                    RIGHT_ROTATE(T, x.getParent());
                    x = T.getRoot();
                }
            }
            x.setColor(NodeColor.Black);
        }
        //左旋
        public void LEFT_ROTATE(RedBlackTree T, RedBlackTreeNode x){
            //左旋结点右子树不能为空
            if ( IsNil(x.getRight()) == true )
                return;
            //定义y结点
            RedBlackTreeNode y = x.getRight();
            //y左子树 -> x右子树
            x.setRight(y.getLeft());
            //x -> y左子树父结点
            y.getLeft().setParent(x);
            //x父结点 -> y父结点
            y.setParent(x.getParent());
            //y -> x父结点左/右子树或根结点
            if( IsNil(x.getParent()) == true){
                //x为根结点，y设为根结点
                T.setRoot(y);
            }else if( x.getParent().getLeft() == x){
                //x为左子树，y设为左子树
                x.getParent().setLeft(y);
            }else{
                //x为右子树，y设为右子树
                x.getParent().setRight(y);
            }
            //x -> y左子树
            y.setLeft(x);
            //y -> x父结点
            x.setParent(y);
        }
        //右旋
        public void RIGHT_ROTATE(RedBlackTree T, RedBlackTreeNode x){
            //右旋结点父结点不能为空
            if ( IsNil(x.getParent()) == true )
                return;
            //定义y结点
            RedBlackTreeNode y = x.getParent();
            //x右子树 -> y左子树
            y.setLeft(x.getRight());
            //y -> x右子树父结点
            x.getRight().setParent(y);
            //y父结点 -> x父结点
            x.setParent(y.getParent());
            //x -> y父结点左/右子树或根结点
            if( IsNil(y.getParent()) == true){
                //y为根结点，x设为根结点
                T.setRoot(x);
            }else if( y.getParent().getLeft() == y){
                //y为左子树，x设为左子树
                y.getParent().setLeft(x);
            }else{
                //y为右子树，x设为右子树
                y.getParent().setRight(x);
            }
            //y -> x右子树
            x.setRight(y);
            //x -> y父结点
            y.setParent(x);
        }
        //前序遍历
        public void preorder(RedBlackTreeNode t){
            if(IsNil(t) == false){
                System.out.println(t.getKey());
                preorder(t.getLeft());
                preorder(t.getRight());
            }
        }
        //中序遍历
        public void midorder(RedBlackTreeNode t){
            if(IsNil(t) == false){
                midorder(t.getLeft());
                System.out.println(t.getKey());
                midorder(t.getRight());
            }
        }
        //后序遍历
        public void postorder(RedBlackTreeNode t){
            if(IsNil(t) == false){
                postorder(t.getLeft());
                postorder(t.getRight());
                System.out.println(t.getKey());
            }
        }
    }

package redblacktree;
    
    /**
     * 红黑数节点
     */
    public class RedBlackTreeNode {
        private String color;
        private int key;
        private RedBlackTreeNode left;
        private RedBlackTreeNode right;
        private RedBlackTreeNode parent;
        //构造Nil结点
        public RedBlackTreeNode(){
            this.color = NodeColor.Black;
            this.key = 0;
            this.left = null;
            this.right = null;
            this.parent = null;
        }
        //构造结点
        public RedBlackTreeNode(String color, int key, RedBlackTreeNode left, RedBlackTreeNode right, RedBlackTreeNode parent){
            this.color = color;
            this.key = key;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }
        //获取颜色
        public String getColor() {
            return color;
        }
        //设置颜色
        public void setColor(String color) {
            this.color = color;
        }
        //获取值
        public int getKey() {
            return key;
        }
        //设置值
        public void setKey(int key) {
            this.key = key;
        }
        //获取左子树
        public RedBlackTreeNode getLeft() {
            return left;
        }
        //设置左子树
        public void setLeft(RedBlackTreeNode left) {
            this.left = left;
        }
        //获取右子树
        public RedBlackTreeNode getRight() {
            return right;
        }
        //设置右子树
        public void setRight(RedBlackTreeNode right) {
            this.right = right;
        }
        //获取父结点
        public RedBlackTreeNode getParent() {
            return parent;
        }
        //设置父结点
        public void setParent(RedBlackTreeNode parent) {
            this.parent = parent;
        }
    }

package redblacktree;
    
    public class Test {
        public static void main(String[] args) {
            RedBlackTree T = new RedBlackTree();
            RedBlackTreeNode node1 = T.RB_NODE(10);
            T.RB_INSERT(T, node1);
            RedBlackTreeNode node2 = T.RB_NODE(20);
            T.RB_INSERT(T, node2);
            RedBlackTreeNode node3 = T.RB_NODE(30);
            T.RB_INSERT(T, node3);
            T.preorder(T.getRoot());
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3MDI2NjAz_size_16_color_FFFFFF_t_70 3][]

后续如若有补充，在 继续更新此篇内容........

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3MDI2NjAz_size_16_color_FFFFFF_t_70]: /images/20221120/631bae910f3e484da18a7af4f04f62cb.png
[Link 1]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91/7077965
[Link 2]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/7077855
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3MDI2NjAz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201030164832184.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3MDI2NjAz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3MDI2NjAz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201030165228568.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3MDI2NjAz,size_16,color_FFFFFF,t_70
[Link 3]: https://baike.baidu.com/item/%E8%AE%A1%E7%AE%97%E6%9C%BA
[Link 4]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1450
[Link 5]: https://baike.baidu.com/item/%E5%85%B3%E8%81%94%E6%95%B0%E7%BB%84/3317025
[Link 6]: https://baike.baidu.com/item/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91/10421057
[20201029151852845.gif]: https://img-blog.csdnimg.cn/20201029151852845.gif
[20201029152634588.gif]: https://img-blog.csdnimg.cn/20201029152634588.gif
[20201029152650533.gif]: https://img-blog.csdnimg.cn/20201029152650533.gif
[20201030171650213.gif]: https://img-blog.csdnimg.cn/20201030171650213.gif
[20201030170120244.gif]: https://img-blog.csdnimg.cn/20201030170120244.gif
[20201030172412347.gif]: https://img-blog.csdnimg.cn/20201030172412347.gif
[https_www.cs.usfca.edu_galles_visualization_RedBlack.html]: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3MDI2NjAz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201209091600323.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3MDI2NjAz,size_16,color_FFFFFF,t_70