理解红黑树

非常推荐通过 USF Data Structure Visualizations 来理解红黑树的变换过程。

红黑树解决了什么问题

在已经有了 AVL 树（请看理解AVL树）的情况下，我们为什么还要开发红黑树？
主要是因为 AVL 在再平衡的过程中的变换太多，性能不够好，红黑树主要是解决了性能问题，采用更加宽松的标准，通过牺牲树高，来减少插入和删除的时候的变换的次数。

红黑树的性质（约束）

红黑树的五条性质（背下来）

一个节点要么是红色，要么是黑色
根节点是黑色
叶子节点是黑色
红节点的子节点必须是黑色
每一个节点，到任意叶子节点的路径中包含的黑色节点数（黑高）都是相同的

红黑树的实现

这里的实现为 AI 生成，其严格参照了《算法导论》中第 13 章红黑树中的伪代码。

树节点

直接上代码
RedBlackTreeNode：为了方便查看树结构，这里让 RedBlackTreeNode 实现了 BTPrinterAdapter，关于这个接口，请看在控制台输出二叉树的结构#节点适配器。

public class RedBlackTreeNode<K extends Comparable<K>, V> implements BTPrinterAdapter<RedBlackTreeNode<K, V>> {  
  
    // Node color constants  
    public static final boolean RED = true;  
    public static final boolean BLACK = false;  
  
    public K key;  
    public V value;  
    // 注意这里有一个向上的指针，就是为了方便查找父节点的另一个子节点  
    //有 parent 这个指针的存在，我们就需要维护双向的关系  
    // 比如在 旋转的时候，  
    // 比如在子节点替代父节点的时候  
    // 在 AVL 树中，我们通过递归更新父节点的 left 和 right 指针，所以不需要这个指针  
    public RedBlackTreeNode<K, V> left, right, parent;  
    public boolean color; // true for RED, false for BLACK  
  
    // 当不指定颜色的时候，默认就是红色  
    public RedBlackTreeNode(K key, V value) {  
        this.key = key;  
        this.value = value;  
        this.left = null;  
        this.right = null;  
        this.parent = null;  
        this.color = RED; // New nodes are always RED  
    }  
  
    public RedBlackTreeNode(K key, V value, boolean color) {  
        this.key = key;  
        this.value = value;  
        this.left = null;  
        this.right = null;  
        this.parent = null;  
        this.color = color;  
    }  
  
    @Override  
    public String getNodeString() {  
        String colorStr = color == RED ? "R" : "B";  
        if (key == null) {  
            return "NIL(" + colorStr + ")";  
        }  
        return key.toString() + ":" + value.toString() + "(" + colorStr + ")";  
    }  
  
    @Override  
    public RedBlackTreeNode<K, V> getLeftNode() {  
        return left;  
    }  
  
    @Override  
    public RedBlackTreeNode<K, V> getRightNode() {  
        return right;  
    }  
}

我们可以看到除了一些常规的树节点的属性

key
value
left
right
之外，还有：
color
parent
color 自不必说，红黑树的节点自带颜色，
parent 指针我们在实现 AVL 树的时候是没有的（理解AVL树），在 AVL 树中，我们通过递归更新父节点的 left 和 right 指针，所以不需要这个指针。但是在红黑树中不行，因为我们在插入之后的再平衡需要参考父节点的父节点的另一个子节点，即舅舅节点（uncle，对应变量名 u），删除之后的再平衡需要参考删除位置的父节点的另一个子节点，也就是兄弟节点（sibling，对应变量名，为什么不用 s？ s 虽然是 “sibling” 的首字母，但也常用于其他变量，如 successor（后继），容易混淆。 w 较少在其他上下文中被使用，避免命名冲突）。因此这里必须有一个指针指向父节点，方便从当前节点本身找到其兄弟节点。
也正是因为这里多了这样一个指针，所以当我们设置父节点的 left 或者 right 之后，我们还要设置子节点的 parent，即需要维护双向的关系。这就导致了当我们在进行子树变换的时候，需要特别注意，不要设置错了指针，比如在旋转（理解红黑树#左旋、理解红黑树#右旋）的时候，比如在一直比如在移植（理解红黑树#移植）的时候。

树本身

直接看代码本身 RedBlackTree，我们先看整体的代码，然后再分块来看这个代码，以理解红黑树的算法

