二叉平衡树之红黑树

迈不过友情╰ 2024-03-16 20:00 67阅读 0赞

**目录**

1.概念

2.性质

3.节点的定义

4.插入

1.按照二叉搜索树规则插入结点

2.调整颜色

1.uncle存在且为红色

2.uncle不存在或者为黑 cur为

3.根节点改为黑色

5.验证

6.比较

7.应用

--------------------

## 1.概念 ##

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

![576f030990034f6888aed1b43557bc61.png][]

## 2.性质 ##

1.每个结点不是红色就是黑色

2.根节点是黑色

3.如果一个结点是红色,则他的两个孩子结点是黑色(没有两个相邻的红色结点)

4.每个结点,从该结点到其所有后代的叶子结点的路径中,含有的黑色节点个数相同

5.每个叶子结点都是黑色

为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

最短:全黑,最长:红黑交替==>满足条件

## 3.节点的定义 ##

static class RBTreeNode{
        public RBTreeNode left;
        public RBTreeNode right;
        public RBTreeNode parent;
        public int val;
        public COLOR color;
    
        public RBTreeNode(int val){
            this.val=val;
            //新增节点不能是黑色,要保证每条路上的黑色节点个数相同,会有问题:
            //1.要新增节点
            this.color=COLOR.RED;
        }
    
    }

## 4.插入 ##

### 1.按照二叉搜索树规则插入结点 ###

1.创建结点

2.为空

3.遍历到当年结点为null

4.插入结点

public boolean insert(int val){
            rbTreeNode node=new rbTreeNode(val);
            if(root==null){
                root=node;
                root.color=COLOR.BLACK;
                return true;
            }
            rbTreeNode parent=null;
            rbTreeNode cur=root;
            while(cur!=null){
                if(cur.val<val){
                    parent=cur;
                    cur=cur.right;
                }else if(cur.val==val){
                    return false;
                }else{
                    parent=cur;
                    cur=cur.left;
                }
            }
            if(parent.val<val){
                parent.right=node;
               
            }else{
                parent.left=node;
            }
            node.parent=parent;
            cur=node;
        }

### 2.调整颜色 ###

以parent == grand.left为例(cur,parent为红色),另一个刚好相反

g为黑色(可能为根节点,根节点为黑色),p为红色(两个连续的红色才需要调整),cur为红色(新插入的都是红色),以uncle的情况分类

#### 1.uncle存在且为红色 ####

p,u变为黑色 g变为红色 继续向上遍历

#### 2.uncle不存在或者为黑 cur为 ####

1.cur==parent.left -->右旋,p黑,g红

2.cur==parent.right -->左旋,cur和p交换,变为第一种

#### 3.根节点改为黑色 ####

情况1:cur为红，p为红，g为黑，u存在且为红

![8e99452233024a38b743bf8820fb4c47.png][]

把parent和uncle改为红色,grad改为黑色

思路: 不能有两个连着的红色结点,把p和u改为黑色,如果不把g改为红色就违背黑色节点个数相同的的性质

情况2:g为黑,u为黑,p为红,cur为红,cur为p的左孩子

![52d7ff20678440b39d1c2e02029b5ed9.png][]

情况3:g为黑,u为黑,p为红,cur为红,cur为p的右孩子

p做左单旋转,变成情况2

