红黑树学习

向右看齐 2023-06-01 12:57 44阅读 0赞

开始复习红黑树，根据算法4，上面先介绍2-3树，再引入红黑树方便理解

红黑树是 2-3 查找树，但它不需要分别定义 2- 节点和 3- 节点，而是在普通的二叉查找树之上，为节点添加颜色。指向一个节点的链接颜色如果为红色，那么这个节点和上层节点表示的是一个 3- 节点，而黑色则是普通链接。  
**红黑树的性质**  
1.每个节点都是红色或者黑色的。  
2.根节点一定是黑色的。  
3.每一个叶子节点（最后的空节点）是黑色的，为什么空节点是黑色的，因为在红黑树为空时，树根是黑色的。  
4.如果一个节点是红色的，那么它的孩子都是黑色的。  
5.从任意一个节点到叶子节点，经过的黑色节点是一样的

思考的方向就是，从2-3树到红黑树，就能明白红黑树的一些性质为什么是这样的。  
比如：红色节点的意思是，与它的父节点融合，类比成了2-3树的4-节点，就需要操作了。  
2-节点对应在红黑树中，就是黑色节点。  
如果4-节点拆分成为单独的2-节点，那么拆分的中间节点需要变成红色。  
**所有的红色节点都是左倾斜的，根节点的右子节点是红色的就不行，需要左旋。**

红黑树节点的定义就是在节点定义加个Color:

private static final boolean RED = true;
        private static final boolean BLACK = false;
    
        private class Node{
        
    
            public K key;
            public V value;
            public Node left,right;
    
            public boolean color;
    
            public Node(K key,V value){
        
    
                this.key = key;
                this.value = value;
                left = null;
                right  =null;
                color = RED;
            }
    
        }

这里面都有几种冲突但是大致的解决思路都是：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ_size_16_color_FFFFFF_t_70]

先左旋，后右旋，再颜色翻转。而这个左旋，右旋，其实操作都和AVL左旋右旋一样。理解了就一通百通。

//   node                     x
        //  /   \     左旋转         /  \
        // T1   x   --------->   node   T3
        //     / \              /   \
        //    T2 T3            T1   T2
        private Node leftRotate(Node node){
        
    
            Node x = node.right;
            node.right = x.left;
            x.left = node;
    
            x.color = node.color;
            node.color = RED;
    
        }
    
    
        //     node                   x
        //    /   \     右旋转       /  \
        //   x    T2   ------->   y   node
        //  / \                       /  \
        // y  T1                     T1  T2
        private Node rightRotate(Node node){
        
    
            Node x = node.left;
            node.left = x.right;
            x.right = node;
    
            x.color = node.color;
            node.color = RED;
    
            return x;
        }
    
        // 颜色翻转
        private void flipColors(Node node){
        
    
            node.color = RED;
            node.left.color = BLACK;
            node.right.color = BLACK;
    
        }

然后，每处理颜色冲突，就在每次二分递归找到的节点处，处理后，再递归返回到它的父节点，再出现冲突，再返回祖先节点解决冲突。  
**每次处理不在乎当前node节点的颜色，左旋，右旋，每次都是判断node的左子节点和右子节点的颜色，符合那种才旋转。** 处理完node，其次被返回给它的父节点，再重复判断。

// 向红黑树树中添加新元素节点(key,value)
        private void add(K key,V value){
        
            root = add(root,key,value);
            root.color = BLACK;
        }
    
        // 向以node为根节点的红黑树中插入元素(key,value)
        // 返回插入新节点后红黑树的根
        private Node add(Node node, K key, V value){
        
    
            if(node  ==  null) {
        
                size++;
                return new Node(key, value);
            }
            if(key.compareTo(node.key)<0)
            {
        
                node.left = add(node.left,key,value);
            }else if(key.compareTo(key)>0){
        
                node.right = add(node.right,key,value);
    
            }else{
        
                node.value = value;
            }
    
            if(isRed(node.right) && !isRed(node.left)){
        
    
                node = leftRotate(node);
            }
    
            if(isRed(node.left) && isRed(node.left.left))
            {
        
                node = rightRotate(node);
            }
            if(isRed(node.left) && isRed(node.right))
                flipColors(node);
    
    
            return node;
        }

附带bobo老师代码地址：[地址][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ_size_16_color_FFFFFF_t_70]: /images/20230601/39d34be2541b4ed088efbd2390a55ebb.png
[Link 1]: https://github.com/liuyubobobo/Play-with-Data-Structures/blob/master/13-Red-Black-Tree/08-The-Performance-of-Red-Black-Tree/src/RBTree.java