/**  
 * Red-Black Tree implementation * <p>  
 * Properties of Red-Black Trees: 
 * 1. Every node is either red or black. 
 * 2. The root is black. 
 * 3. Every leaf (NIL) is black. 
 * 4. If a node is red, then both its children are black. 
 * 5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes. 
 */
 public class RedBlackTree<K extends Comparable<K>, V> {  
  
    private RedBlackTreeNode<K, V> root;  
    // 整个树只用一个 NIL 对象，  
    // 有两个好处，一个是不需要开辟额外的内存空间，不然每一个 NIL 都是一个新的对象，那当叶子节点足够多，一个红黑树就会占用极大的内存，而且无法释放。  
    // 第二个是好处是对比起来直接用 == 即可  
    private final RedBlackTreeNode<K, V> NIL;  
  
    public RedBlackTree() {  
        // Create a sentinel NIL node (always black)  
        NIL = new RedBlackTreeNode<>(null, null, RedBlackTreeNode.BLACK);  
        root = NIL;  
    }  
  
    /**  
     * Search for a node with the given key     
     *     
     * @param key The key to search for  
     * @return The node with the given key, or null if not found  
     */    
     public RedBlackTreeNode<K, V> search(K key) {  
        if (key == null) {  
            return null;  
        }  
  
        RedBlackTreeNode<K, V> current = root;  
        while (current != NIL) {  
            int cmp = key.compareTo(current.key);  
            if (cmp == 0) {  
                return current;  
            } else if (cmp < 0) {  
                current = current.left;  
            } else {  
                current = current.right;  
            }  
        }  
        return null;  
    }  
  
    /**  
     * Insert a key-value pair into the tree     
     *     
     * @param key   The key  
     * @param value The value  
     */    
     public void insert(K key, V value) {  
        if (key == null || value == null) {  
            return;  
        }  
  
        // Create new node  
        RedBlackTreeNode<K, V> newNode = new RedBlackTreeNode<>(key, value);  
        newNode.left = NIL;  
        newNode.right = NIL;  
  
        // Find position to insert  
        // y 表示要 newNode 最终要挂的位置  
        RedBlackTreeNode<K, V> y = NIL;  
        // x 可以理解为一个过程变量  
        RedBlackTreeNode<K, V> x = root;  
  
        // 跟搜索的方式一样，直接找到要插入的位置，然后插入到这个位置下  
        while (x != NIL) {  
            y = x;  
            int cmp = key.compareTo(x.key);  
            if (cmp < 0) {  
                x = x.left;  
            } else if (cmp > 0) {  
                x = x.right;  
            } else {  
                // Key already exists, update value  
                x.value = value;  
                return;  
            }  
        }  
  
        // 此时 x 一定是 NIL  
        // 需要这个向上的指针吗？  
        // Set parent of new node  
        // 如果此时 y 就是 NIL，那么此时 newNode 的父节点就是 NIL，也就是说 root 节点的 NIL 其实是 NIL
        newNode.parent = y;  
  
        // 确定是 newNode 是其父节点的左节点还是右节点  
        // Insert node in the right position  
        if (y == NIL) {  
            // 其实这个可以提前，直接判断 root 的 key 是否是 null            
            // Tree was empty            
            // 因为我们之前在构造 newNode 的时候就设置了，其左右两个子节点都是 NIL，所以这里可以直接将其设置成根节点  
            root = newNode;  
        } else {  
            int cmp = key.compareTo(y.key);  
            if (cmp < 0) {  
                // y.left 之前指向 NIL，这里直接用 newNode 替代，毕竟 newNode 的左右子节点也都是 NIL                
                y.left = newNode;  
            } else {  
                // y.right  之前指向 NIL，这里直接用 newNode 替代，毕竟 newNode 的左右子节点也都是 NIL                
                y.right = newNode;  
            }  
        }  
  
        // 其实到这里，并没有看出跟 AVL 树的区别  
        // 因为有 parent 指针，所以这里不需要传入更多的条件  
        // Fix Red-Black properties  
        fixInsert(newNode);  
    }  
  
    /**  
     * Fix Red-Black Tree properties after insertion     
     *     
     * @param k The newly inserted node  
     */    
     private void fixInsert(RedBlackTreeNode<K, V> k) {  
        RedBlackTreeNode<K, V> u;  
  
  
        // 注意，插入的时候仅仅需要注意一条规则：其父节点不能是 Red，因为新插入的节点都是 red，所以其父节点不能是 red，  
        // 这是红黑树的第四条规则决定的：因为 red 下只能是 black        
        // 而如果父节点是黑色，那就啥都不用干了，直接跳出循环即可。
        // k.parent 是 NIL，说明 k 是根节点  
        // While parent is red (violates property 4)  
        while (k.parent != NIL && k.parent.color == RedBlackTreeNode.RED) {  
            if (k.parent == k.parent.parent.right) {  
                // Parent is right child of grandparent  
                u = k.parent.parent.left; // Uncle  
  
                if (u.color == RedBlackTreeNode.RED) {  
                    // Case 1: Uncle is red  
                    // 此时不用管 k 在父节点的左边还是右边，因此此时不需要旋转，只有旋转才需要在乎节点在左边还是右边  
                    u.color = RedBlackTreeNode.BLACK;  
                    k.parent.color = RedBlackTreeNode.BLACK;  
                    // 为了保证黑高不变，所以这里必须将父节点的父节点变色，否则就相当于多了一个黑高  
                    k.parent.parent.color = RedBlackTreeNode.RED;  
                    // 但是让父节点的父节点变色，有可能让 grandparent 和 grandparent  的 parent 相冲突，  
                    // 因此需要让 k 的 grandparent 节点作为下一轮循环的主角  
                    // 再次进行循环，进行颜色的平衡  
                    k = k.parent.parent;  
                    // 其实直接变色，相当于节省了一次旋转  
                } else {  
                    // 此时 k 的父节点是红色，同时 u 节点是黑色，其实此时可以倒推出来，k.parent.parent 的节点的颜色一定是黑色  
                    // 非情况讨论  
                    // k 在其父节点的左边，现在的场景有点类似于 RL                    
                    if (k == k.parent.left) {  
                        // Case 2: Uncle is black and k is left child  
                        // 将 k 的父节点设置为 K，然后对其进行右旋  
                        // 如果理解这个操作，其实可以这么看，k 代表的是一个位置，而不是指特定的节点  
                        k = k.parent;  
                        rightRotate(k);  
                        // 这样，右旋之后，k 就处于最下面，这就跟 k 在一开始就满足 k == k.parent.right 对上了，可以直接往下走。  
                        // 注意，要先设置 k = k.parent，然后再进行右旋  
                    }  
                    // Case 3: Uncle is black and k is right child  
                    k.parent.color = RedBlackTreeNode.BLACK;  
                    k.parent.parent.color = RedBlackTreeNode.RED;  
                    // 变色结束之后，u 所在的分支的黑高少了，此时只能进行左旋，来保证 u 这条线的黑高不变  
                    leftRotate(k.parent.parent);  
                    // 其实从图中我们就可以看出，只要是这种情况，基本上就一次操作结束，再次递归也不会进行操作了  
                    // 因为旋转完之后，k 的 parent 的颜色就是 黑色了，下一次循环就跳出去了。  
                }  
            } else {  
                // Parent is left child of grandparent (mirror cases)  
                u = k.parent.parent.right; // Uncle  
  
                if (u.color == RedBlackTreeNode.RED) {  
                    // Case 1: Uncle is red  
                    u.color = RedBlackTreeNode.BLACK;  
                    k.parent.color = RedBlackTreeNode.BLACK;  
                    k.parent.parent.color = RedBlackTreeNode.RED;  
                    k = k.parent.parent;  
                } else {  
                    if (k == k.parent.right) {  
                        // Case 2: Uncle is black and k is right child  
                        k = k.parent;  
                        leftRotate(k);  
                    }  
                    // Case 3: Uncle is black and k is left child  
                    k.parent.color = RedBlackTreeNode.BLACK;  
                    k.parent.parent.color = RedBlackTreeNode.RED;  
                    rightRotate(k.parent.parent);  
                }  
            }  
  
            if (k == root) {  
                break;  
            }  
        }  
  
        // 只通过颜色转换来保持颜色平衡的时候，是可能将根节点换成红色的，比如我一开始只有两层，然后现在你来了第三层，第二层恰好都是红色，那一次变色直接将根节点变成了红色，  
        // 这个时候就需要这里来将根节点的颜色变回来。  
        // Ensure root is black (property 2)  
        root.color = RedBlackTreeNode.BLACK;  
    }  
  
    /**  
     * Delete a node with the given key     
     *     
     * @param key The key to delete  
     */    
     public void delete(K key) {  
        if (key == null) {  
            return;  
        }  
  
        // Find the node to delete  
        RedBlackTreeNode<K, V> z = search(key);  
        if (z == null) {  
            return; // Key not found  
        }  
  
        deleteNode(z);  
    }  
  
  
    /**  
     * Delete a node from the tree     
     *     
     * @param z The node to delete  
     */    
     private void deleteNode(RedBlackTreeNode<K, V> z) {  
        //  y 是被删除的节点  
        RedBlackTreeNode<K, V> y = z;  
        // x 是 顶替被删除节点的节点，也就是说，检查或者修复要从 x 开始  
        // 如果被删除节点没有子节点或者只有一个子节点，那参数 z 就是 y，z 的 left 或者 right 就是 x        
        // 如果被删除节点两个子节点都有，那就从 right 节点开始找一个最小的节点替换到被删除节点的位置，而且颜色也要换成 z 的颜色，这就说明实际上 z 的附近的颜色其实没有变化，变化的是这个最小节点的附近，  
        // 所以 y 是最小节点，x 是 y 的 right（因为是最小节点，所以 left 为 null）  
        RedBlackTreeNode<K, V> x;  
        boolean yOriginalColor = y.color;  
  
        if (z.left == NIL) {  
            // Case 1: No left child  
            x = z.right;  
            transplant(z, z.right);  
        } else if (z.right == NIL) {  
            // Case 2: No right child  
            x = z.left;  
            transplant(z, z.left);  
        } else {  
            // Case 3: Two children  
            // 从右节点中找到最小的元素  
            y = minimum(z.right);  
            yOriginalColor = y.color;  
            // 因为 y 是最小的节点，因此，y 肯定没有左子节点，只可能有右子节点  
            x = y.right;  
  
            if (y.parent == z) {  
                // z.right 这个节点没有左子节点，也就是说 y 就是 z.right，此时 y 就不用删除了，直接用 y 移植到 z 的位置上即可  
                // 此时，将 x 的 parent 设置成 y（不过 x 的 parent 本来也就是 y）  
                // 在下面这个分支里，x 的 parent 其实是 y 的 parent，这两种情况不一样  
                x.parent = y;  
            } else {  
                // y 从树中半脱离，没有指向它的指针，只有 y.right 指向树中的节点了  
                // 这里实际上将 x 的 parent 指向了 y 的 parent                
                transplant(y, y.right);  
                // 同样的，y 因为是最小的节点，所以的左叶节点是 null，  
                // 这里是将要删除的 z 的右子节点挂到 y 上，  
                // 这是在为 y 替代 z 做准备  
                y.right = z.right;  
                // y 的 parent 指针在 transplant 方法中设置  
                // 设置指针的只想关系，一定要设置两次。  
                // 这个完全可以专门写一个方法，内容就跟 transplant 一样，换个名字，就叫 connectTwoNode，两个参数，一个 parent，一个 child，然后给一个参数 isLeft                
                y.right.parent = y;  
            }  
  
            // y 替代 z            
            transplant(z, y);  
            // z.right 在上面已经替代过了  
            y.left = z.left;  
            y.left.parent = y;  
            // 也就是说，删除了 z，其实 z 附近的黑高并没有影响，因为 z 原来是什么颜色，y 填充过来之后就改变成了什么颜色  
            // 所以我们只用检查删除 y 之后的的黑高的变化  
            y.color = z.color;  
        }  
  
        // 为什么不用再检查 z.color，因为前面 y 在替代 z 之后，颜色也改成了 z 的颜色，所以 z 的附近的黑高是没有变化的。所以这里只用检查 y 被删除之后，x 替代它的时候的黑高的变化。  
        // 如果 y 的颜色为红色，那也不用管，因为不会影响黑高，只有 y 的原来的颜色是黑色的时候，才会影响黑高，才需要修复  
        // If the original color was black, we need to fix the tree  
        if (yOriginalColor == RedBlackTreeNode.BLACK) {  
            fixDelete(x);  
        }  
    }  
  
    /**  
     * Fix Red-Black Tree properties after deletion     
     *     
     * @param x The node that replaced the deleted node  
     */    
     private void fixDelete(RedBlackTreeNode<K, V> x) {  
  
        // 这里的操作梳理一下是这样的，首先被删除的节点是黑色的，  
        // 如果顶替其的节点 x 是红色的，那么直接将其变黑即可，黑高不变，同时少了一个红节点没关系，x 变红，其子节点也不受影响。直接就结束了  
        // 如果顶替其的节点 x 是黑色的，那么就只能通过变换，从 x 的父节点中增加一个黑色节点，或者从 x 的兄弟节点中减少一个黑色节点，来进行平衡  
  
		// 重点是，在删除一个结点之后，保证经过的路径的黑高都不变，且相等，所以，就必须考虑相邻节点的黑高。因为被删除的节点的相关的黑高都少了 1       
		while (x != root && x.color == RedBlackTreeNode.BLACK) {  
            if (x == x.parent.left) {  
                RedBlackTreeNode<K, V> w = x.parent.right;  
  
                if (w.color == RedBlackTreeNode.RED) {  
                    // 兄弟节点是红色，此时两个子节点一定是黑色节点，  
                    // 通过变色 + 旋转  
                    // 这个其实没有往 x 这一边增加一个黑色节点，这个时候的做法其实是转化为了其他的场景  
                    // Case 1: Sibling is red  
                    w.color = RedBlackTreeNode.BLACK;  
                    x.parent.color = RedBlackTreeNode.RED;  
                    leftRotate(x.parent);  
                    // 保持 w 的定义，w 始终都是 x 的兄弟节点  
                    // 新的 w 其实是原来的老的 w 的左节点，一定是黑色节点  
                    w = x.parent.right;  
                }  
  
                // w 一定是黑色的  
                if (w.left.color == RedBlackTreeNode.BLACK && w.right.color == RedBlackTreeNode.BLACK) {  
                    //  兄弟节点是黑色，而且兄弟节点的两个子节点都是黑色  
                    // Case 2: Sibling is black and both its children are black  
                    w.color = RedBlackTreeNode.RED;  
                    x = x.parent;  
                    // 因为此时我们不知道 x.parent 的颜色是什么，如果是红色，那么就有两个红色了，所以，此时需要将  x.parent 作为 x 再次进行判断  
                    // 只有这一种情况会再次循环  
                } else {  
                    // x 是黑色，兄弟节点是黑色，兄弟节点的两个子节点不全是黑色  
                    // 有可能是两个红色，或者一红一黑  
                    // 这个思路是给 x 这一侧增加一个黑色节点  
                    if (w.right.color == RedBlackTreeNode.BLACK) {  
                        // Case 3: Sibling is black, left child is red, right child is black  
                        // 此时左节点必定不为黑色，也就是为红色，那么左节点的两个子节点也都是黑色  
                        // 需要通过旋转，将 w 的右子节点变成红色  
                        w.left.color = RedBlackTreeNode.BLACK;  
                        w.color = RedBlackTreeNode.RED;  
                        rightRotate(w);  
                        // 保持 w 的定义，w 始终都是 x 的兄弟节点  
                        w = x.parent.right;  
                    }  
  
                    // Case 4: Sibling is black, right child is red  
                    // 这个变色很精髓，我感觉变色，其实没有什么技巧，就是按照最终结果去变色即可。  
                    // 这是为了让 w 作为新的顶点做准备  
                    w.color = x.parent.color;  
                    // 为 x 这一只新增一个黑节点  
                    x.parent.color = RedBlackTreeNode.BLACK;  
                    // 之前为红，现在直接转为黑，  
                    w.right.color = RedBlackTreeNode.BLACK;  
                    leftRotate(x.parent);  
                    //因为可以直接结束了，所以直接将 root 赋值给 x，直接跳出循环  
                    x = root;  
                }  
            } else {  
                // Mirror cases for right child  
                RedBlackTreeNode<K, V> w = x.parent.left;  
  
                if (w.color == RedBlackTreeNode.RED) {  
                    // Case 1: Sibling is red  
                    w.color = RedBlackTreeNode.BLACK;  
                    x.parent.color = RedBlackTreeNode.RED;  
                    rightRotate(x.parent);  
                    w = x.parent.left;  
                }  
  
                if (w.right.color == RedBlackTreeNode.BLACK && w.left.color == RedBlackTreeNode.BLACK) {  
                    // Case 2: Sibling is black and both its children are black  
                    w.color = RedBlackTreeNode.RED;  
                    x = x.parent;  
                } else {  
                    if (w.left.color == RedBlackTreeNode.BLACK) {  
                        // Case 3: Sibling is black, right child is red, left child is black  
                        w.right.color = RedBlackTreeNode.BLACK;  
                        w.color = RedBlackTreeNode.RED;  
                        leftRotate(w);  
                        w = x.parent.left;  
                    }  
  
                    // Case 4: Sibling is black, left child is red  
                    w.color = x.parent.color;  
                    x.parent.color = RedBlackTreeNode.BLACK;  
                    w.left.color = RedBlackTreeNode.BLACK;  
                    rightRotate(x.parent);  
                    x = root;  
                }  
            }  
        }  
  
        // 这样不管 x 下面是红色还是黑色，都不影响黑高。因为 x 变黑填补了 y 这个黑节点被删掉的空缺，而少一个红节点其实不影响黑高  
        // 必须写在最后面  
        // 这里会把 x 的 coler 强制变黑，  
        x.color = RedBlackTreeNode.BLACK;  
    }  
  
    /**  
     * 这个方法并没有修改 u，也只修改了 u.parent 的左指针或者右指针和 v 的 parent 指针  
     * u 从树中半脱离，没有指向它的指针，只有它指向树中的节点了  
     * Replace subtree rooted at u with subtree rooted at v  
     *     
     * @param u The subtree to be replaced  
     * @param v The subtree that replaces u  
     */    
     private void transplant(RedBlackTreeNode<K, V> u, RedBlackTreeNode<K, V> v) {  
        // 这里要更新两个元素，一个元素是 u 的 parent，一个是 v        
        // 让 u 的 parent 的 left 或者 right 指向 v，同时 v 的 parent 指向 u 即可  
        // 这个方法并没有修改 u  
  
        //有 parent 这个指针的存在，我们就需要维护双向的关系  
        if (u.parent == NIL) {  
            root = v;  
        } else if (u == u.parent.left) {  
            u.parent.left = v;  
        } else {  
            u.parent.right = v;  
        }  
        v.parent = u.parent;  
    }  
  
    /**  
     * Find the minimum node in the subtree rooted at x     
     *     
     * @param x The root of the subtree  
     * @return The minimum node  
     */    
     private RedBlackTreeNode<K, V> minimum(RedBlackTreeNode<K, V> x) {  
        while (x.left != NIL) {  
            x = x.left;  
        }  
        return x;  
    }  
  
    /**  
     * Left rotation     
     *     
     * @param x The node to rotate around  
     */    
     private void leftRotate(RedBlackTreeNode<K, V> x) {  
        RedBlackTreeNode<K, V> y = x.right;  
        x.right = y.left;  
  
        if (y.left != NIL) {  
            y.left.parent = x;  
        }  
  
        y.parent = x.parent;  
  
        if (x.parent == NIL) {  
            root = y;  
        } else if (x == x.parent.left) {  
            x.parent.left = y;  
        } else {  
            x.parent.right = y;  
        }  
  
        y.left = x;  
        x.parent = y;  
    }  
  
    /**  
     * Right rotation     
     *     
     * @param y The node to rotate around  
     */    
     private void rightRotate(RedBlackTreeNode<K, V> y) {  
  
        RedBlackTreeNode<K, V> x = y.left;  
  
		// 更新一个链接  
		y.left = x.right;  
		// 注意需要维护 parent 链接，感觉好麻烦啊。  
		if (x.right != NIL) {  
		    x.right.parent = y;  
		}  
		  
		// 跟新 x 的 parent 链接，并更新 从上到下的链接，  
		x.parent = y.parent;  
		if (y.parent == NIL) {  
		    root = x;  
		} else if (y == y.parent.left) {  
		    y.parent.left = x;  
		} else {  
		    y.parent.right = x;  
		}  
		  
		// 更新另一个链接  
		x.right = y;  
		y.parent = x;  
	}  
  
    /**  
     * Get the root of the tree     
     *     
     * @return The root node  
     */    
     public RedBlackTreeNode<K, V> getRoot() {  
        return root == NIL ? null : root;  
    }  
  
}

