简介
最后我们总结出二叉树是无法自平衡的:原因是二叉树不能调整节点位置。本文我们将介绍红黑树，一种能自平衡的二叉树，为了方便理解红黑树，有必要先学习2-3树。
2-3树
2-3树的定义:同时具有2-节点，3-节点的树，而n-节点指一个节点最多有n个子节点。一个例子:
查找与插入
查找
2-3树的查找和二叉树无本质区别，仍然是比大小。
插入
插入操作2-3树和二叉树完全不同：由于节点可以容纳2个健，所以先将健放在最底层节点，然后判断健个数，如果超过2，则拆分推中(将大小健拆分成两个节点，将中间键推到父节点内)，此时父节点也增加了健个数，做相同的判断以及拆分推中操作，直至根节点。下面看几个例子：
不拆分推中（2-节点 -> 3-节点）
拆分推中（3-节点 -> 3个2-节点）
- 根节点提升
- 父节点是2节点时左侧提升
- 父节点是2节点时右侧提升
- 父节点是3节点时左侧提升
- 父节点是3节点时中间提升
- 父节点是3节点时右侧提升 其中只有第1种情况，整棵树的高度增加，另外5种情况都是局部变化，不影响其他部分的高度，所以自始至终，2-3树都是一个平衡树。
一个真实的例子
小结
总结下2-3树和二叉树的区别:二叉树向下生长，而2-3树是向上生长。
红黑树
终于到红黑树了，我们先给出红黑树的定义：
- 红黑树是一棵二叉树
- 每个节点都有颜色属性，红或黑（该属性也可以理解为和父节点链接的颜色）
- 红色属性只能是左子节点（或左链接） 暂且不提红黑树的定义，先看下红黑树和2-3树的关系。
和2-3树的等价性
前面我们讨论了2-3树的定义、特点、操作，却没有实现代码，原因在于2-3树实现相当复杂，复杂的数据结构和变化运算几乎抵消算法本身的优势。 那怎么办呢？你猜对了，用红黑树表示2-3树（想象红色节点和父节点是一个整体，不就是3-节点吗），因为每棵2-3树确实存在至少一棵红黑树与之对应，并且红黑树是二叉树，使得我们可以用二叉树的操作实现2-3树的变化。
插入
下面我们看下红黑树的插入过程（和上面2-3树的插入过程对比下）：
不拆分推中（2-节点 -> 3-节点）
拆分推中（3-节点 -> 3个2-节点）
左旋、右旋及颜色反转
上一节图例中，红黑树使用了左旋转（rotate left）、右旋转(rotate right)和颜色反转(color flip)三种变化，我们一一解释：
左旋转
左旋转目的是让当前节点符合红黑树的定义（红色节点只能在左分支）。
private Node rotateLeft(Node node) { Node right = node.right; right.red = node.red; node.right = right.left; node.red = true; right.left = node; return right;}复制代码 右旋转
右旋转的目的是为颜色反转变化做准备。
private Node rotateRight(Node node) { Node left = node.left; left.red = node.red; node.left = left.right; node.red = true; left.right = node; return left;}复制代码 颜色反转
颜色反转对应2-3树中的拆分推中操作。
private void flipColor(Node node) { node.left.red = node.right.red = false; node.red = true;}复制代码 我理解3种操作直接或间接在红黑树上实现2-3树的操作。 还有一点：插入的元素是红色，正好对应2-3中新元素添加在底层节点，而非底层节点的子节点。
代码
private Node put(Node curr, Key key, Value value) { if (curr == null) return new Node(key, value, true); int r = key.compareTo(curr.key); if (r < 0) curr.left = put(curr.left, key, value); else if (r > 0) curr.right = put(curr.right, key, value); else curr.value = value; if (isRed(curr.right) && !isRed(curr.left)) curr = rotateLeft(curr); if (isRed(curr.left) && isRed(curr.left.left)) curr = rotateRight(curr); if (isRed(curr.left) && isRed(curr.right)) flipColor(curr); return curr;}复制代码 可见，红黑树的插入函数对比二叉树版本 ，仅仅多了最后的旋转和颜色反转操作。
小结
其实本节介绍的红黑树其实更应该叫做左倾红黑树，因为我们规定了红色节点必须是左节点。左倾红黑树是红黑树的改进版，有兴趣的同学可以自行百度。
总结
本文在前文二叉树的基础上先介绍了2-3树、红黑树，介绍2-3树是为红黑树做铺垫，他们都是平衡树，具备对数级别的时间复杂度。