Java平衡树之红黑树代码实现过程详解（2）

梦里梦外; 2024-03-30 11:18 22阅读 0赞

## 红黑树 ##

前面介绍了[2-3树][2-3]，可以看到2-3树能保证在插入元素之后，树依然保持平衡状态，它的最坏情况下所有子结点都是2-结点，树的高度为lgN,相比于我们普通的二叉查找树，最坏情况下树的高度为N，确实保证了最坏情况下的时间复杂度，但是2-3树实现起来过于复杂，所以我们介绍一种2-3树思想的简单实现：**红黑树**。

### 1. 定义： ###

红黑树主要是对`2-3树`进行编码，红黑树背后的基本思想是用标准的`二叉查找树(完全由2-结点构成)`和一些额外的信息(替换3-结点)来表示`2-3树`。

我们将树中的链接分为**两种类型**：  
**红链接**：将两个2-结点连接起来构成一个3-结点；  
**黑链接**：则是2-3树中的普通链接。  
确切的说，我们将3-结点表示为由由一条左斜的红色链接(两个2-结点其中之一是另一个的左子结点)相连的两个2-结点。这种表示法的一个**优点是，我们无需修改就可以直接使用标准的二叉查找树的get方法。**  
![在这里插入图片描述][249ca9ca86d14ae2927f1642c858ca88.png]  
**红黑树是含有红黑链接并满足下列条件的二叉查找树：**

1.  红链接均为左链接；
2.  没有任何一个结点同时和两条红链接相连；
3.  该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同；

**下面是红黑树与2-3树的对应关系：**

![在这里插入图片描述][69d8e7aa53d14f81a94f860fe9417889.png]

### 2.红黑树结点API ###

> 因为每个结点都只会有一条指向自己的链接（从它的父结点指向它），我们可以在之前的Node结点中添加一个布尔类型的变量color来表示链接的颜色。如果指向它的链接是红色的，那么该变量的值为true，如果链接是黑色的，那么该变量的值为false。  
> ![在这里插入图片描述][fe56842f28d64d29abd23c9bc29ce4e9.png]

#### 2.1 API设计 ####

![在这里插入图片描述][0140b85f53f244fb900cffd8b0262829.png]

#### 2.2 代码实现 ####

private class Node<Key,Value>{
        
    	//存储键
    	public Key key;
    	//存储值
    	private Value value;
    	//记录左子结点
    	public Node left;
    	//记录右子结点
    	public Node right;
    	//由其父结点指向它的链接的颜色
    	public boolean color;
    	public Node(Key key, Value value, Node left,Node right,boolean color) {
        
    	this.key = key;
    	this.value = value;
    	this.left = left;
    	this.right = right;
    	this.color = color;
    	}
    }

### 3. 平衡化 ###

> 在对红黑树进行一些增删改查的操作后，很有可能会出现红色的右链接或者两条连续红色的链接，而这些都不满足红黑树的定义，所以我们需要对这些情况通过旋转进行修复，让红黑树保持平衡。

#### 3.1 左旋 ####

当某个结点的左子结点为黑色，右子结点为红色，此时需要左旋。  
**前提：** 当前结点为h，它的右子结点为x；  
**左旋过程：**  
1.让x的左子结点变为h的右子结点：h.right=x.left;  
2.让h成为x的左子结点：x.left=h;  
3.让h的color属性变为x的color属性值：x.color=h.color;  
4.让h的color属性变为RED：h.color=true;  
![在这里插入图片描述][77043decde7b41b6bedee494d7f1d4cc.png]

#### 3.2右旋 ####

当某个结点的左子结点是红色，且左子结点的左子结点也是红色，需要右旋  
**前提：** 当前结点为h，它的左子结点为x；  
**右旋过程：**

1.  让x的右子结点成为h的左子结点：h.left = x.right;
2.  让h成为x的右子结点：x.right=h;
3.  让x的color变为h的color属性值：x.color = h.color;
4.  让h的color为RED；\#\# 4.向单个2-结点中插入新键  
    ![在这里插入图片描述][20ab1e61dfe64429abf58e3b08d3fe7f.png]

一棵只含有一个键的红黑树只含有一个2-结点。插入另一个键后，我们马上就需要将他们旋转。

*  如果新键小于当前结点的键，我们只需要新增一个红色结点即可，新的红黑树和单个3-结点完全等价。  
    ![在这里插入图片描述][6ecd245a032f4d69a721068ded846f1a.png]
 *  如果新键大于当前结点的键，那么新增的红色结点将会产生一条红色的右链接，此时我们需要通过左旋，把红色右链接变成左链接，插入操作才算完成。形成的新的红黑树依然和3-结点等价，其中含有两个键，一条红色链接。  
    ![在这里插入图片描述][b58a8c84703844ecbeefa4c848ce2b81.png]

### 5. 向底部的2-结点插入新键 ###

> 用和二叉查找树相同的方式向一棵红黑树中插入一个新键，会在树的底部新增一个结点（可以保证有序性），唯一  
> 区别的地方是我们会用红链接将新结点和它的父结点相连。如果它的父结点是一个2-结点，那么刚才讨论的两种方  
> 式仍然适用。