NIL

我们看这个代码首先会发现这里有一个 NIL 节点，这在 AVL 中是没有的。
NIL 节点的作用是，将 null 包装了起来，同时，为了满足红黑树的黑高相同的定义，为其赋予一个颜色：黑色。
而且整个红黑树都只用一个 NIL 对象，这有两个好处，

一个是不需要开辟额外的内存空间，不然每一个 NIL 都是一个新的对象，那当叶子节点足够多，一个红黑树就会占用极大的内存，而且无法释放。
二是对比起来直接用 == 即可
而我们在写代码的时候，要注意 NIL 节点有以下特性：
NIL 是一个固定存在的节点。整棵树只有一个。
NIL 是黑色的：nil.color = BLACK。
NIL 本身不会再指向任何有效节点，它的 left、right 指针始终都指向自己或 null。
NIL 的 parent 指针在一开始的时候指向自己或者 null，在红黑树变化的过程中会被赋值，但是不会出现混乱或者死循环的问题，具体请看理解红黑树#用 NIL 替代 null 的作用
所有叶子（空子树）的 left 或者 right 指针指向 NIL，而不是 null。
root 节点的 parent 指向 NIL
所以 NIL 节点其实是很简单的，是对问题的一种简化。有很多同学在写代码的时候感觉用 NIL 替代 null 很复杂，其实不是的，抓住以上几点写代码就会觉得很简单。
因此实际上，一个红黑树的实际结构可能是这样的。