public boolean insert(int val){
           RBTNode node=new RBTNode(val);
           if(root==null){
               root=node;
               root.color=COLOR.BLACK;
               return true;
           }
    
           RBTNode parent=null;
           RBTNode cur=root;
           while(cur!=null){
               if(cur.val<val){
                   parent=cur;
                   cur=cur.right;
               }else if(cur.val==val){
                   return false;
               }else{
                   parent=cur;
                   cur=cur.left;
               }
           }
           if(parent.val<val){
               parent.right=node;
           }else{
               parent.left=node;
           }
           node.parent=parent;
           cur=node;
    
    
           //调整颜色
            while (parent!=null && parent.color==COLOR.RED){
                RBTNode grand=parent.parent;
                if(parent==grand.left){
                    RBTNode uncle=grand.right;
                    if(uncle!=null  && uncle.color==COLOR.RED){
                        //cur,p,u红,g黑
                        //方法:p.u黑,g,继续向上遍历
                        parent.color=COLOR.BLACK;
                        uncle.color=COLOR.BLACK;
                        grand.color=COLOR.RED;
                        cur=grand;
                        parent=cur.parent;
                    }else{
                        if(cur==parent.right){
                            rotateLeft(parent);
                            RBTNode tmp=parent;
                            parent=cur;
                            cur=tmp;
                        }
                        rotateRight(grand);
                        parent.color=COLOR.BLACK;
                        grand.color=COLOR.RED;
                    }
                }else{
                    RBTNode uncle=grand.left;
                    if(uncle!=null && uncle.color==COLOR.RED){
                        parent.color=COLOR.BLACK;
                        uncle.color=COLOR.BLACK;
                        grand.color=COLOR.RED;
                        cur=grand;
                        parent=cur.parent;
                    }else{
                        if(cur==parent.left){
                            rotateRight(parent);
                            RBTNode tmp=parent;
                            parent=cur;
                            cur=tmp;
                        }
                        rotateLeft(grand);
                        grand.color=COLOR.RED;
                        parent.color=COLOR.BLACK;
                    }
                }
            }
            root.color=COLOR.BLACK;
            return true;
        }
    
        private void rotateRight(RBTNode parent) {
            RBTNode subL=parent.left;
            RBTNode subLR=subL.right;
            subL.right=parent;
            parent.left=subLR;
            if(subLR!=null){
                subLR.parent=parent;
            }
            //记录原来的parent
            RBTNode pparent=parent.parent;
            parent.parent=subL;
            if(parent==root){
                root=subL;
                root.parent=null;
            }else{
                if(pparent.left==parent){
                    pparent.left=subL;
                }else{
                    pparent.right=subLR;
                }
                subL.parent=pparent;
            }
        }
    
        private void rotateLeft(RBTNode parent) {
            RBTNode subR=parent.right;
            RBTNode subRL=subR.left;
            subR.left=parent;
            parent.right=subRL;
            if(subRL!=null){
                subRL.parent=parent;
            }
            RBTNode pparent=parent.parent;
            parent.parent=subR;
            if(parent==root){
                subR=root;
                root.parent=null;
            }else{
                if(pparent.left==parent){
                    pparent.left=subR;
                }else{
                    pparent.right=subR;
                }
                subR.parent=pparent;
            }
        }

## 5.验证 ##

红黑树的检测分为两步：

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

2.检测其是否满足红黑树的性质

1. 每个结点不是红色就是黑色

2. 根节点是黑色的

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的【没有2个连续的红色节点】

4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

public boolean isRBTree(){
            if(root==null){
                return true;
            }
            if(root.color!=COLOR.BLACK){
                System.out.println("违反了性质2:根节点必须是黑色的");
            }
    
            int blackNum=0;
            RBTNode cur=root;
            while(cur!=null){
                if(cur.color==COLOR.BLACK){
                    blackNum++;
                }
                cur=cur.left;
            }
           //检查是否存在两个连续的红色节点  && 每条路径上黑色的节点的个数是一致的
            return checkRedColor(root) && checkBlackNum(root,0,blackNum);
    
        }
    
        private boolean checkBlackNum(RBTNode root, int pathBlackNum, int blackNum) {
            if(root==null) return true;
            if(root.color==COLOR.BLACK){
                pathBlackNum++;
            }
            if(root.left==null && root.right==null){
                if(pathBlackNum!=blackNum){
                    System.out.println("违反了每条路径上的黑色节点的个数相同");
                    return false;
                }
            }
            return checkBlackNum(root.left,pathBlackNum,blackNum)
                    && checkBlackNum(root.right, pathBlackNum, blackNum);
        }
    
        private boolean checkRedColor(RBTNode root) {
            if(root==null) return true;
            if(root.color==COLOR.RED){
                RBTNode parent=root.parent;
                if(parent.color==COLOR.RED){
                    System.out.println("违反了性质:连续出现两个红色的结点");
                    return false;
                }
            }
            return checkRedColor(root.left)
                    & checkRedColor(root.right);
        }
        public void inorder(RBTNode root){
            if(root==null){
                return ;
            }
            inorder(root.left);
            System.out.print(root.val+" ");
            inorder(root.right);
        }

## 6.比较 ##

红黑树不追求绝对公平,只保证最长路径不超过最短路径的2倍,降低了插入和旋转的次数，在增删的结构中性能比AVL树更优

## 7.应用 ##

java集合框架中的：TreeMap、TreeSet底层使用的就是红黑树

[576f030990034f6888aed1b43557bc61.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/397abf598dc84d14a806e1f62a6bd126.png
[8e99452233024a38b743bf8820fb4c47.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/c0f8c7c638b84851a9622d3554ddf856.png
[52d7ff20678440b39d1c2e02029b5ed9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d23e0227d6804834b17ef450bfa72668.png