前提了解

• B树、2-3树、2-3-4树
• 二叉搜索树、平衡二叉树
• Robert Sedgewick原论文
• Robert Sedgewick论文翻译和解释

红黑树和平衡多叉树的对应关系

• 黑链接相当于2-节点
• 一边红链接相当于3-节点
• 两边红链接相当于4-节点
• 红链接与红节点是等效的（链接是节点的内部属性，表示父节点对其的指向）

左倾红黑树

根据Robert Sedgewick原论文的定义：左倾红黑树指3-节点向左倾斜的红黑树，其具有2种形式

• 基于自顶向下2-3-4树的左倾红黑树
• 基于2-3树的左倾红黑树

具有以下特性

• 不能出现向右倾斜的红链接
• 从根到叶节点不包含两条连续的红色链接
• 从根到叶节点的每条路径拥有相同的黑色链接数量

基于自顶向下2-3-4树的左倾红黑树

向左倾斜的要求决定了红黑树和 2-3-4 树之间一对一的对应关系，从而减少了要考虑的情况

自底向上：指插入4-叶子节点后开始分裂，并将中间值传给父节点，如果其父节点也是4-节点，继续向上分裂，直到到达根节点，如果根节点也是4-节点，分裂后树的高度+1，如下图

自顶向下：从根节点到插入所在的叶子节点路径上，遇到4-节点就将其分裂，这样确保了最后到达的叶子节点必然是2-或者3-节点，搜索路径上不存在4-节点，如下图

基于2-3树的左倾红黑树

向左倾斜的要求决定了红黑树和 2-3 树之间一对一的对应关系，从而减少了要考虑的情况

重要代码

下面代码图片来源于原论文

左右旋转变色

当出现向右倾斜的红链接或两个连续的红链接时需要旋转变色

翻转变色

当左右都是红链接时，需要翻转变色，若翻转到根节点，则黑链高度增加

• 对于2-3左倾红黑树来说，相当于分裂生成的4-节点
• 对于2-3-4左倾红黑树来说，相当于分裂遇到的4-节点
  

向2-3左倾红黑树插入

向2-节点插入，插入左边直接插入，插入右边需左旋（因为不能出现向右倾斜的红链接），相当于将2-节点变成了3-节点

向3-节点插入，插入左中位置，需要旋转调整（因为不能两条连续的红色链接），此时左右两边都有红链接，已无法通过旋转调整，相当于将3-节点变成了4-节点，然后通过翻转变色分裂生成的4-节点

可以看到是先旋转变色调整，再判断是否需要翻转变色

向2-3-4左倾红黑树插入的额外情况

向2节点插入同2-3树，但向3-节点插入，3-节点变成4-节点，即两边红链

如果出现4-节点，下次插入搜索时将拆分4-节点（就不会出现向4-节点添加元素的情况），当其父节点为2-节点时，根据自顶向下的规则，分裂遇到的4-节点，传递中间值给父节点，父节点变成3-节点，问题转为插入2-节点，即先翻转变色再判断是否需要旋转变色

如下同理，只不过4-节点的父节点是3-节点的情况

插入代码

根据上面对2-3左倾红黑树和2-3-4左倾红黑树的分析，作者给出了插入的代码

将两边红链接翻转的那行代码放到前面是自顶向下的2-3-4左倾红黑树，放到后面是2-3左倾红黑树

2-3左倾红黑树删除最小值的情况

在2-3树的删除讨论中，只有当待删除元素为3-叶节点或待删除元素的父节点为3-节点时不影响树平衡

• 前者直接删除，如下图
  
• 后者将3-节点重新分配或合并成2-节点，如下图
  
  对应到红黑树，删除要保持平衡，需要保证待删除元素节点为红链接或其父节点为红链接，其对立面是待删除元素节点和父节点都是黑链接，为了消除这个情况，原论文采用了一个非常极端的方法，将左搜索路径的连续黑链接都翻转变色，即代码中的 if (!isRed(h.left) && !isRed(h.left.left))及flipsColors()
  
  flipsColors()的操作会导致：