为什么叫 NIL

在红黑树（Red-Black Tree）中，NIL 并不是某个词组的缩写，它本身就是一个特殊的术语， 通常表示“空节点”或“哨兵节点”。
传统红黑树的实现（特别是在《算法导论》中）会为每一个叶子节点的子节点使用一个 共享的 NIL 节点，这个节点：

有固定的颜色：黑色
不是 null，而是一个特殊的 Node 对象
避免判断 null，逻辑更统一简洁

在写代码的时候如何注意 NIL

搜索的时候：任何一个子树的根节点（甚至 root 节点）一开始的都是 NIL，当我们迭代树的时候，如果一个节点是 NIL，则表明以这个节点为根节点的额子树是空的，不需要再往下遍历了。
插入的时候：如果你通过遍历查找发现新插入的节点要挂接的父节点是 NIL，说明整个树就是空的，新插入的节点直接就是新的 root 节点
删除的时候：把 NIL 当空节点判断
左旋或者右旋或者移植的时候：当我们查找 parent 的时候，如果 parent 是 NIL，说当前节点就是 root，不再需要进行其 parent 节点的 left 或者 right 指针的设置，如果一个节点是 NIL，我们就不用设置其 parent 节点。

用 NIL 替代 null 的作用

我们在前面提到过 NIL 节点的 parent 指针会在红黑树变换的过程中被赋值，我们这里就来简单看看什么时候会被赋值。
当我们向树中新插入一个节点的时候，我们会初始化这个节点，其 left 和 right 指针默认指向 NIL，但是我们不会将 NIL 的 parent 指向新插入的节点。
树的变换，无非就是变色和旋转还有移植，

