问题引入 #
我们先从二叉查找树开始谈起，在足够理想的情况下，二叉查找树和快速排序非常类似，树的根节点就是快排的第一个切分元素pivot，并且满足左子结点小于root，右子结点的值大于root。他们都是使用了分治法的思想。并且一棵保持平衡的二叉查找树（BST）在平均的情况下查询的时间复杂度能达到 O(log n)。
这是一个可以被我们接受的时间复杂度。不过因为二叉查找树的所有操作所需的时间都和树的高度成正比，假如这个数退化成一个链表，那查询速度将会大打折扣。如果我们始终保持这棵树是平衡的，这个可以实现，但是也要花费很大的成本。如下图，插入1之后大量的结点发生了调整。
为了优化这个问题，人们就考虑在一个树的结点中保存多个值，这样就能减少高度的增加。最直观的想法就是让一个结点可以保存不超过2个值，如下图：
我们保证结点中的值都是从小到大排列的，并且可以看到单个值对应有两个孩子（2-结点），两个值的结点对应3个孩子（3-结点）。所以我们把这种数据结构叫2-3树。
可以看到树上的所有叶子都在一个层次上，因此2-3树总是保持高度平衡的。它的查找效率也能保证在 O(log n)。虽然看似只是进行了一点小小的优化，但一个10个结点的2-3树高度只在19-30之间，这实际上是一个很惊人的数据了。
但是我们怎么插入新的元素呢，假如我们采取和查找一样的方式，直接插到尾部，那将无法保持平衡。所以必须做一些规定：
- 假如要插入的元素位置的父结点是一个2-结点，那我们就将这个2-结点变成3-结点，把新元素加进去就行
- 如果父结点是一个3-结点，我们要把它变成一个4-结点，然后根据不同情况做拆分：
- 这个4-结点的父结点为2-结点，就将4-结点中最中间的值加进2-结点中，把2-结点变成3-结点，然后剩下的最小的元素和最大的元素拆成两个2-结点接到下面；
- 这个4-结点的父结点为3-结点，采取和1一样的做法，一直往上做拆分，直到找到一个父结点是2-结点。如果到根节点都不满足根节点是一个2-结点，那根节点就会变成一个临时的4-结点，然后把这个4-结点拆成3个2-结点，使得树的高度增加1.
以上就是所有插入的变换情况，可以看到整个过程中树都是保持平衡的，而且和二叉查找树自上而下生长的方式不同，2-3树是自下而上生长的。
红黑树 #
基本概念 #
我们已经对插入进行了设计，下面要做的就是真正实现这种数据结构了。不难想到，我们可以构建2-结点和3-结点的类，然后根据上面的算法不断的变换来实现它。事实上这么做当然没问题，但是却面临两个难点：
- 首先是结点之间的数据需要来回变换，效率低，消耗资源；
- 另外真正实现起来也比较容易出错。
所以科学家就根据这种思路实现了红黑二叉查找树的这种数据结构来高效地进行优化，方便我们进行代码实现，也减少了数据之间的来回变化。
我们知道普通的二叉查找树的高度不好控制，所以我们才允许一个结点出现多个值来降低高度。那我们能不能只是在逻辑上采用这种思想，但是实际上还是采用二叉查找树的结构呢。毕竟这种结构实在是有很多好处。所以有了下面的这种实现，如下图：
如果我们把二叉树的某一个链接放平，可以看到树的高度明显减小了1，而且在本质上这棵树是没有发生变化的。同样的，我们把这两个结点合起来不就正好是一个3-结点吗。
红黑树实际上就是将3-结点拆开了，然后把较大的值作为父结点，较小的值作为子结点，这样就能用一个2-结点的数据结构来实现。只要我们把父结点放平，再把这两个结点合起来，它们就构成了一个3-结点。
为了便于区分我们到底把哪个链接放平了，我们就要给这个链接做个特殊的颜色标记，把它标记为红色，如上图所示。但是我们知道链接是结点这个类里面的一个成员变量，它指向某一个结点，所以我们就直接把它指向的这个结点的颜色标记为红色，其余的颜色为黑色。但是为了便于理解，我们还是约定某一个结点的颜色指的是指向该结点的链接的颜色。结点的数据结构如下：
class Node<Key,Value>{
Key key;
Value val;
Node<Key,Value> left,right;
boolean color; //红色为true,黑色为false
public Node(Key key, Value val,boolean color){
this.key = key;
this.val = val;
this.color = color;
}
……
}
现在我们来说明它具有的几个特征：
（1) 空链接的颜色为黑色，这也说明根结点中的颜色标记为黑色，因为指向根节点的链接是空链接；
（2）红链接全是左链接；
（3）没有任何一个结点同时和两条红链接相连，因为如果将2-3树的3-结点画成红色左链接相连的两个2-结点，必然不会存在能够和两条红色链接相连的结点；
（4）任意空链接到根结点的路径上的黑链接数量相同，该树完美黑色平衡。
要使这棵树完美黑色平衡，以上条件必须满足。如果不满足，就必须进行调整，调整的策略就是对树进行旋转和颜色转换。
- 左旋转：将红色的右链接转化为左链接的过程叫左旋转，具体过程如下图所示：
可以看到，我们需要把较小元素的color设置为红色，并且需要让较大元素的左子树链接到较小元素的右子结点下面。代码实现如下：
public Node rotateLeft(Node node){ //node为较小元素对应的结点
Node x = node.right; //x为较大元素对应的结点，也就是node的右子结点
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = true; //将链接指向的元素的颜色设置为红色
return x;
}
- 右旋转：当出现一个结点同时和两条红链接相连的情况的时候我们就要考虑右旋，即就是把左红链接转化为右红链接的过程，如下图所示：
右旋之后较小结点的右子树要拼接到较大结点的左子树那里，代码实现和左旋类似：
public Node rotateRight(Node node){ //node为较大元素对应的结点，也就是这整个子树的根结点
Node x = node.left; //x为较小元素对应的结点，也就是node的左子结点
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = true; //将链接指向的元素的颜色设置为红色
return x;
}
- 颜色转换：但是在右旋之后一个结点链接两个红链接的情况仍然没有避免，所以这里采取的措施是将它的父链接标记为红色，两个子链接的颜色标记为黑色。其实这个和2-3树的插入过程是一致的，这个我们后面会介绍。示意图如下：
实现这个的代码非常简单，只需要几行命令就可以：
public void flipColors(Node node) {
node.color = true;
node.left.color = false;
node.right.color = false;
}
红黑树的插入 #
下面我们来了解红黑树的插入过程：
我们已经知道了红黑树就是2-3树的一种实现，所以整个插入过程我们类比2-3树的插入来介绍，深色部分是上面描述的2-3树的插入过程，后面是红黑树的实现。
- 假如要插入的元素位置的父结点是一个2-结点，那我们就将这个2-结点变成3-结点，把新元素加进去就行
这个在红黑树中要变成3-结点就是把这个新元素的color属性设置为true，然后让2-结点指向新结点，如果新插入的元素小于这个2-结点的元素的值，那就直接插入；如果大于2-结点的元素的值，这个红链接就是右链接了，不满足上面的条件。所以需要把它旋转为左链接。
- 如果父结点是一个3-结点，我们要把它变成一个4-结点，然后根据不同情况做拆分：
首先将新元素的color属性设置为true，然后判断这个元素的值和前面的3-结点的每个值的大小。根据不同的情况，这个4-结点在红黑树中可以分为下面三种情况：
每种不同的情况都要根据前面提到的左旋，右旋和颜色转换来处理。
（1）这个4-结点的父结点为2-结点，就将4-结点中最中间的值加进2-结点中，把2-结点变成3-结点，然后剩下的最小的元素和最大的元素拆成两个2-结点接到下面；
这里我们分别对前面提到的4-结点的三种情况进行讨论，已知这个4-结点的父结点为2-结点。
- 如果是新插入的值最大，就直接采用颜色转换，把中间的值对应的结点的颜色设置为红色，其他两个设置为黑色；
- 如果新插入的值最小，就先把上面的红色链接进行右旋，然后采用颜色转换；
- 如果介于两者之间，就先对下面的红链接进行左旋，然后再把最上面的红色链接进行右旋，最后再进行颜色转换。
(2) 这个4-结点的父结点为3-结点，采取和（1）一样的做法，一直往上做拆分，直到找到一个父结点是2-结点。如果到根节点都不满足根节点是一个2-结点，那根节点就会变成一个临时的4-结点，然后把这个4-结点拆成3个2-结点，使得树的高度增加1.
这部分红黑树的实现也是同上，采用递归的方式来保证一直往上做拆分，而且只要不满足前面的条件，就会进行树的调整。但是这样可能会出现一种情况，就是在颜色转换的时候非常有可能会使得根节点的颜色变成红色，而我们又规定了根节点的颜色必须是黑色。那怎么办呢，其实只要理解树完美黑色平衡这个概念，那这个问题就不再是问题，因为我们只需要把颜色重新设置为黑色就可以了。这样的话就相当于多了一个黑色的结点，也就相当于树的高度增加了1，依然和2-3树是一致的。
到这里红黑树的插入过程就完成了，具体代码如下：
public void insert(Key key, Value val){
root = insert(root, key,val);
root.color = false; //最后都要把根节点设置为黑色
}
public Node insert(Node root,Key key,Value val){
if(root == null) return new Node(key,val,true);
int cmp = key.compareTo((Key) root.key);
if(cmp < 0 ) root.left = insert(root.left,key,val);
else if(cmp > 0 ) root.right = insert(root.right,key,val);
else root.val = val;
if(root.right.color && !root.left.color) //右链接是红色，左链接是黑色
root = rotateLeft(root); //左旋
if(root.left.color && root.left.left.color) //一个结点连接两条红色的左链接
root = rotateRight(root);
if(root.left.color && root.right.color) //一个结点连接两条红色的链接（一左一右）
root = flipColors(root);
return root;
}
红黑树虽然在内部设置了很多规则来保证它是平衡的二叉查找树，但忽略掉这些规则它本质上还是一个普通的二叉查找树，所以查找算法和二叉查找树的一模一样。
public Node search(Key key){
return search(root,key);
}
public Node search(Node root,Key key){
int cmp = key.compareTo((Key) root.key);
if(cmp < 0 )
root.left = search(root.left,key);
else if(cmp > 0 )
root.right = search(root.right,key);
else
return root;
return new Node();
}
红黑树的删除 #
下面我们进入红黑树结点的删除操作。在删除操作中，如果被删除的数在树的底部，我们就直接删除它。否则，将他和它的后继结点交换，和二叉查找树一样。在数底的删除操作需要注意以下几点：
- 当前结点不是2-结点，直接删除；
- 当前结点是2-结点考虑从它的兄弟结点中借一个过来。
以上就是红黑树的实现了，为了让整个故事更加完整，我们后续再加入一点B树和B+树的内容。我们在实现红黑树的过程中用到了2-3树，是因为之前提出的想法是在一个结点中放多个值来减少树的高度，但是到目前位置我们只是放了不超过2个值，那我们能否更加一般化，让它不超过m个值呢？答案当然是肯定的。
这也就是B树的概念，m阶B树是指除了树根和叶子的每一个结点，具有最少 m/2个最多 m个孩子，并且B 树上的所有叶子都在同一个层次，因此B 树总是平衡的。如下图就是一个4阶B树：
B树的缺点在于它不能支持高效的范围查找，所以人们还根据B树演化出了B+树来弥补这一缺陷，B+ 树是一种最常使用的B树的变型 ，B+ 树的中间结点不存储和特定数据记录相关的内容，而只是记录关键字用于查找，所有在同一个层次的结点链成一个链表。如下图：
Last modified on 2021-07-24