• 引入连续的左左红色链接（如插入60-50-70-40-55-80-90-30，删除30，会导致50和40红）
• 引入左右红色链接（如插入60-50-70-40-55-80-90，删除40，会导致50和70红）
• 引入单右红色链接（如插入60-50-70，删除50，会导致70红）
• 引入左右红色链接导致的连续右左红色链接（如插入60-50-70-40-55-80-90-53，删除40，会导致55和53红）

前三种情况刚好对应2-3树插入时的修正代码，即fixup()，可在递归回调时修正

最后一种情况遇到时应该立马修正，即代码中的 isRed(h.right.left)，原论文中给了示例，如下图

2-3-4左倾红黑树删除最小值的额外情况

上面的说法对于2-3-4树更广义的描述应该是不能出现两个连续的2-节点，因为可能会导致合并和递归合并

故if (!isRed(h.left) && !isRed(h.left.left))及flipsColors()对于2-3-4树也是适用的

细心的人可能发现，在2-3-4左倾红黑树可能多出现另一种情况，这在原论文没有给出，即右边左右红色链接，这需要更多的旋转操作

2-3左倾红黑树删除最大值的情况

同理，只有当待删除元素为3-叶节点或待删除元素的父节点为3-节点时不影响树平衡，反映到红黑树需要保证待删除元素节点为红链接或其父节点为红链接，其对立面是待删除元素节点和父节点都是黑链接，即不能出现连续的2-节点

按照删除最小值的方式将右搜索路径的连续黑链接都翻转变色，但当其左链接为红色时，其本身就是3-节点，需要对其右旋恢复，故只有当其左连接不为红才需要翻转，即代码中的!isRed(h.right) && !isRed(h.right.left)和flipColors()

同理flipsColors()的操作会导致：

• 引入单左红色链接（如插入60-50-70，删除70，会导致50红）
• 引入左右红色链接（如插入60-50-70-40-55-80-90，删除90，会导致50和70红）
• 引入左右红色链接导致的右右红色连续链接（如插入60-50-70-40-55-80-90-100，删除100，会导致70和90红）
• 引入左右红色链接导致的右左红色连续链接（如插入60-50-70-40-55-80-90-75，删除90，会导致80和75红）

第一种情况不用管，第二三种情况将在fixUp()中修复，第四种情况在遇到后要立即修复，即代码中的isRed(h.left.left)

2-3-4左倾红黑树删除最大值的额外情况

在2-3-4左倾红黑树可能多出现另一种情况，即左边为左右红色链接，如下图，其变换步骤一样，不需要额外的代码

2-3和2-3-4左倾红黑树删除一般情况

要理解删除一般情况的代码，必须充分理解删除最大最小值的代码，尤其是为什么不能出现连续的2-节点，关于这点，可以再看看这篇 https://www.freesion.com/article/4026432302/#Key_398

2-3左倾红黑树完整代码

原论文代码是运行不了的，为了测试对原论文进行了一些修改，但关键代码是一样的