变色不涉及到指针修改，
旋转的时候新的顶点需要重新设置 parent，但是新的顶点永远不可能是 NIL，然后还有 T2 节点，其也需要设置 parent，这个 T2 节点可能会为 NIL，不过我们的代码里也写死了，如果其为 NIL，就不设置其父节点。所以旋转也不会设置 NIL 的父节点
移植，有可能，删除一个节点之后，接替他的节点是 NIL 节点，此时我们就会设置 NIL 节点的 parent 指针。移植是我们唯一可能设置 NIL 的 parent 指针的时候。
搜索的时候没有这些变化不用考虑，插入的时候只有旋转没有移植操作，不用考虑，只有删除的时候有移植操作，所以删除可能会更新 NIL 的 parent 指针，
举个例子：

                        2:b(B)                        
              _________|      |_________              
        1:a(R)                          3:c(R)        
      _|      |_                      _|      |_      
NIL(B)          NIL(B)          NIL(B)          NIL(B)

按顺序插入 1、2、3 得到上面的结构，然后删除 3，此时接替 3 的就是其右子节点，也就是 NIL，执行 transplant(z, z.right); 的时候会将 NIL 的 parent 设置为 2 所在的节点。
我们在删除一个节点之后，需要修改删除节点引起的对红黑树 5 条特性的破坏，因此需要调用 fixDelete 方法，此时我们需要以这个接替被删除节点的节点为起点去查找其兄弟节点，因此我们必须知道这个节点的父节点，而 null 是无法保存父节点的，因此，我们别无选择，只能用 NIL 来代替 null，并设置其父节点。这是我们使用 NIL 的根本原因。
那全局使用一个 NIL 节点，任何地方都可能修改 NIL 节点的 parent 指针，会不会出问题，比如会不会出现 parent 指针相互覆盖的情况呢？
不会，为什么？
首先我们分析过了，只有移植才会设置 parent 节点，而且每次的步骤都是先移植，然后再 fixDelete，也就是先设置再使用。
下一次执行删除操作的时候，又会先移植设置 parent 指针，然后再使用 parent 指针。
也就是说只要你做到，每一次都是先设置再使用，而且在你设置这个值之后到你使用之前，没有别人来设置这个值，就不会有问题。NIL 的 parent 指针刚好满足这些条件。

