一、红黑树比较重要的特性
1、红黑树每个节点要么是黑色、要么是红色
2、根节点是黑色
3、红色节点的所有儿子都是黑色节点（也就是说从根节点到叶子结点的路径上不能出现连续的红色节点）
4、从根节点到叶子结点的每一条路径上拥有相同的黑色节点个数
n个节点的红黑树的最大深度不超过2log(n+1)，其首先是一颗查找树，其次是平衡树的一个变种。其具有o(logn)的插入删除操作复杂度，操作性能比较好，java的TreeSet、TreeMap就是红黑树的实现，jdk1.8开始HashMap、ConcurrentHashMap在链表长度超过8时也会转而使用红黑树进行数据的维护，红黑树应用十分广泛。
二、红黑树的插入操作
对红黑树的插入操作主要分为两个部分，因为其本身是一颗二叉搜索树，所以首先要按照二叉搜索树进行插入，插入的元素默认红色。
插入后的第二阶段就是进行调整，使得插入后的的二叉树仍然符合红黑树，这种调整fixup包括两个方面（一方面是颜色调整，一方面是旋转调整）
对于插入操作的调整可以分为六种case，其中两两镜像，可以分为三类：
case1：父节点红色+叔叔节点也是红色
在这种情况下将父节点与叔叔节点的颜色全部调整为黑色，为了保证黑色节点数不变，将祖父节点调整为红色，此时有可能祖父节点与曾祖父节点都为红色，所以要上滤，也就是将当前节点设置为祖父节点，再接着进行调整。
case2：父节点是红色，叔叔节点是黑色，当前结点是父节点的右子节点，构成之字形
在这种情况下将父节点进行左旋转变成右边这种情况，当前还是存在连续的红色节点，还需要调整，这就是接下来的case3
case3：父节点是红色，叔叔节点是黑色，且当前结点是父节点的左子节点
在这种情况下将父节点设置为黑色，将祖父节点设置为红色，并且将祖父节点进行右旋转，得到右边的图，此时最上面的节点是左图中的父节点为黑色，不会再出现连续两个红色节点的情况。
场景描述fixupcase1父节点红+叔叔节点红将父节点、叔叔节点全部设置为黑色，将祖父节点设置为红色，将当前节点设置为祖父节点进行上滤case2父节点红+叔叔节点黑+当前结点是父节点的右子节点将父节点进行左旋变成case3再进行处理case3父节点红+叔叔节点黑+当前结点是父节点的左子节点将父节点设置为黑色，将祖父节点设置为红色，将祖父节点进行右旋转
三、红黑树的删除
红黑树的删除与插入一样也分为两个部分，首先与二叉搜索树一样进行删除，删除分为几种情况，删除的节点有左右子树的情况下在右子树中找到要删除的节点的后继节点，并将后继节点的值赋值给要删除节点，然后转移到删除后继节点上，后继节点此时一定要么只拥有右子树，要么没有子树，此时的删除就比较简单了，直接去掉该节点，并将该节点的子节点链接上。
第二步就是进行调整修复，使得删除之后的新树满足红黑树，具体的修复包括颜色调整与旋转操作，如果删除的节点是红色节点则直接不用修复，因为删除的红色节点对红黑树没有直接影响，如果删除的是黑色节点，那么链的路径上就少了一个黑色节点，那么在其子节点上增加一个黑色属性（空节点也增加），由于红黑树的定义中一个节点要么是黑色要么是红色，所以这违背了定义，还需要进一步进行调整，调整主要分8种情况，其中两两镜像，所以最终可以总结为4种case：
case1：当前结点是黑色节点，当前节点的兄弟节点是红色节点
在这种情况下将父节点设置为红色，将兄弟节点设置为黑色，并将父节点进行左旋转得到右边这种情况，而右边是接下来要讨论的case2、case3、case4中的一种。
case2：兄弟节点是黑色，兄弟节点的左右子树都是黑色
将兄弟节点设置为红色，并将加黑的属性上滤到父节点，接着将父节点作为当前节点继续。
case3：兄弟节点是黑色，兄弟节点的左子节点是红色
将兄弟节点设置为红色，将兄弟节点的左子节点设置为黑色，并将兄弟节点右旋转，此时变成了case4
case4：兄弟节点黑色，兄弟节点的右子节点是红色
将兄弟节点设置为父节点的颜色，将父节点设置为黑色，将兄弟节点的右子节点设置为黑色，并将父节点左旋转，结束
场景描述fixupcase1兄弟节点是红色将兄弟节点设置为黑色，将父节点设置为红色，并将父节点左旋转变成case2、case3、case4中的一种case2兄弟节点是黑色，兄弟节点的两个子节点都是黑色（空节点默认是黑色）将兄弟节点设置为红色，将加黑的属性上滤到父节点，也就是设置新的当前结点是父节点，继续case3兄弟节点是黑色，兄弟节点的左子节点是红色将兄弟节点设置为红色，将兄弟节点的左子节点设置为黑色，将兄弟节点进行右旋转变成case4的情况case4兄弟节点是黑色，兄弟节点的右子节点是红色将兄弟节点设置为父节点的颜色，将父节点设置为黑色，将兄弟节点的右子节点设置为黑色，将父节点进行左旋转，结束
四、实现代码
package com.hust517.review; /** * Created by liuwenlong on 2019/5/21. */ public class RedBlackTree<T extends Comparable<? super T>> { private static class RedBlackNode<T> { T val; RedBlackNode<T> left; RedBlackNode<T> right; RedBlackNode<T> parent; int color; RedBlackNode(T val, RedBlackNode<T> left, RedBlackNode<T> right, RedBlackNode<T> parent, int color) { this.val = val; this.left = left; this.right = right; this.parent = parent; this.color = color; } RedBlackNode(T val, RedBlackNode<T> left, RedBlackNode<T> right, RedBlackNode<T> parent) { this(val, left, right, parent, BLACK); } } private static final int BLACK = 0; private static final int RED = 1; // 根节点 private RedBlackNode<T> root; private void setColor(RedBlackNode<T> node, int color) { node.color = color; } private int color(RedBlackNode<T> node) { return node == null ? BLACK : node.color; } private void setParent(RedBlackNode<T> node, RedBlackNode<T> parent) { node.parent = parent; } private void setLeft(RedBlackNode<T> node, RedBlackNode<T> left) { node.left = left; } private void setRight(RedBlackNode<T> node, RedBlackNode<T> right) { node.right = right; } private RedBlackNode<T> parent(RedBlackNode<T> node) { return node.parent; } private RedBlackNode<T> left(RedBlackNode<T> node) { return node.left; } private RedBlackNode<T> right(RedBlackNode<T> node) { return node.right; } private void setRoot(RedBlackNode<T> root) { this.root = root; } /* 左旋 */ private void leftRoate(RedBlackNode<T> node) { RedBlackNode<T> k1 = node; RedBlackNode<T> parent = parent(k1); RedBlackNode<T> k2 = right(k1); setRight(k1, left(k2)); setLeft(k2, k1); if(parent == null) { setRoot(k2); }else { if(right(parent) == k1) { setRight(parent, k2); }else { setLeft(parent, k2); } } setParent(k2, parent); setParent(k1, k2); } /* 右旋 */ private void rightRoate(RedBlackNode<T> node) { RedBlackNode<T> k1 = node; RedBlackNode<T> parent = parent(k1); RedBlackNode<T> k2 = left(k1); setLeft(k1, right(k2)); setRight(k2, k1); if(parent == null) { setRoot(k2); }else { if(right(parent) == k1) { setRight(parent, k2); }else { setLeft(parent, k2); } } setParent(k2, parent); setParent(k1, k2); } /* 插入操作 */ public void insert(T val) { RedBlackNode<T> node = new RedBlackNode<T>(val, null, null, null); insert(node); } private void insert(RedBlackNode<T> node) { if(node == null) { return; } // 如果root为空 if(root == null) { setRoot(node); return; } // 找到插入位置 RedBlackNode<T> child = root; RedBlackNode<T> parent = root; while(child != null) { parent = child; if(child.val.compareTo(node.val) < 0) { child = child.right; }else if(child.val.compareTo(node.val) > 0) { child = child.left; }else { // 已经存在 throw new RuntimeException("元素已经存在"); } } if(node.val.compareTo(parent.val) < 0) { setLeft(parent, node); }else { setRight(parent, node); } setParent(node, parent); setColor(node, RED); // 进行红黑树修正 if(color(parent) == RED) { insertFixup(node); } } /* 修正分三种情况，两种镜像 */ private void insertFixup(RedBlackNode<T> node) { RedBlackNode<T> parent = parent(node); RedBlackNode<T> grand = parent(parent); RedBlackNode<T> uncle; while(node != root && color(parent) == RED) { // 镜像1 if(left(grand) == parent) { uncle = right(grand); // case1 if(color(uncle) == RED) { setColor(grand, RED); setColor(parent, BLACK); setColor(uncle, BLACK); node = grand; parent = parent(node); }else { // case2，最终回到case3 if(right(parent) == node) { // 将进行左旋 leftRoate(parent); // 改变当前结点 node = parent; // 更新parent parent = parent(node); } // case3 setColor(parent, BLACK); setColor(grand, RED); rightRoate(grand); node = root; } }else { // 镜像2 uncle = left(grand); // case1 if(color(uncle) == RED) { setColor(grand, RED); setColor(uncle, BLACK); setColor(parent, BLACK); node = grand; }else { // case2 if(left(parent) == node) { // 右旋 rightRoate(parent); node = parent; parent = parent(node); } // case3 setColor(grand, RED); setColor(parent, BLACK); leftRoate(grand); node = root; } } } // 直接设置根为黑色 setColor(root, BLACK); } /* 删除 */ public void remove(T val) { RedBlackNode<T> temp = root; while(temp != null) { if(temp.val.compareTo(val) > 0) { temp = left(temp); }else if(temp.val.compareTo(val) < 0) { temp = right(temp); }else { break; } } if(temp == null) { throw new RuntimeException("没有该元素"); } remove(temp); } private void remove(RedBlackNode<T> node) { if(node == null) { return; } // 要删除的节点有左右子节点 if(left(node) != null && right(node) != null) { // 找到后继节点 RedBlackNode<T> replacer = findMin(right(node)); node.val = replacer.val; // 删除replacer remove(replacer); }else { RedBlackNode<T> parent = parent(node); RedBlackNode<T> child = right(node) != null ? right(node) : left(node); // 如果删除的是根节点 if(parent == null) { setRoot(child); // 根节点为黑色 if(root != null) { setColor(root, BLACK); } return; } if(child != null) { setParent(child, parent); } if(left(parent) == node) { setLeft(parent, child); }else { setRight(parent, child); } if(color(node) == BLACK) { removeFixup(child, parent); } } } private void removeFixup(RedBlackNode<T> node, RedBlackNode<T> parent) { // 两种镜像四种case RedBlackNode<T> brother; while((node == null) || (color(node) == BLACK && node != root)) { if(left(parent) == node) { brother = right(parent); // case1 变成其他case if(color(brother) == RED) { setColor(parent, RED); setColor(brother, BLACK); leftRoate(parent); // 新的brother brother = right(parent); } // case2 if(color(left(brother)) == BLACK && color(right(brother)) == BLACK) { setColor(brother, RED); // 改变当前node node = parent; parent = parent(node); }else { // case3转化为case4 if(color(left(brother)) == RED) { setColor(brother, RED); setColor(left(brother), BLACK); rightRoate(brother); brother = right(parent); } // case4 setColor(brother, color(parent)); setColor(parent, BLACK); setColor(right(brother), BLACK); leftRoate(parent); node = root; } }else { brother = left(parent); // case1转化为case2、3、4 if(color(brother) == RED) { setColor(parent, RED); setColor(brother, BLACK); rightRoate(parent); brother = left(parent); } // case2 if(color(left(brother)) == BLACK && color(right(brother)) == BLACK) { setColor(brother, RED); node = parent; parent = parent(node); }else { // case3转化为case4 if(color(right(brother)) == RED) { setColor(brother, RED); setColor(right(brother), BLACK); leftRoate(brother); brother = left(parent); } // case4 setColor(brother, color(parent)); setColor(parent, BLACK); setColor(left(brother), BLACK); rightRoate(parent); node = root; } } } setColor(node, BLACK); } private RedBlackNode<T> findMin(RedBlackNode<T> node) { RedBlackNode<T> parent = node; while(node != null) { parent = node; node = left(node); } return parent; } /* 前序遍历，为了方便观察最终代码的正确性，遍历时也输出了颜色信息 */ public void preorder() { preorder(root); } private void preorder(RedBlackNode<T> node) { // 递归终止 if(node == null) { return; } System.out.println("val: " + node.val + ", color: " + color(node)); preorder(left(node)); preorder(right(node)); } /* 中序遍历 */ public void inorder() { inorder(root); } private void inorder(RedBlackNode<T> node) { if(node == null) { return; } inorder(left(node)); System.out.println("val: " + node.val + ", color: " + color(node)); inorder(right(node)); } /* 后序遍历 */ public void postorder() { postorder(root); } private void postorder(RedBlackNode<T> node) { if(node == null) { return; } postorder(left(node)); postorder(right(node)); System.out.println("val: " + node.val + ", color: " + color(node)); } // 插入case1测试 public static void test1() { RedBlackTree<Integer> tree = new RedBlackTree<>(); tree.insert(6); tree.insert(4); tree.insert(10); tree.insert(2); tree.insert(5); System.out.println("****************前序*******************"); tree.preorder(); System.out.println("****************中序*******************"); tree.inorder(); } // 插入case1测试 public static void test2() { RedBlackTree<Integer> tree = new RedBlackTree<>(); tree.insert(6); tree.insert(4); tree.insert(10); tree.insert(2); tree.insert(5); tree.insert(3); System.out.println("****************前序*******************"); tree.preorder(); System.out.println("****************中序*******************"); tree.inorder(); } // 删除case3、case4测试 public static void test3() { RedBlackTree<Integer> tree = new RedBlackTree<>(); tree.insert(6); tree.insert(4); tree.insert(10); tree.insert(2); tree.insert(5); tree.insert(3); tree.remove(4); System.out.println("****************前序*******************"); tree.preorder(); System.out.println("****************中序*******************"); tree.inorder(); } // 删除case2测试 public static void test4() { RedBlackTree<Integer> tree = new RedBlackTree<>(); tree.insert(6); tree.insert(4); tree.insert(10); tree.insert(2); tree.insert(5); // 删除case2 tree.remove(4); System.out.println("****************前序*******************"); tree.preorder(); System.out.println("****************中序*******************"); tree.inorder(); } // 插入case2、case3测试 public static void test5() { RedBlackTree<Integer> tree = new RedBlackTree<>(); tree.insert(6); tree.insert(4); tree.insert(10); tree.insert(2); tree.insert(5); tree.remove(4); tree.insert(3); System.out.println("****************前序*******************"); tree.preorder(); System.out.println("****************中序*******************"); tree.inorder(); } // 删除case1、case2测试 public static void test6() { RedBlackTree<Integer> tree = new RedBlackTree<>(); tree.insert(6); tree.insert(4); tree.insert(10); tree.insert(2); tree.insert(5); tree.insert(3); tree.remove(10); System.out.println("****************前序*******************"); tree.preorder(); System.out.println("****************中序*******************"); tree.inorder(); } // 删除根节点测试 public static void test7() { RedBlackTree<Integer> tree = new RedBlackTree<>(); tree.insert(6); tree.insert(4); tree.remove(6); System.out.println("****************前序*******************"); tree.preorder(); System.out.println("****************中序*******************"); tree.inorder(); } public static void main(String[] args) { // test1(); // test2(); // test3(); // test4(); // test5(); // test6(); test7(); } }