class LL23RB<Key extends Comparable<Key>, Value> {private static final boolean RED = true;private static final boolean BLACK = false;private Node root;private class Node {private Key key;private Value value;private Node left, right;private boolean color;Node(Key key, Value value) {this.key = key;this.value = value;this.color = RED;}}public Value search(Key key) {Node searchNode = searchNode(root, key);if (searchNode != null) {return searchNode.value;}return null;}private Node searchNode(Node node, Key key) {Node x = node;while (x != null) {int cmp = key.compareTo(x.key);if (cmp == 0) return x;else if (cmp < 0) x = x.left;else if (cmp > 0) x = x.right;}return null;}public void insert(Key key, Value value) {root = insert(root, key, value);root.color = BLACK;}private Node insert(Node node, Key key, Value value) {if (node == null) return new Node(key, value);int cmp = key.compareTo(node.key);if (cmp == 0) node.value = value;else if (cmp < 0) node.left = insert(node.left, key, value);else node.right = insert(node.right, key, value);node = fixUp(node);return node;}private boolean isRed(Node node) {if (node == null) {return false;}return node.color == RED;}private Node fixUp(Node node) {if (isRed(node.right) && !isRed(node.left)) node = rotateLeft(node);if (isRed(node.left) && isRed(node.left.left)) node = rotateRight(node);if (isRed(node.left) && isRed(node.right)) flipColors(node);return node;}private Node rotateLeft(Node h) {Node x = h.right;h.right = x.left;x.left = h;x.color = h.color;h.color = RED;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;return x;}private void flipColors(Node h) {h.color = !h.color;h.left.color = !h.left.color;h.right.color = !h.right.color;}public void deleteMin() {root = deleteMin(root);root.color = BLACK;}private Node deleteMin(Node h) {if (h.left == null) return null;if (!isRed(h.left) && !isRed(h.left.left))h = moveRedLeft(h);h.left = deleteMin(h.left);return fixUp(h);}private Node moveRedLeft(Node h) {flipColors(h);if (isRed(h.right.left)) {h.right = rotateRight(h.right);h = rotateLeft(h);flipColors(h);}return h;}public void deleteMax() {root = deleteMax(root);root.color = BLACK;}private Node deleteMax(Node h) {if (isRed(h.left)) {h = rotateRight(h);}if (h.right == null) {return null;}if (!isRed(h.right) && !isRed(h.right.left)) {h = moveRedRight(h);}h.right = deleteMax(h.right);return fixUp(h);}private Node moveRedRight(Node h) {flipColors(h);if (isRed(h.left.left)) {h = rotateRight(h);flipColors(h);}return h;}public void delete(Key key) {root = delete(root, key);root.color = BLACK;}private Node min(Node node) {if (node == null) {return null;}Node current = node;while (current.left != null) {current = current.left;}return current;}private Value get(Node node, Key key) {Node searchNode = searchNode(node, key);if (searchNode != null) {return searchNode.value;}return null;}private Node delete(Node h, Key key) {if (key.compareTo(h.key) < 0) {if (!isRed(h.left) && !isRed(h.left.left))h = moveRedLeft(h);h.left = delete(h.left, key);} else {if (isRed(h.left))h = rotateRight(h);if (key.compareTo(h.key) == 0 && (h.right == null))return null;if (!isRed(h.right) && !isRed(h.right.left))h = moveRedRight(h);if (key.compareTo(h.key) == 0) {h.value = get(h.right, min(h.right).key);h.key = min(h.right).key;h.right = deleteMin(h.right);} else h.right = delete(h.right, key);}return fixUp(h);}private void innerMidOrderTraversal(Node node) {if (node == null) {return;}innerMidOrderTraversal(node.left);System.out.print("[" + node.key + "-" + node.value + "]");if (node.color) {System.out.print("r" + " ");} else {System.out.print("b" + " ");}innerMidOrderTraversal(node.right);}@NonNull@Overridepublic String toString() {System.out.print("中序遍历: ");innerMidOrderTraversal(root);return "";}
}

2-3-4左倾红黑树完整代码

相比于2-3左倾红黑树代码，修改了insert()、moveRedLeft()部分