因此我们在旋转的时候，不能设置 nil 节点的 parent。

AVL 树为什么不适用 NIL

主要是因为 AVL 树中，不需要那么复杂的再平衡逻辑，不需要去查找删除之后的接任节点的兄弟节点，因此不需要向上查找，因此不需要将 null 包装成 NIL，

右旋

跟 AVL 树一样（理解AVL树#对左旋函数和右旋函数的理解），牢记关系节点的关系 y>T2>x
同时因为我们需要维护节点的 parent 指针，因此我们有四个对象需要更新，

y 的 parent 的左指针或者右指针
- 如果 y 的 parent 为 NIL，说明 y 是 root，直接把 x 设置为 root 即可，因为 x 就是新的 root
- 如果不是，则将 x 设置 y 的 parent 的对应位置接替 y
y 的 left，和 parent
- left 为 T2
- parent 为 x
x 的 right，和 parent
- right 为 y
- parent 为 y 的 parent ,如果 y 是 root，此时 parent 为 NIL，也照样赋值
T2 的 parent
- 如果 T2 不为 NIL，设置为 y
  写的时候，尽量先把所有需要修改的变量写出来，然后从上到下修改指针，这样不容易出错


/**  
 * Right rotation     
 *     
 * @param y The node to rotate around  
 */    
 private void rightRotate(RedBlackTreeNode<K, V> y) {  

	// 牢记关系 y>T2>x        
	// 我们有四个对象需要更新，  

	// y 的 parent 的左指针或者右指针  
	// 我们需要更新 y 的 left，和 parent        
	// 我们需要更新 x 的 right，和 parent        
	// 我们需要更新 T2 的 parent  
	// 写的时候，尽量先把所有需要修改的变量写出来，然后从上到下修改指针，这样不容易出错  

	RedBlackTreeNode<K, V> p = y.parent;  
	RedBlackTreeNode<K, V> x = y.left;  
	RedBlackTreeNode<K, V> T2 = x.right;  

	if (p == NIL) {  
		root = x;  
	} else {  
		if (y == p.right) {  
			p.right = x;  
		} else {  
			p.left = x;  
		}  
	}  

	x.right = y;  
	x.parent = p;  

	y.parent = x;  
	y.left = T2;  

	if (T2 != NIL) {  
		T2.parent = y;  
	}  
}

