Java 实现往红黑树插入结点

逃离我推掉我的手 2022-07-12 14:00 150阅读 0赞

红黑树是平衡二叉查找树中的一种，最突出的特点是效率高。时间复杂度：O(log(n))

红黑树有如下4个性质：  
1).没个结点不是红色就是黑色；  
2).根结点是黑色的；  
3).每个红色结点的父亲是黑色的；  
4).根结点到达每个叶子结点的路径中黑色结点的个数是一样的；

那么，为什么红黑树的效率高呢？  
根据性质3，先把红色结点跟父亲结点整合在一块，新整合出来的树称为“2-3-4 树”，它的高度为原先红黑树高度的1/2，如下图：

![这里写图片描述][SouthEast]

因为： 红黑树中，键是8个，叶子结点是9个  
所以：用归纳法可以得到叶子结点 = 键+1  
因为：在2-3-4树中，叶子结点的数量在 2^h <= 叶子结点 <= 2^h  
所以：高度 h 与键(n)的关系是：2^h <= n+1 取对数得：h <= log(n+1)  
又因为：红黑树的高度与2-3-4树的高度关系是：h = H/2  
所以：红黑树的高度与键的关系是： H <= 2log(n+1)  
高度与叶子是对数关系，而且高度一致，所以红黑树的平衡性很好，查找效率非常高。

但是！更新操作容易对红黑树造成破坏，失去平衡性。所以，在插入/删除红黑树的结点时，要保证红黑树的\`性质还在。对于这种恢复红黑树的操作，最典型的就是旋转，就是把某个结点往左/右旋转90度，如下图：

![这里写图片描述][SouthEast 1]

现在执行插入一个结点操作：

1).插入一个15结点，根据15数值的大小，确定15放在红黑树中的位置(叶子结点就不画了，小黑圈那些)

![这里写图片描述][SouthEast 2]

2).虽然15结点插入到红黑树中，但是破坏了红黑树的性质，采取旋转或颜色转换恢复红黑树的性质

![这里写图片描述][SouthEast 3]

根据上面的例子，对于插入结点后的红黑树而言，这里有个通用的算法：

case1：如果左右结点均为红色，进行颜色转换

case2：如果右子结点是红色的而左子结点是黑色的，进行左旋转

case3：如果左子结点是红色的且它的的左子结点是红色的，进行右旋转

如下图所示：

![这里写图片描述][SouthEast 4]

在Java中，集合类TreeMap就是基于红黑树实现的

下面看看Java实现插入结点的代码：

package RBT;
    
    public class RedBlackBST { 
    
        //根结点
        private Node root;
    
        //红黑
        private static final boolean RED = true;
        private static final boolean BLACK = false;
    
        //键
        private class Key { 
            private String key;
            Key(String key) {
                this.key = key;
            }
            public int compareTo(Key key2) {
                return key.compareTo(key2.key);
            }
        }
    
        //键值
        private class Value { 
            private int val;
            Value(int val) {
                this.val = val;
            }
        }
    
        //结点
        private class Node { 
            //键和键值
            Key key;
            Value val;
            //左右结点
            Node left, right;
            //包含几个子结点
            int N;
            //颜色
            boolean color;
    
            Node(Key key, Value val, int N, boolean color) {
                this.key = key;
                this.val = val;
                this.N = N;
                this.color = color;
            }
        }
    
        private boolean isRed(Node h) {
            if(h == null) return false;
            return h.color = RED;
        }
    
        private int size() {
            return size(root);
        }
    
        private int size(Node h) {
            if(h == null) {
                return 0;
            }
            return h.N;
        }   
    
        //左旋
        private Node rotateLeft(Node h) {
            Node x = h.right;
            h.right = x.left;
            x.left = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + size(h.left) + size(h.right);
            return x;
        }
    
        //右旋
        private Node rotateRight(Node h) {
            Node x = h.left;
            h.left = x.right;
            x.right = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + size(h.left) + size(h.right);
            return x;
        }
    
        //颜色转换
        private void flipColors(Node h) {
            h.color = RED;
            h.left.color = BLACK;
            h.right.color = BLACK;
        }
    
        public void put(Key key, Value val) {
            root = put(root, key, val);
            root.color = BLACK;
        }
    
        //插入结点
        public Node put(Node h, Key key, Value val) {
            if(h == null) 
                return new Node(key, val, 1, RED);
            //以下4个语句是将h根据键值大小放进红黑树中的位置
            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.val = 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);
            h.N = size(h.left) + size(h.right) + 1;
            return h;
        }
    
    }

以上是红黑树的插入操作，至于删除操作，看了一下午，还是有点蒙，若有一天我理解了，一定分享出来！

[SouthEast]: /images/20220709/a318a0bf09d64a12a155288fbc98d5fc.png
[SouthEast 1]: /images/20220709/f72ccbd16f59421395a37f2512568e93.png
[SouthEast 2]: /images/20220709/4b41d039a42a4d9b9f2ad4577217c43e.png
[SouthEast 3]: /images/20220709/fc0256893dd44e84bd96fd29b098c827.png
[SouthEast 4]: /images/20220709/3e81891cdf874ee59d534ce49dc9779f.png