![在这里插入图片描述][00f7afc4153648d1ab31d7798e3742c6.png]

### 6. 颜色反转 ###

> 当一个结点的左子结点和右子结点的color都为RED时，也就是出现了临时的4-结点，此时只需要把左子结点和右子结点的颜色变为BLACK，同时让当前结点的颜色变为RED即可  
> ![在这里插入图片描述][f3832ed4e5fb4d909a8091ced3a2dc1b.png]

### 7. 向一棵双键树(即一个3-结点)中插入新键 ###

这种情况有可以分为`三种情况`：

1.  新键大于原树中的两个键
2.  新键小于原树中的两个键
3.  新键介于原数中两个键之间

#### 7.1 新键大于原树中的两个键 ####

![在这里插入图片描述][3fbfcc8b109f4e42bbbe2dac5fb0a0e2.png]

#### 7.2 新键小于原树中的两个键 ####

![在这里插入图片描述][bb76c22025e64a029a1aa9b1c106462f.png]

#### 7.3 新键介于原数中两个键之间 ####

![在这里插入图片描述][622a07617cce418db1aeda7a56122e07.png]

### 8. 根结点的颜色总是黑色 ###

> 之前我们介绍结点API的时候，在结点Node对象中color属性表示的是父结点指向当前结点的连接的颜色，由于根结点不存在父结点，所以每次插入操作后，我们都需要把根结点的颜色设置为黑色。

### 9. 向树底部的3-结点插入新键 ###

> 假设在树的底部的一个3-结点下加入一个新的结点。前面我们所讲的3种情况都会出现。指向新结点的链接可能是3-结点的右链接（此时我们只需要转换颜色即可），或是左链接(此时我们需要进行右旋转然后再转换)，或是中链接(此时需要先左旋转然后再右旋转，最后转换颜色)。颜色转换会使中间结点的颜色变红，相当于将它送入了父结点。这意味着父结点中继续插入一个新键，我们只需要使用相同的方法解决即可，直到遇到一个2-结点或者根结点为止。  
> ![在这里插入图片描述][5a11b12eb4d3480eb62800c2cd12d1fc.png]  
> ![在这里插入图片描述][9684a83551784ad9be0882bcfa0507b5.png]

### 10. 红黑树的API设计 ###

![在这里插入图片描述][56e40c1119614ea5aab82ce4aff2b316.png]

### 11. 红黑树的代码实现 ###