左旋

同理解红黑树#右旋，只不过是对称换个方向

移植

移植操作只要用于删除节点的，参数是两个，一个参数是 u，被删除的节点，一个是 v 替代 u 的节点。
我们需要更新两个元素，一个元素是 u 的 parent，一个是 v

让 u 的 parent 的 left 或者 right 指向 v
让 v 的 parent 指向 u
- 注意这里并没有判断 v 是否是 NIL，即使是，也会更新其 parent 指针
  注意，这个方法并没有修改 u，这里只是将指向 u 的指针删除了，u 仍然指向着树中的节点。

查询

二分查找，过程这里就不赘述了

插入

主要看两个方法

insert
fixInsert
insert 方法的逻辑很简单，就是将新节点挂到红黑树上
先通过对比，找到新节点所挂接的父节点
确定挂接到父节点的左边还是右边
- 如果如节点是 NIL，则说明当前树是空的，新插入的节点就是 root
  挂接完之后就开始修复红黑树。fixInsert
  因为新节点是红色的，所以我们只需要修复一种场景，就是其父节点是红色（违反特性 4），如果其父节点是黑色，则没有违反任何一条特性，不需要修复，然后我们就需要看其父节点的兄弟节点，也就是舅舅节点（uncle，用变量 u 表示）
  当前节点用 k 表示
  同时这里只展示 k 的父节点是爷爷节点的右子节点的情况，k 的父节点是爷爷节点的左子节点为镜像场景，这里省略，

场景 1：uncle 是红色

将 k 的父节点跟舅舅节点都设置成黑色，
然后将 k 的父节点的父节点即爷爷节点设置成红色，
然后将爷爷节点设置成新的待检查的节点 k
继续循环转向下一次检查
如图

图 A-S1-1

图 A-S1-2

图 A-S1-3

场景 2：uncle 是黑色，新节点挂载在父节点左侧

将 k 指向 k 的父节点
然后右旋 k 节点
变成理解红黑树#场景 3：uncle 是黑色，新节点挂载在父节点右侧的图 A-S3-1

图 A-S2-1

图 A-S2-2

图 A-S2-3

场景 3：uncle 是黑色，新节点挂载在父节点右侧

将 k 的父节点设置成黑色
将 k 的爷爷节点设置成红色
以 k 的爷爷节点为起点进行左旋
结束

图 A-S3-1

图 A-S3-2

图 A-S3-3

总结

插入的时候，主要看插入节点的父节点（parent）的兄弟节点（uncle）
插入总共三种情况，
情况一不需要旋转，只是更新检查节点，然后再次循环
然后从情况二变到情况三需要一次旋转，情况三再进行一次旋转，插入的 fix 就结束了，因此
红黑树的插入实际上最多只需要 2 次旋转，当然还有无数次的变色，不过变色的代价极低，可以忽略不计

删除

主要看两个方法

delete
deleteNode
fixDelete
delete 的方法很简单，如果通过 key 能找到被删除节点，则进行下一步，否则直接返回
deleteNode 的内容
如果被删除的节点只有一个子节点，则让这个子节点来代替被删除的节点
如果被删除的节点两个子节点，则从右侧中找到最小的子节点代替自己
道理虽然简单但是代码写起来很复杂，假设传入的参数是 z
首先这里确定了两个概念，一个是被删除的节点 y，一个是接替被删除的位置的节点 x，
如果是只有一个子节点，那么被删除的节点就是 z，x 就是它唯一的子节点
但是如果 z 有两个子节点，那么 z 的右子树的最小值，并记录颜色，这里取名 m，就是最终的 y，，m 的右子节点才是 x（因为 m 最小，所以其没有左子节点），
为什么不用考虑 z 呢，因为 m 再被移植到 z 这里的时候，把 m 会把自己的颜色设置为 z 的颜色，也就是说删除 z 然后用 m 替换，对其附近的节点来说，是没有红黑树规则的违反的，因此我么只需要考虑 m 的右子节点接替 m 的位置有没有存在对红黑树规则的违反。
我们根据删除的节点的颜色，判断是否需要进行 fixDelete，如果删除的节点是红色，则不需要进行 fix，因为删除红色节点，不影响红黑树的特性，如果删除的是黑色的节点，才需要进行 fix。

分析红黑树的时候经常能看到这种判断，即因为有了红黑树的规则很松散，插入或者删除节点之后，有的时候是不需要进行操作的，就很省事。