class LL234RB<Key extends Comparable<Key>, Value> {private static final boolean RED = true;private static final boolean BLACK = false;private Node root;private class Node {private Key key;private Value value;private Node left, right;private boolean color;Node(Key key, Value value) {this.key = key;this.value = value;this.color = RED;}}public Value search(Key key) {Node searchNode = searchNode(root, key);if (searchNode != null) {return searchNode.value;}return null;}private Node searchNode(Node node, Key key) {Node x = node;while (x != null) {int cmp = key.compareTo(x.key);if (cmp == 0) return x;else if (cmp < 0) x = x.left;else if (cmp > 0) x = x.right;}return null;}public void insert(Key key, Value value) {root = insert(root, key, value);root.color = BLACK;}private Node insert(Node h, Key key, Value value) {if (h == null) return new Node(key, value);if (isRed(h.left) && isRed(h.right)) flipColors(h);int cmp = key.compareTo(h.key);if (cmp == 0) h.value = value;else if (cmp < 0) h.left = insert(h.left, key, value);else h.right = insert(h.right, key, value);if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);return h;}private Node rotateLeft(Node h) {Node x = h.right;h.right = x.left;x.left = h;x.color = h.color;h.color = RED;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;return x;}private void flipColors(Node h) {h.color = !h.color;h.left.color = !h.left.color;h.right.color = !h.right.color;}private boolean isRed(Node node) {if (node == null) {return false;}return node.color == RED;}public void deleteMin() {root = deleteMin(root);root.color = BLACK;}private Node deleteMin(Node h) {if (h.left == null) return null;if (!isRed(h.left) && !isRed(h.left.left))h = moveRedLeft(h);h.left = deleteMin(h.left);return fixUp(h);}private Node moveRedLeft(Node h) {flipColors(h);if (isRed(h.right.left)) {if (isRed(h.right.right)) {//这是2-3-4树额外的情况，不能复用代码，因为旋转时修改了hh.right = rotateRight(h.right);h = rotateLeft(h);h = rotateLeft(h);h.left = rotateRight(h.left);flipColors(h);} else {h.right = rotateRight(h.right);h = rotateLeft(h);flipColors(h);}}return h;}private Node moveRedRight(Node h) {flipColors(h);if (isRed(h.left.left)) {h = rotateRight(h);flipColors(h);}return h;}public void deleteMax() {root = deleteMax(root);root.color = BLACK;}private Node deleteMax(Node h) {if (isRed(h.left)) {h = rotateRight(h);}if (h.right == null) {return null;}if (!isRed(h.right) && !isRed(h.right.left)) {h = moveRedRight(h);}h.right = deleteMax(h.right);return fixUp(h);}private Node fixUp(Node node) {if (isRed(node.right) && !isRed(node.left)) node = rotateLeft(node);if (isRed(node.left) && isRed(node.left.left)) node = rotateRight(node);if (isRed(node.left) && isRed(node.right)) flipColors(node);return node;}public void delete(Key key) {root = delete(root, key);root.color = BLACK;}private Node min(Node node) {if (node == null) {return null;}Node current = node;while (current.left != null) {current = current.left;}return current;}private Value get(Node node, Key key) {Node searchNode = searchNode(node, key);if (searchNode != null) {return searchNode.value;}return null;}private Node delete(Node h, Key key) {if (key.compareTo(h.key) < 0) { //处理向左搜索路径的情况，避免连续的2-节点if (!isRed(h.left) && !isRed(h.left.left))h = moveRedLeft(h);h.left = delete(h.left, key);       //向左走} else {            //处理向右和相等的情况if (isRed(h.left))             //若当前是3-节点，则先右旋恢复h = rotateRight(h);if (key.compareTo(h.key) == 0 && (h.right == null)) //处理删除根节点或叶节点的情况，如60-50删除60return null;if (!isRed(h.right) && !isRed(h.right.left))    //处理向右搜索路径的情况，避免连续的2-节点h = moveRedRight(h);if (key.compareTo(h.key) == 0) {        //处理删除的是内部节点的情况，用后继节点键值替代，转为删除后继节点h.value = get(h.right, min(h.right).key);h.key = min(h.right).key;h.right = deleteMin(h.right);} else h.right = delete(h.right, key);     //向右走}return fixUp(h);    //递归回调时消除生成的右红链接和左右红链接}private void innerMidOrderTraversal(Node node) {if (node == null) {return;}innerMidOrderTraversal(node.left);System.out.print("[" + node.key + "-" + node.value + "]");if (node.color) {System.out.print("r" + " ");} else {System.out.print("b" + " ");}innerMidOrderTraversal(node.right);}@NonNull@Overridepublic String toString() {System.out.print("中序遍历: ");innerMidOrderTraversal(root);return "";}
}