本文基于《算法第四版》中红黑树作者Robert Sedgewick的原理讲解及代码实现，从2-3树角度来观察和理解红黑树平衡调整设计动机，源码分析说明基于JDK 1.8版本HashMap，转载请注明出处
概述
RBT（Red Black Tree，红黑树）是一种BST（Balanced Search Tree，平衡二叉搜索树），RBT不是完全平衡二叉树，这导致其树高最小 $\scriptsize O(\lg N)$ 最大 $\scriptsize O(2 \lg N)$ ，即红黑树的的插入和查询性能
红黑树相比于其他BST的优点是 $\scriptsize O(1)$ 平衡维护成本，避免逐层传递的平衡调整，因而被广泛使用
应用
- linux内核CFS进程调度器
- EXT3文件系统
- Java和C++中的Map和Set
性质
- 节点仅红色或仅黑色
- 根节点为黑色
- 叶节点为黑色（NULL也算叶节点）
- 红节点的父、子节点为黑色，黑节点父、子节点可红可黑
- 任一节点为根出发到叶节点的所有路径上黑色节点数（黑高）相同
- RBT中序遍历为升序序列
实现
以Java中的HashMap源码为例
平衡旋转操作
旋转的目的是降低后文中LL和RR型树的高度，使树更平衡。分为左旋与右旋，此处以左旋为例
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) { TreeNode<K,V> r, pp, rl; if (p != null && (r = p.right) != null) { if ((rl = p.right = r.left) != null) // 1 左旋后rl成为p的子节点 rl.parent = p; if ((pp = r.parent = p.parent) == null) // 2 左旋后r替代原p位置，成为root (root = r).red = false; else if (pp.left == p) // 2 左旋后r替代原p位置，成为pp.left pp.left = r; else pp.right = r; // 2 左旋后r替代原p位置，成为pp.right r.left = p; // 3 左旋修改指针 p.parent = r; // 4 左旋修改指针 } return root; }
插入操作
插入节点
根据BST性质找到插入位置
final void treeify(HashMap.Node<K,V>[] tab) { HashMap.TreeNode<K,V> root = null; for (HashMap.TreeNode<K,V> x = this, next; x != null; x = next) { next = (HashMap.TreeNode<K,V>)x.next; x.left = x.right = null; if (root == null) { // 根节点单独处理 x.parent = null; x.red = false; root = x; } else { K k = x.key; int h = x.hash; Class<?> kc = null; for (HashMap.TreeNode<K,V> p = root;;) { // 迭代找到插入位置 int dir, ph; K pk = p.key; if ((ph = p.hash) > h) // 小节点插入位置在左子树 dir = -1; else if (ph < h) // 大节点插入位置在右子树 dir = 1; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) dir = tieBreakOrder(k, pk); HashMap.TreeNode<K,V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { // null为插入位置，否则迭代找子树 x.parent = xp; if (dir <= 0) xp.left = x; // 执行小节点插入左子树 else xp.right = x; // 执行大节点插入右子树 root = balanceInsertion(root, x); // 平衡调整 break; } } } } moveRootToFront(tab, root); }
平衡调整
需要检查插入的新节点是否破坏了RBT性质，若破坏则需要进行平衡调整以保证RBT性质使树平衡。导致不满足RBT性质的原因有三：
- CASE1：分为L型和R型，此处分析L型
- CASE2：分为LR型和RL型，此处分析LR型
- CASE3：分为LL型和RR型，此处分析LL型
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { x.red = true; // 新插节点均视为RED节点 for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { if ((xp = x.parent) == null) { x.red = false; return x; } else if (!xp.red || (xpp = xp.parent) == null) // 红节点才是不平衡原因，黑节点以上均满足RBT性质 return root; // 第一次插入根节点时、向上检查至根节点时全树已平衡 if (xp == (xppl = xpp.left)) { if ((xppr = xpp.right) != null && xppr.red) { // CASE1:L xppr.red = false; xp.red = false; xpp.red = true; x = xpp; } else { if (x == xp.right) { // CASE2:LR root = rotateLeft(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { // CASE3:LL xp.red = false; if (xpp != null) { xpp.red = true; root = rotateRight(root, xpp); } } } } else { if (xppl != null && xppl.red) { // CASE1:R xppl.red = false; xp.red = false; xpp.red = true; x = xpp; } else { if (x == xp.left) { // CASE2:RL root = rotateRight(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { // CASE3:RR xp.red = false; if (xpp != null) { xpp.red = true; root = rotateLeft(root, xpp); } } } } } }
删除操作
删除节点
首先查找到待删节点，再确定合适的子节点替换待删节点，其实就是BST的节点删除，详见下图
待删节点只有左孩子或只有右孩子的情况可取子节点直接替代
但若同时有左右孩子，仍取直接子节点替换的话会带来问题：如取l替换u需要将LR分支插入r子树的L分支，可能会增加树的高度降低查询性能。r替换u同理。不推荐
为了维护BST性质，取l<v<r的节点v替换节点u较为合适。而取r子树的最小节点v时，v只可能有右孩子，此时修改最少；选择lmax同理
r右子树的最小节点就是r本身、或无右孩子时可直接替换待删节点。若不是则说明r右子树的最小节点v还有右子树vr，需要依次执行v替换u、vr替换v
安全地删除红色节点
从2-3树的视角来看，删除红色节点全树仍然保持平衡：
所有红色节点均在3-节点中，删除红色节点仅是将3-节点变为2-节点，2-3树任何子树的高度均未发生变化
从红黑树的视角来看，删除红色节点不改变红黑树的性质：
删除红色节点并不会改变所在路径上的黑色节点数目，即黑高不变
待删红色节点被黑色节点替代时，必然不会引起双红问题
待删红色节点被红色节点替代时，其直接父子节点必为黑色，直接子节点替换时必然不会产生双红，即使替换节点v是红色也不会造成原待删位置u发生双红（下图例3），而红色的替换节点v限制rl和vr必为黑色，其右孩子vr替换v时也不会出现双红（下图例4）
由于红色节点不是根节点，删除红色节点后的替代不是根节点，也没有向根节点的颜色调整，根仍然保持黑色
谨慎地删除黑色节点
从2-3树的视角来看，删除红色节点全树仍然保持平衡：
所有红色节点均在3-节点中，删除红色节点仅是将3-节点变为2-节点，2-3树任何子树的高度均未发生变化
从红黑树的视角来看，删除红色节点不改变红黑树的性质：
删除红色节点并不会改变所在路径上的黑色节点数目，即黑高不变
待删红色节点被黑色节点替代时，必然不会引起双红问题
待删红色节点被红色节点替代时，其直接父子节点必为黑色，直接子节点替换时必然不会产生双红，即使替换节点v是红色也不会造成原待删位置u发生双红（下图例3），而红色的替换节点v限制rl和vr必为黑色，其右孩子vr替换v时也不会出现双红（下图例4）
由于红色节点不是根节点，删除红色节点后的替代不是根节点，也没有向根节点的颜色调整，根仍然保持黑色
平衡调整
case1
case2
case3
case4
参考资料
Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein．Introduction to Algorithms, Third Edition．[M]. 北京:机械工业出版社, 2013. 1
Sedgewick R, Wayne K. Algorithms, Fourth Edition[M]. 4. 人民邮电出版社, 2012.
RedBlackBST – Robert Sedgewick – Princeton University
邓俊辉. 数据结构（C++语言版 第3版）[M]. 3. 清华大学出版社, 2013.