接下来我们来解析 fixDelete 方法。
我们传入接替被删除节点的节点，用 x 表示。兄弟节点用 w 表示。
同时这里只展示 x 为其父节点的左子节点的情况，x 为其父节点的右子节点的情况为镜像场景，这里省略，
这里的操作梳理一下是这样的，首先被删除的节点是黑色的，
如果顶替其的节点 x 是红色的，那么直接将其变黑即可，黑高不变，同时少了一个红节点没关系，x 变红，其子节点也不受影响。直接就结束了
如果顶替其的节点 x 是黑色的，那么就只能通过变换，从 x 的父节点中增加一个黑色节点，或者从 x 的兄弟节点中减少一个黑色节点，来进行平衡
删除一个黑色，继任的也是黑色，那么从 x 开始往下的链路，实际上就少了一个黑色节点（黑高 -1），我们在 fixDelete 中所做的所有的调整，都是为了平衡这个黑高的变化（性质 5）
因此下面这里我们只考虑被删除节点是黑色，同时接替其的节点也是黑色的情况
下面的图中，其中白色球为颜色不确定的节点

场景 1：兄弟节点为红色

将兄弟节点 w 变成黑色
将父节点变成红色
左旋父节点（其实做完以上两部，经过 x 的路径的黑高并没有变化）
根据 x 位置得到新的兄弟节点 w，此时 w 为黑色，进入理解红黑树#场景 2：兄弟节点为黑色，且兄弟节点的两个子节点都是黑色图 D-S2-1
经过变换之后，x 的父节点变黑（经过 x 的路径黑高 +1）
- 这里主要得看 fixDelete 的方法的最后一行代码起作用。

图 D-S1-1

图 D-S1-2

图 D-S1-3

图 D-S1-4

图 D-S1-5

场景 2：兄弟节点为黑色，且兄弟节点的两个子节点都是黑色

直接将 w 变成红色
将 x 的父节点变成新的 x（经过 x 的兄弟节点的路径黑高 -1，但是变换仍未结束）
进入下一个循环

图 D-S2-1

图 D-S2-2

图 D-S2-3

场景 3：兄弟节点为黑色，且兄弟节点的右子节点是黑色

将 w 变成红色
将 w 的左节点变成黑色
右旋 w 节点
以 x 为起点更新 w
进入到理解红黑树#场景 4：兄弟节点为黑色，且兄弟节点的右子节点是红色，所以场景 3 实际上是一个中间状态

图 D-S3-1

图 D-S3-2

图 D-S3-3

图 D-S3-4

场景 4：兄弟节点为黑色，且兄弟节点的右子节点是红色

将 x 的父节点变成黑色
将 x 的父节点的颜色复制给 w
将 w 的右节点的颜色变成黑色
左旋 x 的父节点，（最终经过 x 的路径黑高 +1）
结束

图 D-S4-1

图 D-S4-2

图 D-S4-3

总结

删除主要看删除位置的新节点的兄弟节点以及其子节点
删除删除节点总共需要几次旋转其实简单估算。实战中一般不超过 3。

红黑树的节点的颜色到底代表什么

红黑树的红黑性质实际上是通过颜色，间接控制了树的“高度差异”和“局部不对称性”。

颜色	作用解释
黑色	表示一个路径上的“实质性高度”贡献，限制最长路径。它的存在确保从任意节点到叶子黑节点个数一致（黑高一致）。
红色	表示一种“过渡”状态，允许出现少量局部不平衡（红色节点必须在黑色节点下方）。它减少了每次插入都必须完全重构的需求，从而提高效率。
红色的本质，代表的是红黑树允许的局部出现的不平衡。而红色下面必须是黑色以及黑高必须相同的规则，限制了这种不平衡的范围和这种不平衡对整棵树的最终影响，而因为允许出现局部的不平衡，减少了对树的变换的次数。

颜色带来的优势

如果只有黑节点 → 就像严格平衡的 AVL 树 → 插入/删除成本很高。
有了红节点 → 放宽平衡要求，最多允许路径差翻倍（最长路径最多是最短路径的两倍），但依然保证 O(log n) 高度。
插入/删除操作只需“旋转 + 变色”，不会频繁大范围调整。

颜色可以替代吗？

在一些红黑树的变种中，颜色甚至可以被别的东西代替（如位标记、层级、状态位等），比如：

红黑树的颜色可以实现为 1-bit 状态。
线程中红节点可以代表“还未完成平衡修复”的状态。
所以你可以理解为：
颜色是算法上的“标记”，其核心作用是辅助维护结构平衡，不是某种实际数据。
红黑树的“颜色”并没有物理意义，它是为了辅助维护树的平衡，通过控制红黑规则使得插入和删除操作保持 O(log n) 的时间复杂度。

跟 AVL 树的对比

我们在观察红黑树的插入和删除过程之后，会发现因为红黑树的规则很松散，插入或者删除节点之后，有的时候是不需要进行操作的，就很省事。
AVL 的算法的的逻辑更加简单粗暴，每一个节点的左右子树的高度差不能超过 1，所以它实际上会检查被插入或删除的点到根节点的路径之间的每一个节点。标准简单粗暴，同时检查更加频繁。但是它的树高控制得更好，因此搜索性能稍微好一点，但是插入和删除的性能没有红黑树好。

这也是为什么，我们在进行代码实现的时候，AVL 树的实现推荐用递归来做，但是红黑树的实现，不推荐用递归来做，而是推荐用 while 循环来做，因为红黑树插入和删除的时候不一定会向上更新到根节点。

虽然红黑树不需要考虑平衡度（子树高度差）但是颜色，考虑起来也挺难搞的
树的平衡度是一个简单而又严格的要求

二叉树中的各种变色和旋转，让我意识到，光看代码你是很难反推出作者为什么这么写的，相反，只有当你知道作者为什么写的时候，你才能看懂代码。