红黑树
什么是红黑树
红黑树是一种常见的自平衡二分搜索树，常用于关联数组、字典，在各种语言的底层实现中被广泛应用。
满足红黑树的五个性质
- 每个节点是红色或者是黑色
- 根节点是黑色
- 每一个叶子节点（最后的空节点）是黑色
- 如果一个节点是红色的，那么它的孩子节点都是黑色的
- 从任意一个节点到叶子节点，经过的黑色节点是一样的
2-3树的定义
红黑树和2-3树有相似之处，我们先了解一下什么是2-3树
满足二分搜索树的基本性质，但是2-3树并不是二叉树
2-3树有两个节点，一个可以存放1个元素，一个可以存放2个元素
满足2-3树的三个性质
- 满足二叉搜索树的性质
- 节点可以存放一个或两个元素
- 每个节点有两个或三个子节点
每个节点都有2个子节点或者3个子节点，所以就叫做2-3树
左边节点都比42小，而右边节点都比42大，所以是满足二分搜索树的性质。注意，13和33这个节点中间是18，是比17大同时比33小。
2-3树的绝对平衡性
对于2-3树来说任意一个节点，左右子树的高度一定是相等的，而类似像AVL这种平衡二叉树左右子树的高度相差不超过1。
而2-3树是如何维持绝对平衡性，就要从它的添加操作说起。
对于一颗空树我们添加一个节点42，他既是根节点也是叶子节点，这个时候如果我们想再添加一个节点37应该添加到那里呢？
按平衡二叉树结构的逻辑来讲37比42小，所以添加到42的左孩子的位置。
但是在2-3树的中并不是这样的，
在2-3中我们依然是从根节点出发，请注意在2-3树中新的节点永远不会添加进空的位置
发现42节点的左子树为空，2-3树就会找到最后一个叶子节点上也就是42的位置，这时候37就会和42进行融合，从一个2节点变为了3节点。这个时候还是一颗绝对平衡的二叉树。
如果这个时候我们再添加一个12节点的话，因为12节点比37小，所以去找37的左孩子，但是我们已经知道，37的左孩子为空，而2-3并不会将新的节点添加到空的位置中去，这个时候我们就会变成4节点！
但是在2-3中最多支持3个节点所以这个时候就会进行分裂，同时保持绝对平衡。
如果这个时候我们再添加一个18节点，我们可以很清楚的知道18会找到12节点但是12节点的子节点都为空，所以18就会和12节点进行融合。
如果这个时候我们再添加一个6节点，大家很清楚的知道是会和12节点、18节点进行融合，这个时候变成了4节点，所以要进行分裂成为下图这样。
但是！这样我们就不是绝对平衡的二叉树了！
这个时候就需要我们12节点去找他的父节点，发现12的父节点37是一个2节点，这个时候就简单了，我们只需要让12和37节点进行融合为3节点，然后让6变成12和37的左孩子，让18节点变成中间孩子节点即可！
这个时候我们依次加入5和11节点，就会变成下图这样。
因为不满足2-3树的性质，所以我们还是将他们进行分裂。
但是这个时候又不是绝对平衡了，所以我们需要让6去找父亲节点，但是父亲节点已经是3节点了，不过没关系，我们照样把他融合进去成下图这样。
这个时候我们需要进行分裂，我们需要把5和11分别放在6的左孩子和右孩子的位置，37也同理，形成下图这样。依然保持着绝对平衡性。
其实我们可以分为两种情况去理解，一种就是当前节点为3节点而父节点为2节点。
另一种就是当前节点为3节点，父节点也为3节点的情况。
红黑树和2-3树的等价性
在2-3树种，我们可以表示2个节点和3个节点。
在红黑树中，我们可以这样表示，然后用红色的线来表示bc是融合的，同时b是比c小的。由于红色节点是由3节点拆分而来，因此所有的红色节点都只会出现在左子树上。
在下图中只有6和17和66是红色节点，我们很容易得知，因为他们都是3节点。
如果抽象的话可以红色节点上移一下，我们可以看到其实是和2-3树是一样的。
保持根节点为黑色和左旋
在下图上，我们知道最后分裂以后，6继续会向上进行融合，我们知道向上融合的节点一定是红色的，所以我们知道6是红色的，但发现已经没有父亲节点的时候，我们将6变为黑色。
最开始的时候我们想添加一个42的话，我们直接让42当根节点就好了，然后我们需要让42变为黑色节点。
这个时候我们添加一个37，可以直接放入到42左孩子的位置。
但是，如果我们要插入的节点为根节点的右孩子的节点的时候，我们需要进行左旋。
伪代码如下：
node.right = x.left; x.left = node; x.color = node.color; node.color = red;
Java代码如下：
// node x // / \ 左旋转 / \ // T1 x ---------> node T3 // / \ / \ // T2 T3 T1 T2 private Node leftRotate(Node node){ Node x = node.right; node.right = x.left; x.left = node; x.color = node.color; node.color = RED; return x; }
颜色翻转和右旋
最开始的时候我们想添加一个42的话，我们直接让42当根节点就好了，然后我们需要让42变为黑色节点。
这个时候我们添加一个37，可以直接放入到42左孩子的位置。
如果这时候我们再向红黑树中加入66节点，会变成如下图这样。
相应的在2-3树中是这个样子。
在红黑树中红色节点的意思就是和父节点是融合在一起的。
而37和66都是红色节点，说明它们都和父亲节点是融合在一起的。
在2-3树中，我们处理4节点的时候会进行分裂，分裂为3个2节点。
但是在红黑树中其实黑色节点就是2个节点，我们不需要进行旋转操作，我们只需要让37和66进行变色为黑色，就和2-3树中节点的性质是一样的了。
在2-3树中，我们需要继续让42节点向上去找父亲节点进行融合，相应的在红黑树中我们只需要让42变为红色即可。
这个就是颜色翻转（flipColors）
//颜色翻转 private void flipColors(Node node){ node.color = RED; node.left.color = BLACK; node.right.color = BLACK; }
另外一种情况就是，我们树添加成这个样子。我们添加了12节点，其实可以理解为它们是融合在一起的。在2-3树种就是4节点，然后将它进行分裂。
但是在红黑树中我们怎么变成这个样子呢？其实很简单，我们只需要进行右旋转即可。
为了方便理解，我们引入T1和T2虚拟节点来演示。
我们将x的右节点t1放到node的左孩子上，然后将node放在x的右孩子的位置即可。
别忘了，在这个时候node(42)节点其实是融合在x(37)节点上的，所以它要改为红色，37要改为黑色。
对应的伪代码：
node.left = t1; x.right = node; x.color = node.color; node.color = red;
最终我们就可以得到和2-3树结构一样的红黑树了。
// node x // / \ / \ // x T2 向右旋转 (y) y node // / \ - - - - - - - -> / \ // y T1 T1 T2 private Node rightRotate(Node node){ Node x = node.left; node.left = x.right; x.right = node; x.color = node.color; node.color = RED; return x; }
在红黑树中添加新元素
其实还有一种情况我们在前面没有讲到，就是在下图中添加一个元素40应该怎么做。
根据二分搜索树的性质，我们会将40添加进37的右孩子的位置。
但是这个时候已经破坏了红黑树的性质，所以我们需要进行左旋。
这个时候我们还需要进行右旋。
然后我们需要将40变黑色，42变为红色。
最后我们进行颜色翻转即可维持红黑树的性质。
总结图片如下：
如果我们添加的第三个元素是最小的话，我们可以直接从右旋开始。
反之我们添加的如果是最大的元素，我们可以直接进行颜色翻转。
// 判断节点node的颜色 private boolean isRed(Node node){ if(node == null) { return BLACK; } return node.color; } // node x // / \ 左旋转 / \ // T1 x ---------> node T3 // / \ / \ // T2 T3 T1 T2 private Node leftRotate(Node node){ Node x = node.right; node.right = x.left; x.left = node; x.color = node.color; node.color = RED; return x; } //颜色翻转 private void flipColors(Node node){ node.color = RED; node.left.color = BLACK; node.right.color = BLACK; } // node x // / \ / \ // x T2 向右旋转 (y) y node // / \ - - - - - - - -> / \ // y T1 T1 T2 private Node rightRotate(Node node){ Node x = node.left; node.left = x.right; x.right = node; x.color = node.color; node.color = RED; return x; } // 向红黑树中添加新的元素(key, value) public void add(K key, V value){ root = add(root, key, value); //根节点为黑色 root.color = BLACK; } // 向以node为根的红黑树中插入元素(key, value)，递归算法 // 返回插入新节点后红黑树的根 private Node add(Node node, K key, V value){ if(node == null){ size ++; return new Node(key, value); //默认插入红色节点 } if(key.compareTo(node.key) < 0) { node.left = add(node.left, key, value); } else if(key.compareTo(node.key) > 0) { node.right = add(node.right, key, value); } else // key.compareTo(node.key) == 0 { node.value = value; } //右孩子为红色，左孩子为黑色，进行左旋 if(isRed(node.right) && !isRed(node.left)){ node = leftRotate(node); } // 左孩子为红色，并且左孩子的左孩子也是红色，进行右旋 if(isRed(node.left) && isRed(node.left.left)){ node = rightRotate(node); } //颜色翻转 if(isRed(node.left) && isRed(node.right)){ flipColors(node); } return node; }
时间复杂度分析
红黑树相比于AVL树，其实是牺牲了平衡性的，红黑树并不完全满足平衡二叉树的定义，红黑树的最大高度达到了2logn的高度，红色节点影响了红黑树的的平衡性。红黑树虽然牺牲了一定的查询性能，但是在增删改操作的性能得到了弥补，红黑树的综合性能还是要优于AVL树的。
