情况3.2：x的父节点为黑色，w的左孩子是红色的
case3.2调整过程如下：
调整说明：同样的，对节点c 进行一次左旋转，将节点w 的右孩子颜色修改为黑色。此时节点c 已经达到平衡，同时节点w 也达到平衡，整棵树已经平衡了！
情况3.3：x的父节点为红色，w的左孩子是黑色的
case3.3调整过程如下：
调整说明：对节点c 进行一次左旋转，将节点 w 的右孩子颜色修改为黑色，同时将节点80 和节点100 颜色进行互换。此时节点c 已经达到平衡，同时节点w 也达到平衡，整棵树已经平衡了！
情况3.4：x的父节点为红色，w的左孩子是红色的
case3.4调整过程如下：
调整说明：同样的，对节点c 进行一次左旋转，将节点 w 的右孩子颜色修改为黑色，同时将节点80 和节点100 颜色进行互换。此时节点c 已经达到平衡，同时节点w 也达到平衡，整棵树已经平衡了！
4）x的兄弟节点w是黑色的，而且w的左孩子是红色的，w的右孩子是黑色的
当x的兄弟节点w是黑色的，而且w的左孩子是红色的，w的右孩子是黑色的，此时也需要分2种情况！
情况4.1：x的父节点为红色
case4.1调整过程如下：
调整说明：对节点w 进行一次右旋转，将节点90和节点100 进行颜色互换，此时节点x 和节点w 的关系变成：x的兄弟节点w是黑色的，并且w的右孩子是红色的。此时按照case3.3情况进行处理即可！
情况4.2：x的父节点为黑色
case4.2调整过程如下：
调整说明：同样的，对节点w 进行一次右旋转，将节点90和节点100进行颜色互换，此时节点x 和节点w 的关系变成：x的兄弟节点w是黑色的，并且w的右孩子是红色的。此时按照case3.1情况进行处理即可！
删除的场景相比插入要多很多，情况也比较复杂，但是基本有自己的规律，我们只需要把规律总结出来，然后就可以用逻辑代码来实现！
需要注意的是：此次节点x 位于节点c 的左子树，如果位于右子树，操作与之对称！
可以得出如下结论：对删除节点后的调整所做的旋转操作不会超过3次！
三、代码实践
接下来，我们从代码层面来定义一下树的实体结构，如下：
public class RBTNode<E extends Comparable<E>> { /**节点颜色*/ boolean color; /**节点关键字*/ E key; /**父节点*/ RBTNode<E> parent; /**左子节点*/ RBTNode<E> left; /**右子节点*/ RBTNode<E> right; public RBTNode(E key, boolean color, RBTNode<E> parent, RBTNode<E> left, RBTNode<E> right) { this.key = key; this.color = color; this.parent = parent; this.left = left; this.right = right; } @Override public String toString() { return "RBTNode{" + "color=" + (color ? "red":"black") + ", key=" + key + '}'; } }
我们创建一个算法类RBTSolution，完整实现如下：
public class RBTSolution<E extends Comparable<E>> { /**根节点*/ public RBTNode<E> root; /** * 颜色常量 false表示红色，true表示黑色 */ private static final boolean RED = false; private static final boolean BLACK = true; /* * 新建结点(key)，并将其插入到红黑树中 * 参数说明：key 插入结点的键值 */ public void insert(E key) { System.out.println("插入[" + key + "]:"); RBTNode<E> node=new RBTNode<E>(key, BLACK,null,null,null); // 如果新建结点失败，则返回。 if (node != null) insert(node); } /* * 将结点插入到红黑树中 * * 参数说明： * node 插入的结点 // 对应《算法导论》中的node */ private void insert(RBTNode<E> node) { int cmp; RBTNode<E> y = null; RBTNode<E> x = this.root; // 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。 while (x != null) { y = x; cmp = node.key.compareTo(x.key); if (cmp < 0) x = x.left; else x = x.right; } node.parent = y; if (y!=null) { cmp = node.key.compareTo(y.key); if (cmp < 0) y.left = node; else y.right = node; } else { this.root = node; } // 2. 设置节点的颜色为红色 node.color = RED; // 3. 将它重新修正为一颗二叉查找树 insertFixUp(node); } /* * 红黑树插入修正函数 * * 在向红黑树中插入节点之后(失去平衡)，再调用该函数； * 目的是将它重新塑造成一颗红黑树。 * * 参数说明： * node 插入的结点 // 对应《算法导论》中的z */ private void insertFixUp(RBTNode<E> node) { RBTNode<E> parent, gparent; // 若“父节点存在，并且父节点的颜色是红色” while (((parent = parentOf(node))!=null) && isRed(parent)) { gparent = parentOf(parent); //若“父节点”是“祖父节点的左孩子” if (parent == gparent.left) { // Case 1条件：叔叔节点是红色 RBTNode<E> uncle = gparent.right; if ((uncle!=null) && isRed(uncle)) { setBlack(uncle); setBlack(parent); setRed(gparent); node = gparent; continue; } // Case 3条件：叔叔是黑色，且当前节点是右孩子 if (parent.right == node) { RBTNode<E> tmp; leftRotate(parent); tmp = parent; parent = node; node = tmp; } // Case 2条件：叔叔是黑色，且当前节点是左孩子。 setBlack(parent); setRed(gparent); rightRotate(gparent); } else { //若“z的父节点”是“z的祖父节点的右孩子” // Case 1条件：叔叔节点是红色 RBTNode<E> uncle = gparent.left; if ((uncle!=null) && isRed(uncle)) { setBlack(uncle); setBlack(parent); setRed(gparent); node = gparent; continue; } // Case 2条件：叔叔是黑色，且当前节点是左孩子 if (parent.left == node) { RBTNode<E> tmp; rightRotate(parent); tmp = parent; parent = node; node = tmp; } // Case 3条件：叔叔是黑色，且当前节点是右孩子。 setBlack(parent); setRed(gparent); leftRotate(gparent); } } // 将根节点设为黑色 setBlack(this.root); } /* * 删除结点(z)，并返回被删除的结点 * * 参数说明： * tree 红黑树的根结点 * z 删除的结点 */ public void remove(E key) { RBTNode<E> node; if ((node = search(root, key)) != null) remove(node); } /* * 删除结点(node)，并返回被删除的结点 * * 参数说明： * node 删除的结点 */ private void remove(RBTNode<E> node) { RBTNode<E> child, parent; boolean color; // 被删除节点的"左右孩子都不为空"的情况。 if ( (node.left!=null) && (node.right!=null) ) { // 被删节点的后继节点。(称为"取代节点") // 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。 RBTNode<E> replace = node; // 获取后继节点 replace = replace.right; while (replace.left != null) replace = replace.left; // "node节点"不是根节点(只有根节点不存在父节点) if (parentOf(node)!=null) { if (parentOf(node).left == node) parentOf(node).left = replace; else parentOf(node).right = replace; } else { // "node节点"是根节点，更新根节点。 this.root = replace; } // child是"取代节点"的右孩子，也是需要"调整的节点"。 // "取代节点"肯定不存在左孩子！因为它是一个后继节点。 child = replace.right; parent = parentOf(replace); // 保存"取代节点"的颜色 color = colorOf(replace); // "被删除节点"是"它的后继节点的父节点" if (parent == node) { parent = replace; } else { // child不为空 if (child!=null) setParent(child, parent); parent.left = child; replace.right = node.right; setParent(node.right, replace); } replace.parent = node.parent; replace.color = node.color; replace.left = node.left; node.left.parent = replace; if (color == BLACK) removeFixUp(child, parent); node = null; return ; } if (node.left !=null) { child = node.left; } else { child = node.right; } parent = node.parent; // 保存"取代节点"的颜色 color = node.color; if (child!=null) child.parent = parent; // "node节点"不是根节点 if (parent!=null) { if (parent.left == node) parent.left = child; else parent.right = child; } else { this.root = child; } if (color == BLACK) removeFixUp(child, parent); node = null; } /* * 红黑树删除修正函数 * * 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数； * 目的是将它重新塑造成一颗红黑树。 * * 参数说明： * node 待修正的节点 */ private void removeFixUp(RBTNode<E> node, RBTNode<E> parent) { RBTNode<E> other; while ((node==null || isBlack(node)) && (node != this.root)) { if (parent.left == node) { other = parent.right; if (isRed(other)) { // Case 1: x的兄弟w是红色的 setBlack(other); setRed(parent); leftRotate(parent); other = parent.right; } if ((other.left==null || isBlack(other.left)) && (other.right==null || isBlack(other.right))) { // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的 setRed(other); node = parent; parent = parentOf(node); } else { if (other.right==null || isBlack(other.right)) { // Case 4: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。 setBlack(other.left); setRed(other); rightRotate(other); other = parent.right; } // Case 3: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。 setColor(other, colorOf(parent)); setBlack(parent); setBlack(other.right); leftRotate(parent); node = this.root; break; } } else { other = parent.left; if (isRed(other)) { // Case 1: x的兄弟w是红色的 setBlack(other); setRed(parent); rightRotate(parent); other = parent.left; } if ((other.left==null || isBlack(other.left)) && (other.right==null || isBlack(other.right))) { // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的 setRed(other); node = parent; parent = parentOf(node); } else { if (other.left==null || isBlack(other.left)) { // Case 4: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。 setBlack(other.right); setRed(other); leftRotate(other); other = parent.left; } // Case 3: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。 setColor(other, colorOf(parent)); setBlack(parent); setBlack(other.left); rightRotate(parent); node = this.root; break; } } } if (node!=null) setBlack(node); } /** * 查询节点 * @param key * @return */ public RBTNode<E> search(E key) { return search(root, key); } /* * (递归实现)查找"红黑树x"中键值为key的节点 */ private RBTNode<E> search(RBTNode<E> x, E key) { if (x==null) return x; int cmp = key.compareTo(x.key); if (cmp < 0) return search(x.left, key); else if (cmp > 0) return search(x.right, key); else return x; } /** * 中序遍历 * @param node */ public void middleTreeIterator(RBTNode<E> node){ if(node != null){ middleTreeIterator(node.left);//遍历当前节点左子树 System.out.println("key:" + node.key); middleTreeIterator(node.right);//遍历当前节点右子树 } } private RBTNode<E> parentOf(RBTNode<E> node) { return node!=null ? node.parent : null; } private boolean colorOf(RBTNode<E> node) { return node!=null ? node.color : BLACK; } private boolean isRed(RBTNode<E> node) { return ((node!=null)&&(node.color==RED)) ? true : false; } private boolean isBlack(RBTNode<E> node) { return !isRed(node); } private void setBlack(RBTNode<E> node) { if (node!=null) node.color = BLACK; } private void setRed(RBTNode<E> node) { if (node!=null) node.color = RED; } private void setParent(RBTNode<E> node, RBTNode<E> parent) { if (node!=null) node.parent = parent; } private void setColor(RBTNode<E> node, boolean color) { if (node!=null) node.color = color; } /* * 对红黑树的节点(x)进行左旋转 * * 左旋示意图(对节点x进行左旋)： * px px * / / * x y * / \ --(左旋)-. / \ # * lx y x ry * / \ / \ * ly ry lx ly * * */ private void leftRotate(RBTNode<E> x) { // 设置x的右孩子为y RBTNode<E> y = x.right; // 将 “y的左孩子” 设为 “x的右孩子”； // 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲” x.right = y.left; if (y.left != null) y.left.parent = x; // 将 “x的父亲” 设为 “y的父亲” y.parent = x.parent; if (x.parent == null) { this.root = y; // 如果 “x的父亲” 是空节点，则将y设为根节点 } else { if (x.parent.left == x) x.parent.left = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子” else x.parent.right = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子” } // 将 “x” 设为 “y的左孩子” y.left = x; // 将 “x的父节点” 设为 “y” x.parent = y; } /* * 对红黑树的节点(y)进行右旋转 * * 右旋示意图(对节点y进行左旋)： * py py * / / * y x * / \ --(右旋)-. / \ # * x ry lx y * / \ / \ # * lx rx rx ry * */ private void rightRotate(RBTNode<E> y) { // 设置x是当前节点的左孩子。 RBTNode<E> x = y.left; // 将 “x的右孩子” 设为 “y的左孩子”； // 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲” y.left = x.right; if (x.right != null) x.right.parent = y; // 将 “y的父亲” 设为 “x的父亲” x.parent = y.parent; if (y.parent == null) { this.root = x; // 如果 “y的父亲” 是空节点，则将x设为根节点 } else { if (y == y.parent.right) y.parent.right = x; // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子” else y.parent.left = x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子” } // 将 “y” 设为 “x的右孩子” x.right = y; // 将 “y的父节点” 设为 “x” y.parent = x; } }
测试代码，如下：
public class RBTClient { public static void main(String[] args) { RBTSolution<Integer> tree = new RBTSolution<Integer>(); //插入节点 System.out.println("========插入元素========"); tree.insert(new Integer(100)); tree.insert(new Integer(85)); tree.insert(new Integer(120)); tree.insert(new Integer(60)); tree.insert(new Integer(90)); tree.insert(new Integer(80)); tree.insert(new Integer(130)); System.out.println("========中序遍历元素========"); //中序遍历 tree.middleTreeIterator(tree.root); System.out.println("========查找key为100的元素========"); //查询节点 RBTNode<Integer> searchResult = tree.search(100); System.out.println("查找结果：" + searchResult); System.out.println("========删除key为90的元素========"); //删除节点 tree.remove(90); System.out.println("========再次中序遍历元素========"); //中序遍历 tree.middleTreeIterator(tree.root); } }
输出结果如下：
========插入元素======== 插入[100]: 插入[85]: 插入[120]: 插入[60]: 插入[90]: 插入[80]: 插入[130]: ========中序遍历元素======== key:60 key:80 key:85 key:90 key:100 key:120 key:130 ========查找key为100的元素======== 查找结果：RBTNode{color=red, key=100} ========删除key为90的元素======== ========再次中序遍历元素======== key:60 key:80 key:85 key:100 key:120 key:130
四、总结
本篇文章，前前后后写了大概一个星期，尤其是删除逻辑，比较复杂，如果有理解不对的地方，欢迎网友们指出！
以下是红黑树总结：
- 1、红黑树是一个基本平衡的二叉树，在查询方面，与二叉查找树思路相同；在插入方面，单次回溯不会超过2次旋转；在删除方面，单次回溯不会超过3次旋转！
- 2、相比于平衡二叉树，红黑树在查询、插入方面，效率差不多；在删除方面，平衡二叉树最多需要
log(n)次变化，以达到严格平衡，而红黑树最多不会超过3次变化，因此效率要高于平衡二叉树！ - 3、在实际应用中，很多语言都实现了红黑树的数据结构，比如 Java 中的 TreeMap、 TreeSet，以及 jdk1.8 中的 HashMap！
