红黑树是 2-3 树的一种简易实现方式，它拥有两种链接，红链接和黑链接。
黑链接是普通的二叉查找树链接，红链接表示了一个 3-节点
在这里，我们使用的是左斜的红黑树 ，它满足以下条件：
红链接永远在左边（向左倾斜） 一个节点不能同时链接两个红链接 红黑树是完美黑链接平衡的 需要注意的是，如果红黑树满足以上条件，那么其和 2-3 树就是等价的。
为了表示链接的颜色，我们需要定义一个新的节点，或者说向原有节点增加新的属性——颜色。
1 2 3 4 5 6 pravite class Node Key key; Value val; int N; boolean color; }
在这里，我们为原有的节点增加一个布尔值来表示指向它的链接的颜色 ，这样定义能省去一些麻烦，具体在下面的内容中会讨论到。
当我们往红黑树插入节点时，需要进行一些变形 来让红黑树满足以上条件，就像我们对 2-3 树插入节点时做的处理一样。
第一个重要的变形是旋转变形 。红色的右链接 ，或者两个连续的红链接 等。
由图可以注意到，所谓的旋转 主要做了两件事：
交换根节点 将中间子树调换父亲 剩下就是转换颜色，修改子树节点数目等。
1 2 3 4 5 6 7 8 9 10 11 12 13 Node rotateLeft (Node h) { Node x = h.right; h.right = x.left; x.left = h; x.color = h.color; h.color = RED; x.N = h.N; h.N = 1 + size(h.left) + size(h.right); return x; }
注意，我们采用了和二叉查找树一样的递归返回引用 的方法，这样有利于重用原有代码和维护树的链接性。
这个方法和向左旋转大同小异，核心的思想就是转换根节点和中间子树。
关于必要性：有些时候遇到复杂的红链接情况，就首先要将连接向右旋转，随后在进行其他变形操作。
虽然红黑树条件中不允许红色右链接的存在使得此方法显得无意义，但是此方法的用意在于构建一个便于处理的中间状态 。
当我们在进行旋转的过程中，很可能会遇到两个子节点的链接都是红色 的情况。
由于红链接代表了 3-节点，显然 2 个红链接就代表了一个 4-节点，在 2-3 树插入中，我们需要将临时的 4-节点 分裂 ，在红黑树中就是第二种变形——颜色转换。
步骤如下：
将两个红链接变成黑链接 将父节点的链接颜色变为红色
1 2 3 4 5 void filpColors (Node h) h.color = RED; h.left.color = BLACK; h.right.color = BLACK; }
这很好地体现了 4-节点 的分裂过程。分裂了 红色 ，此时父节点就会变为上层 3-节点 的一部分，也满足了在分裂过程中，将中间节点向上传递 的思想。
假如父节点是根节点时，由于没有任何链接指向根节点，所以根节点的颜色变得无关紧要了 指向其链接的颜色 的原因
最后，我们终于进入了真正的插入环节，根据 2-3 树的插入思想，红黑树的插入步骤如下：
新节点的颜色是红色的
由于 2-3 树在插入之后一定会形成至少一个 3-节点（有时还会有临时的 4-节点）
如果右子结点是红色，左子结点是黑色，那么向左旋转
右子结点为红色，左子结点为黑色，说明红黑树中存在红色的右链接，将其向左旋转
如果左子结点和它的左子结点都是红色的，那么将当前节点向右旋转
这种情况说明红黑树中存在两个连续的红色链接 ，说明存在一个内部的 4-节点，此时我们将其向右旋转 ，变为可以进行颜色转换的状态，随后通过颜色转换来将 4-节点 分裂
如果左子结点和右子结点都是红色的 ，那么进行颜色转换
此时说明存在 4-节点，通过颜色转换将其分裂
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 public void put (Key key, Value val) root = put(root, key, val); root.color = BLACK; } private Node put (Node h, Key key, Value val) if (h == null ) return new Node(key, val, 1 , RED); int cmp = key.compareTo(h.key); if (cmp < 0 ) h.left = put(h.left, key, val); else if (cmp > 0 ) h.right = put(h.right, key, val); else h.val = val; if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h); if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); if (isRed(h.left) && isRed(h.right)) flipColors(h); h.N = size(h.left) + size(h.right) + 1 ; return h; }
需要注意的是，有可能存在需要多次变换 的情况，所以上述检测需要依次进行一遍
比如折线式的红链接（红色的左链接 + 红色的右链接） ，此时就需要先将右链接向左旋转，变为连续的红链接 ，再将上面的链接进行右旋转，变为两个红色的子链接 ，随后进行颜色转换。
这样做的原因在于，我们可以按照图示那样， 逐步减少需要讨论的情况 ，从而节省代码
同时，为了能让父节点也能进行正确的变形，变形操作要放置在递归方法之后 ，也就是修改值之后再进行变形操作。
删除通常来说是符号表实现的一个比较难的部分。
对于红黑树来说， 我们不能直接删除一个黑节点 ，这样会导致黑节点出现不平衡。
一般的红黑树实现中，通常是对红黑树做一个 BST 的删除操作，随后再进行恢复，不过这样在实践中会导致代码过于冗长。
在左斜红黑树中，我们以 删除一个红节点 作为目标；
在删除完成后，我们通过递归向上对链接进行修复。
为了能够让我们所删除的元素成为红节点，当出现连续两个子节点都是黑的时，我们就必须通过颜色变换将红链接向下传递；
否则红链接的特性就会断绝
但是，这样有可能导致两个连续的红链接 ，如下图所示；
b 节点并不在我们的递归路线中，我们无法对这种非法的 4-节点进行修复；
所以我们要对这种情况进行处理。
可以看到，我们首先将 a 节点进行颜色反转，从而将 c 染红；
但是此时，由于 b 也是红节点，所以造成了两个连续的红链接；
所以我们通过先将 c 向右旋转，再将 a 向左旋转，将其变为平衡态；
再通过颜色反转避免了连续的红链接出现。
实现如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 private Node moveRedLeft (Node h) colorFlip(h); if (isRed(h.right.left)) { h.right = rotateRight(h.right); h = rotateLeft(h); colorFlip(h); } return h; }
完整的删除最小元素的代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 public void deleteMin () if (!isRed(root.left) && !isRed(root.right)) root.color = RED; root = deleteMin(root); if (!isEmpty()) 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 balance(h); } private Node balance (Node h) if (isRed(h.right)) h = rotateLeft(h); if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); if (isRed(h.left) && isRed(h.right)) flipColors(h); h.size = size(h.left) + size(h.right) + 1 ; return h; }
同理，在删除最大元素和删除通常元素的时候，我们也会出现由于红链接向下传递引起的连续红链接问题，如图所示：
其中 d 不处在我们的递归路线上，所以就必须进行处理。
实现如下：
1 2 3 4 5 6 7 8 9 10 11 12 private Node moveRedRight (Node h) flipColors(h); if (isRed(h.left.left)) { h = rotateRight(h); flipColors(h); } return h; }
完整实现如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 public void deleteMax () if (!isRed(root.left) && !isRed(root.right)) root.color = RED; root = deleteMax(root); if (!isEmpty()) 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 balance(h); }
对于通常内部节点的删除，由于红黑树的特殊特性，我们直接使用 BST 的删除方法需要考虑的问题颇多；
但除此之外，我们可以使用一个巧妙的方法：
将节点设置为其后继节点 将其后继节点删除 这样既符合 BST 删除原理，同时我们可以重用现有的代码；
因为一个节点的后记节点，就是 其右子树的最小节点 (min(h.right))；
因为我们已经实现了 deleteMin() 方法；
所以只需要简单的将节点交换，同时将后继删除即可。
完整的实现如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 public void delete (Key key) if (key == null ) throw new IllegalArgumentException("argument to delete() is null" ); if (!contains(key)) return ; if (!isRed(root.left) && !isRed(root.right)) root.color = RED; root = delete(root, key); if (!isEmpty()) root.color = BLACK; } 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 ) { Node x = min(h.right); h.key = x.key; h.val = x.val; h.right = deleteMin(h.right); } else h.right = delete(h.right, key); } return balance(h); }