package heimadatapractise;
    
    public class RedBlackTree <Key extends Comparable<Key>,Value>{
         //红黑树代码
        public static void main(String[] args) throws Exception{
         //测试代码
            RedBlackTree<Integer, String> bt = new RedBlackTree<>();
            bt.put(4, "二哈");
            bt.put(1, "张三");
            bt.put(3, "李四");
            bt.put(5, "王五");
            System.out.println(bt.size());
            bt.put(1,"老三");
            System.out.println(bt.get(1));
            System.out.println(bt.size());
    
        }
        private Node root; //根节点
        private int N; //记录树中元素的个数
        private static final boolean RED = true;//红色链接
        private static final boolean BLACK = false; //黑色链接
    
        private class Node{
        //结点类
            public Key key; //存储键
            private Value value; //存储值
            public Node left; //记录左子结点
            public Node right;//记录右子结点
            public boolean color; //由其父结点指向它的链接的颜色
            public Node(Key key,Value value,Node left,Node right, boolean color){
        
                this.key =key;
                this.value= value;
                this.left= left;
                this.right = right;
                this.color= color;
            }
        }
    
        private boolean isRed(Node x){
         //判断当前节点的父指向链接是否为红色
            if(x==null){
         //空结点默认是黑色链接
                return false;
    
            }
            return x.color ==RED; //非空结点需要判断结点color属性的值
    
        }
    
        private Node rotateLeft(Node h){
        //左旋转
            Node hRight = h.right; //找出当前结点h的右子结点
            Node lhRight = hRight.left; //找出右子结点的左子结点
            h.right =lhRight; //让当前结点h的右子结点的左子结点成为当前结点的右子结点
            hRight.left =h; //让当前结点h称为右子结点的左子结点
            hRight.color = h.color; //让当前结点h的color编程右子结点的color
            h.color = RED; //让当前结点h的color变为RED
            return hRight;//返回当前结点的右子结点
    
        }
        private Node rotateRight(Node h){
         //右旋
            Node hLeft = h.left; //找出当前结点h的左子结点
            Node rHleft = hLeft.right; //找出当前结点h的左子结点的右子结点
            h.left =rHleft; //让当前结点h的左子结点的右子结点称为当前结点的左子结点
            hLeft.right =h; //让当前结点称为左子结点的右子结点
            hLeft.color =h.color; //让当前结点h的color值称为左子结点的color值
            h.color =RED; //让当前结点h的color变为RED
            return hLeft; //返回当前结点的左子结点
        }
        private void flipColors(Node h){
        //颜色反转,相当于完成拆分4-节点
            h.color = RED; //当前结点的color属性值变为RED；
            h.left.color = BLACK;//当前结点的左右子结点的color属性值都变为黑色
            h.right.color = BLACK;
        }
    
       public void put(Key key, Value val){
         //在整个树上完成插入操作
            root = put (root,key,val); //在root整个树上插入key-val
            root.color = BLACK; //让根结点的颜色变为BLACK
    
        }
        private Node put(Node h,Key key, Value val) {
         //在指定树中，完成插入操作,并返回添加元素后新的树
            if (h == null) {
        
                N++; //标准的插入操作，和父结点用红链接相连
                return new Node(key, val, null, null, RED);
    
            }
            //比较要插入的键和当前结点的键
            int cmp = key.compareTo(h.key); //比较要插入的键和当前结点的键
            if (cmp < 0) {
         //继续寻找左子树插入
                //继续寻找左子树插入
                h.left = put(h.left, key, val);
            } else if (cmp > 0) {
         //继续寻找右子树插入
                //继续寻找右子树插入
                h.right = put(h.right, key, val);
            } else {
        
                //已经有相同的结点存在，修改节点的值；
                h.value = val; //已经有相同的结点存在，修改节点的值；
            }
    
            if(isRed(h.right)&&!isRed(h.left)){
         //如果当前结点的右链接是红色，左链接是黑色，需要左旋
                h=rotateLeft(h);
            }
            //如果当前结点的左子结点和左子结点的左子结点都是红色链接，则需要右旋
            if (isRed(h.left) && isRed(h.left.left)) {
        
                h=rotateRight(h);
            }
            if(isRed(h.left)&&isRed(h.right)){
         //如果当前结点的左链接和右链接都是红色，需要颜色变换
                flipColors(h);
            }
            return h; //返回当前结点
        }
        //根据key，从树中找出对应的值
        public Value get(Key key) {
         //根据key，从树中找出对应的值
            return get(root, key); //如果当前结点为空，则没有找到,返回null
        }
        public Value get(Node x,Key key){
        
            if(x==null){
        
                return null;
            }
            int cmp =key.compareTo(x.key);  //比较当前结点的键和key
            if(cmp<0){
         //如果要查询的key小于当前结点的key，则继续找当前结点的左子结点；
                return get(x.left,key);
    
            }else if(cmp>0){
         //如果要查询的key大于当前结点的key，则继续找当前结点的右子结点；
                return get(x.right,key);
            }else{
         //如果要查询的key等于当前结点的key，则树中返回当前结点的value。
                return x.value;
            }
        }
        public int size(){
          //获取树中元素的个数
            return N;
        }
    
    
    }

### 12. 代码实现结果 ###

4
    老三
    4

参考：黑马程序员Java数据结构与java算法

[2-3]: https://blog.csdn.net/weixin_45428910/article/details/128403857?csdn_share_tail=%7B%22type%22:%22blog%22,%22rType%22:%22article%22,%22rId%22:%22128403857%22,%22source%22:%22weixin_45428910%22%7D
[249ca9ca86d14ae2927f1642c858ca88.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b017f1f760874d5399d3729e8cabce96.png
[69d8e7aa53d14f81a94f860fe9417889.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0f6d4cf10bc44b52ae1c9d0f338e6fa9.png
[fe56842f28d64d29abd23c9bc29ce4e9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/5b907126af7d44b387e94d4e18adfa20.png
[0140b85f53f244fb900cffd8b0262829.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8ea5aeec63fb4edab6fc4dfcd7a699b6.png
[77043decde7b41b6bedee494d7f1d4cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d59668d568034bb08eded403c511a749.png
[20ab1e61dfe64429abf58e3b08d3fe7f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/06c61dcd4158485fa63e0e97d1013edd.png
[6ecd245a032f4d69a721068ded846f1a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6fbda6bd92bb45378d1163d3cdd9c056.png
[b58a8c84703844ecbeefa4c848ce2b81.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/451e7535645243789a91bb49024f3079.png
[00f7afc4153648d1ab31d7798e3742c6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/dbb80b8e1f5444cd94ffadb48605f436.png
[f3832ed4e5fb4d909a8091ced3a2dc1b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/eac071af2e7a4d629ba7439da99dc562.png
[3fbfcc8b109f4e42bbbe2dac5fb0a0e2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/182844df7f7e46e29915be1ab5940775.png
[bb76c22025e64a029a1aa9b1c106462f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/ba436767555047f09624463933553c72.png
[622a07617cce418db1aeda7a56122e07.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/87b6ed2c63ed491e8e1cfd54a749c01d.png
[5a11b12eb4d3480eb62800c2cd12d1fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/ac363aefc5c340a09b4bfd7dfee264df.png
[9684a83551784ad9be0882bcfa0507b5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/32e41a2878864a37925e58bef20274f5.png
[56e40c1119614ea5aab82ce4aff2b316.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/5173d71a41094ca5bd50c6aabc1200d2.png