前言： 树结构是一种很常见的数据结构，比如我们的文件目录，数据库的索引，以及我们现在将要讲述的字典。在第一篇文章中（传送门：https://www.jianshu.com/p/577d5e878c4f），我们用hashtable实现了一个字典，这种结构的字典也是 apple NSDictionary 或 CFDictionary 所采用的方案。但是，c++ 的 STL 中 map、 linux 的内核调度的底层实现是一棵红黑树。理想情况下，hashtable 的查找插入时间复杂的可达O(1)，但是这需要花费额外的内存空间，也就是说需要更多的桶，红黑树不需要占用额外的空间，更省空间。
二叉搜索树 BST （binary search tree）
在实现我们的轮子之前，我们先回顾一下关于二叉树的相关概念。二叉树是一个节点最多只有两个子树的树型结构，也就是说节点会有两个分叉，所以叫二叉树。二叉搜索树 BST 是二叉树的一种，区别于二叉树是它是有序的。只要按中序遍历，就能按顺序打印数据。二叉搜索树如果遇到有序输入，它就会退化成链表（好惨），这叫树的失衡。为了解决这个问题，各种二叉树的变种，平衡树就出现了，例如avl树，红黑树等。
我们先看看BST构建，构建一个BST最主要的是插入操作
看伪代码：
定义简单的二叉树结构
typedef struct _Node {
keyType key;
_Node *left;
_Node *right;
} *NodeRef;
NodeRef insert(NodeRef n, key) {
if (NULL == n) {
//如果节点是空，创建节点
NodeRef node = new Node
node.key = key;
return node;
}
if (key == n.key) return n;
if (key < n.key) { // 往节点的左子树插入
n.left = insert(n.left, key);
} else { // 往节点的右子树插入
n.right = insert(n.right, key);
}
return n;
}
删除节点
删除节点的操作分三种情况：
第一种情况，节点没有孩子，这时候直接删除。
第二种情况，如果只有一个孩子，那么让节点的孩子顶替节点的位置，删除节点。
第三种情况，节点有两个孩子，这时候有两个选择，1）寻找节点左孩子的最大叶子，用来顶替被删除节点。2）寻找节点右孩子的最小节点，用来顶替被删除节点。
我们用右孩子的最小叶子来顶替被删除节点。
NodeRef delete(NodeRef n, key) {
if (!n) return NULL;
if (key < n.key) {
n.left = delete(n.left, key);
} else if (key > n.key) {
n.right = delete(n.right, key);
} else {
if (n.left && n.right) {
NodeRef tmp = findMin(n.right);
n.key = tmp.key;
n.right = delete(n.right, tmp.key);
} else {
n = n.left ? n.left : n.right;
}
}
return n;
}
2-3树
什么是红黑树？对于这个问题，笔者在刚开始接触红黑树的时候也很疑惑，代码怎么体现红和黑呢？到底红节点和黑节点有什么作用？为什么它可以保持树的平衡呢？各种旋转变色操作让人看的头昏眼花。其实，只要我们了解红黑树的来源，就能发现红黑树也不是那么抽象，其实红黑树是来源于2-3树。让我们稍微了解一下2-3-树。2-3树的定义，可以参考维基百科（https://zh.wikipedia.org/wiki/2-3树 ）。在这里讨论2-3树，那么文章的篇幅未免太长，但是如果不谈论，那么这篇文章就不能算完整。犹豫再三，笔者还是先从2-3树说起。如果读者了解2-3树，则可以略过。
2-3树是多叉树，一个节点可以有2个分叉，或者3个分叉。他还能临时有4个分叉。
每种节点如下图
我是2节点，我有2只手，指向空叶子null
我是3节点，我有3只手，指向空叶子null
我是4节点，我有4只手，指向空叶子null
对于2-3树来说，4节点是临时的，很快它就要分裂成2节点或3节点。稍后很快会看到它是怎么分裂的。
理解一棵树最好的方法就是观察它是怎么长出来的，或者怎么生成的。
我们试着用A D C E K J B M 依次插入一个空树中，看看它的生长过程。
（简便起见，空叶子不画出来。本来是想用PS画的，但是太慢了，还不如手写，不是很好看，大家将就点了😄。）
插入 A
生成一个2节点的树，同时它也是树根
插入 D
如图，这时候2节点变成3节点了
插入 C
3节点变成节点，我们看到，在节点内，元素都是按从小到大的顺序放置的，这就保持了树是有序的。上面说到，4节点是临时的，下一步它就要分裂了，继续看
C 元素从4节点提取出来成为新的树根，也可以叫父节点，它有两个孩子A 和 D 。为什么要把 C 提取出来作为父节点而不是 A 或 D 呢。因为这是一颗搜索树，把中间的 C 提取出来树才能保持有序。看看现在它是不是很像二叉树啊~
插入 E
这时候的插入，如同二叉树，从根节点 C 开始寻找， E 比 C 大，所以从 C 的右子树继续寻找，找到 D 节点，这时候树往下没有子节点了，那么 E 就放在和 D 同一个节点，并且在 D 的右边。如图，D E 组成一个新的3节点。
插入 K
因为K比C大，所以往右子树查找，K 比 D E 大，再往下是空叶子了，所以K停留 在 E 的右边，D E K 它们一起组成了4节点。又因为 这是 2-3树，4节点是临时的，所以又要分裂，如下图：
对照前一张图，我们把4节点（包含D E K）分裂，跟前面一样，提取 E 出来 和父节点（2节点C）合并成为3节点（C E） ，剩下的 D K 各自成为一个2节点 ，父节点的第二只手指向 D ，第三只手指向 K。这就恢复了2-3树的特点。
插入 J
继续上面的方式，J 比 K 小，所以放在 K 的左边
插入 B
B 比 C 小 ，往左子树找，找到 A ，A 是2节点，所以 B 可以和 A 安心的放在一起。
插入 M
M 要停留在 （J K） 节点， M 比 K大，放 K 右边。这个时候 J K M 组成了4节点，老规矩他们要分裂。
K 提取出来 和 它的父节点 合并 组成了 （C E K ) 4节点。
这个时候 ，新的父节点是4节点，不符合2-3树的性质，他必须分裂。E 被提取出来，成为新的树根。
C 和 K 成为 E 的子节点。，如下
可以看到，经过这次分裂，整棵树长高了一层了。
以上就是2-3树的生成。了解了2-3树，我们继续看红黑树
红黑树
红黑树是被加入了几个限定条件的二叉树。这个限定条件的来源其实就是2-3树。实际情况中，2-3树编码实现很麻烦，人们就另辟蹊径，用二叉树模拟2-3树的性质，红黑树就粉墨登场，嘿，闪亮登场了。这就是为什么在说红黑树前，我们先去了解2-3树的原因。
先看看红黑树都有什么限定条件：（来源百度）
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 每个叶节点（NIL节点，空节点）是黑色的。
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
解析一下这是什么意思：
性质1：红黑树的节点，不是红色，就是黑色。没有其它什么绿色白色紫色之类的。嗯，很单纯，设计经典红黑搭配。
性质2：就是说树根是黑色，或者说树头是黑的。很合理不是吗，嘿嘿，树头嘛，能不黑吗？
性质3：树叶是黑色的，就是说没数据的nil节点，也就是空指针，是黑色的。注意，树叶不是绿色的，啥？！
性质4：也就是说一个节点是红色，那么它的子节点（离它最近的）必须是黑色。
性质5：（略）
那么，问题来了，这红黑的节点的区分是有什么意义呢？（其实，捡垃圾只是我的表面，我的真实身份是一名研究生。。。。。。），把节点标记成红色只是它表面，它的真实意思是：我（红色节点）和我老爸（父节点）是一伙的，分不开的。红色节点有如在自身和父节点之间连上了一条红色的链条，我们应当把它们看作一个整体，这就等同于2-3树的3节点。
如图：
红线连起来的两个2节点应该看作一个整体，他们是不可分的3节点。这就是红节点的意义。
说了这么多有什么用。。。写点代码吧。
我们试着实现一棵左倾红黑树，为什么叫左倾，因为红链都在左边，就是上图红色那根线。左倾比较容易实现......
相比而言，左倾红黑树多了两条性质：
1、红链接均为左链接。
2、没有任何一个结点同时和两条红链接相连。
左倾是对三节点而言的
通过上图可以看到，红链在左边，4节点是节点的两个孩子都是红色的，这是临时节点，最后要变成左倾的。
再看看红黑树和2-3树的对比
左边的树根（C E）是一个3节点，用红黑树表示就是C E 之间有一根
红黑树，先给它来点颜色瞧瞧，不要以为是UIColor啊~~~
typedef NS_ENUM(NSUInteger, Color) {
RED,
BLACK,
};
呵呵，这就是颜色了,,ԾㅂԾ,,
接下来我们在定义红黑树的节点Node
@interface Node : NSObject
@property(nonatomic, strong) NSString *key;
@property(nonatomic, strong) NSString *value;
@property(nonatomic, assign) Color color;
@property(nonatomic, strong) Node *left;
@property(nonatomic, strong) Node *right;
+ (instancetype) nodeWidthKey:(id)key value:(id)value;
@end
@implementation Node
+ (instancetype) nodeWidthKey:(NSString *)key value:(NSString *)value {
Node *n = [Node new];
n.key = key;
n.value = value;
n.color = RED;
return n;
}
@end
在标准的二叉树定义下，多了一个color属性，还包括了一个生成 Node 节点的类方法，这个方法简单的对成员变量赋值。注意这里有个约定：新创建的节点一定是红色的。切记这一点。
现在看整棵红黑树树的定义
@interface LLRB : NSObject
@property(nonatomic, strong) Node *root;
- (void) insert:(Node *)n;
- (void) remove:(NSString *)key;
@end
很简单，只有一个root根节点，一个插入节点的方法insert和一个删除节点的方法remove。
普遍的，我们先来看看红黑树是怎么生成的，再来看如何删除其中某个节点。
树生成是通过插入操作实现的。
我们先定义一下工具方法
BOOL isRed(Node *n) {
if (!n) return NO;
return n.color == RED;
}
int compareTo(NSString *k1, NSString *k2) {
return [k1 compare:k2];
}
第一个方法判断节点是否红色，第二个是key 的比较方法。
无论我们多么小心翼翼，再插入节点的过程中，总会出现违反红黑树性质的情形。下面我们要分析的出现的各种情形以及用什么方法修正。
情形1
解析： 这图左边是一个父节点，插入一个节点在父节点的右边。新插入的节点总是红色的，因为我们的是左倾，这里变成右倾，不合法，我们通过左旋操作修复。
可以看到，F节点的右子树不再指向Q，而是指向Q的左子树，并将F 设置为 Q 的左子树。这就完成了左旋操作，上面是java的代码，对应 oc 的代码如下：
Node* rotateLeft(Node *h) {
Node *x = h.right;
h.right = x.left;
x.left = h;
x.color = x.left.color;
x.left.color = RED;
return n;
}
h 对应上面的 F 节点， x 对应上面的 Q 节点。
情形2
如上图的，在左链下面的右子树插入了一个节点，又变成了右倾了，那么我们先用左旋操作修复了右倾。这时候又出现了一个情形，同一条路径有两个连续红节点，这是不合法的。我们这时候用右旋操作把上面一条红链移到右边。
右旋就是左旋的镜像，下面直接给出oc代码了
Node* rotateRight(Node *h) {
Node *n = h.left;
h.left = n.right;
n.right = h;
n.color = n.right.color;
n.right.color = RED;
return n;
}
这时候的样子是这样的
情形3
这时候的请况父节点左右两边都是红链了，左倾右倾都有了。这可怎么办😱？我们总不能再旋转了吧。
嗯~~，等等，我们还可以操作颜色对不，只要我们把两个红节点涂黑，把父节点涂红，不就决解问题了吗！这不会违反红黑树的性质（在同一条路径上黑色节点的数量一样）。这叫颜色的翻转
图上的代码是错的，把参数 h 错写成 x 了，也不需要返回值，不过图不错，我们拿来用了，✌。对应的oc代码是：
void rbcolorFlip(Node *n) {
n.color = !n.color;
n.left.color = !n.left.color;
n.right.color = !n.right.color;
}
好了，需要考虑的也就上面三种情形，并且我们都解决了，现在我们可以写红黑树的插入了。
Node* insert(Node *h, Node *aNode) {
if (!h) return aNode; //1
int cmp = compareTo(aNode.key, h.key); //2
if (cmp == 0) h.value = aNode.value; //3
else if (cmp < 0) //4
h.left = insert(h.left, aNode); //5
else //6
h.right = insert(h.right, aNode); //7
if (isRed(h.right) && !isRed(h.left)) //8
h = rotateLeft(h); //9
if (isRed(h.left) && isRed(h.left.left)) //10
h = rotateRight(h); //11
if (isRed(h.left) && isRed(h.right)) //12
rbcolorFlip(h); //13
return h; //14
}
代码很少啊，嗯~，看看都做了什么事。我们逐行讨论一下。
第1行，insert 函数传入的是根节点，如果根节点为空，证明是一颗空的树，我们直接返回 aNode 作为树根。
接着比较aNode 的key 和 h 的key ，相等的话最简单，直接将 h 的 value 替换成 aNode 的 value。如果新插入的key 比 h 的key 小，那么往 h 的左子树插入，否则往 h 的右子树插入。
从第8行开始，我们对应着之前分析的插入会导致左倾红黑树性质被破坏的情形一个个修复。
1、如果h 右孩子是红的，左孩子是黑的，对应情形1， 执行左旋操作修复。
2、如果h 的左孩子是红，h 的左孩子的左孩子也是红，说明一条路径上有两个连续的红色节点，对应情形2，执行右旋操作修复。
3、上面的分析我们知道，修复情形2会导致情形3，那么我们用颜色翻转去修复左倾红黑树的性质。
以上，我们实现了红黑树的插入。继续之前，我们把上面的的第八行开始的代码抽出来成为一个fixUp方法，因为删除也要用到
Node* fixUp(Node *h)
{
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))
rbcolorFlip(h);
return h;
}
红黑树的插入操作 oc 代码这样调用
- (void)insert:(Node *)node {
self.root = insert(self.root, node);
self.root.color = BLACK;
}
呼，能看到这里，列为看官也算给俺面子了（也说明我写的还不算胡扯，😁），要不要歇会。。。
----------不要怂，不要停，继续干--------------
我们 go on 把红黑树的删除操作也撸完，怎么样？这主意看起来 不咋地。。。
左倾红黑树的删除(最复杂的)
跟普通二叉搜索树（下面称二叉树）的删除一样，因为是左倾的，所以我们尽量删除右子树的最小元素。方法如下：
1、找出当前要删除的节点C
2、找出C的右子树的最小节点M
3、用M节点的值替换C节点
4、删除M节点
这里有个问题就是，如果被删除的M节点是一个3节点，也就是说它红色的，n那么直接删除就行了，不会影响树的平衡，因为每条路径上的黑节点数没有变化。如果是一个2节点就麻烦了，2节点意味着它是黑色的，删除了就造成当前节点路径上的黑节点少1了。为了让树不要失去平衡，最好我们删除的都是红节点就再好不过了。为了达到这个目的，我们在往下找到删除节点的时候能带一个红色点下去，那不就很完美了吗？因此，我们看看怎么做的这一点。
从树根开始搜索，也是分几种情况：
1、要删除的节点比当前节点小
这时候，我们要往left 搜索，我们判断当前节点的 left 和 left 的 left 都是 2节点的情况。这个时候我们需要把一个红节点往 left 下面带。怎么带呢，这个时候要依赖当前节点的 right 的 left 的颜色。
如上图，h为当前节点，h.left 和 h.left.left 都是黑色，如果h.right.left 是黑色，那么简单的翻转颜色就行了。这样heft.left就是红色了，我们成功把红色往left带了。那么h.right也是红色啦，这没问题？当然没问题，在我们完成删除递归返回的时候调用fixUp方法，会修复这个问题的。
如果h.right.left是红色，我们首先做的是颜色翻转，这个时候，h.right 是红色，h.right.left 也是红色。如果就这样不管，递归返回的时候是没办法修复（两个连续的红色，fixUp修复不到这个地方）。因此，我们对h.right 右旋，然后颜色翻转，这样，红色往left带，right同时也满足红黑树的性质。如果还是不太明白，上面的图仔细看看。
通过上面的分析，我们得到下面的方法：
Node* moveRedLeft(Node* h)
{
rbcolorFlip(h);
if (isRed(h.right.left))
{
h.right = rotateRight(h.right);
h = rotateLeft(h);
rbcolorFlip(h);
}
return h;
}
2、要删除的节点比当前节点大
这时候我们要往右边搜索了，如果当前节点h 的left 是红 right 是黑，我们要把红节点往 right 带。对h 右旋。如果h.right 和 h.right.left是黑色，我们执行和 1情形的镜像操作，
如下:
Node* moveRedRight(Node* h) {
rbcolorFlip(h);
if (isRed(h.left.left)) {
h = rotateRight(h);
rbcolorFlip(h);
}
return h;
}
3、要删除的节点和当前节点相等。
我们在这里需要往右子树搜索其最小值。如果当前节点h.left红，h.right黑，用右旋把红点往右带一位。再比较，如果当前节点h和要删的节点相等，同时h.right 是空，直接删除当前节点。如果h.right黑和h.right.left黑，moveRedRight 把红点往右边带，再次比较如果相等，寻找h.right的最小节点覆盖当前节点，然后用deleteMin方法删除h.right的最小节点，否则对h.right递归调用删除方法。
Node* deleteMin(Node* h)
{
if (h.left == nil)
return nil;
if (!isRed(h.left) && !isRed(h.left.left))
h = moveRedLeft(h);
h.left = deleteMin(h.left);
return fixUp(h);
}
//寻找 最小节点
Node* min(Node* h) {
if (!h) return nil;
if (h.left == nil) {
return h;
} else {
return min(h.left);
}
}
完整的删除方法：
Node* delete(Node* cn, NSString* k) {
if (cn == nil) return nil;
int cmp = compareTo(k, cn.key);
if (cmp < 0) { // k < cn.k 往左边 left 搜索
if (!isRed(cn.left) && !isRed(cn.left.left)) //红点往left带
cn = moveRedLeft(cn);
cn.left = delete(cn.left, k);
} else if (cmp > 0) { // k > node.k go right
if (isRed(cn.left) && !isRed(cn.right)) //红点往right带到右边
cn = rotateRight(cn);
if (!isRed(cn.right) && !isRed(cn.right.left)) //红点往right带
cn = moveRedRight(cn);
cn.right = delete(cn.right, k);
} else { // 就算找到了，也不能直接删除，必须先带了红点下来才能继续
if (isRed(cn.left) && !isRed(cn.right)) {
cn = rotateRight(cn);
}
if (compareTo(k, cn.key) == 0 && (cn.right == nil)) //直接删除
return nil;
if (!isRed(cn.right) && !isRed(cn.right.left)) // 红点往right带
cn = moveRedRight(cn);
if (compareTo(k, cn.key) == 0) { // 跟二叉树一样的办法，用被删节点的右子树的最小节点替代被删节点
Node* x = min(cn.right);
cn.key = x.key;
cn.value = x.value;
cn.right = deleteMin(cn.right);
} else cn.right = delete(cn.right, k);
}
return fixUp(cn);
}
- (void) remove:(NSString *)key {
self.root = delete(self.root, key);
self.root.color = BLACK;
}
以上就是我们要做的红黑树字典的轮子了，写代码测试一下
// A D C E K J B M
LLRB *t = [LLRB new];
[t insert: [Node nodeWidthKey: @"A" value: @"1"]];
[t insert: [Node nodeWidthKey: @"D" value: @"4"]];
[t insert: [Node nodeWidthKey: @"C" value: @"3"]];
[t insert: [Node nodeWidthKey: @"E" value: @"5"]];
[t insert: [Node nodeWidthKey: @"K" value: @"11"]];
[t insert: [Node nodeWidthKey: @"J" value: @"10"]];
[t insert: [Node nodeWidthKey: @"B" value: @"2"]];
[t insert: [Node nodeWidthKey: @"M" value: @"13"]];
[t remove:@"D"];
[t remove:@"E"];
剩下的get方法跟二叉树一样，就不再赘述了。
参考文章和图片来源:
http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf
