用字符“画”搜索树，包括二叉树、红黑树等。
此篇文章，以树的“搜索”为主线来讲解，因为无论是插入还是删除，均离不开搜索；而反过来，为了保证树的搜索性能，插入和删除均需要做一定处理。
Binary Tree
首先说二叉树(Binary Tree)，毕竟，后面所讲的，都要基于二叉树。
从离散数学的角度来讲，树是由通过图结构来定义的，这里就直接讲二叉树了（当然，直接讲就不怎么严谨）。
基本概念
- 二叉树节点
D
/ \
L R
D : 当前节点，称D为L和R的父节点；
L : D的左孩子节点；
R : D的右孩子节点；
二叉树节点C式代码的实现：
struct Node{
Data data;
struct Node* parent;
struct Node* left;
struct Node* right;
int height; // 节点高度
int color; // 节点颜色，红黑树需要用到
};
- 简单的二叉树
----- r -----
Depth(v) / \
----- v u
/ \ / \ Height(r)
Height(v) a b x y
/ \ / \
----- al ar bl br -----
r : 根节点；
Height(r) : 树根节点r的高度，也称为树的高度；
Depth(v) : 子树根节点v的深度，根节点r的深度为0；
Height(v) : 子树根节点v的高度，空树的高度取为-1；
叶子节点 : 没有子节点（子节点为NULL）的节点，其高度为0；
节点数为n，高度为h；
二叉树 : h < n < 2^(h+1) 根根等比数列可求解；
满二叉树 : n = 2^(h+1) 树中所有节点均含有2个孩子节点，或没有孩子节点；
单链二叉树 : n = h + 1 树中所有节点均只有1个孩子节点，或没有孩子节点；
遍历算法
二叉树的遍历主要包括深度优先遍历（先序、中序、后序）和广度优先遍历（层次遍历）。
深序优先遍历递归式的算法就不说了，太简单了，这里主要说下迭代式的算法。
(1) 基本顺序
D
/ \
L R
先序遍历： D --> L --> R
(2) 实现
d
/ \
l1 r1 /
/ \ / => 对任何以d为根节点的子树，执行以下过程（称之为DLR过程）：
l2 r2 / 因为先访问D(即d,l1,l2)，所以在访问D的过程中，将R(r1,r2)按斜线方向入栈；
之后将出栈的节点R，当成新的子树d节点，执行DLR过程；
先序遍历 : d - l1 - l2 - r2 - r1
d - l1 - l2 : 从d开始，沿着left一直visit下去（注意将right入栈）；
r2 - r1 : 看成一个Stack，r2最后入栈，但最先访问；
访问r2时，同样从r2开始，沿着left一直visit下去（注意将right入栈）；
(1) 基本顺序
D
/ \
L R
先序遍历： L --> D --> R
(2) 通过迭代实现：
/ d
/ / \
/ l1 r1
/ / \
/ l2 r2
/ => 对任何以d为根节点的子树，执行以下过程（称之为LDR过程）：
因为需要访问完L后才能访问D，故先将L(d,l1,l2)按斜线方向入栈（即沿left入栈）；
然后每个出栈的节点，先访问，再转向R(r2,r1)，再将R当成新子树的根节点d，执行LDR过程；
中序遍历 : l2 - l1 - r2 - d - r1
Stack示例 : 将L一直入栈，直至栈为 [d - l1 - l2>，然后弹出l2，访问l2，转向l2->right；
l2->right为nullptr，故不需要将L入栈，继续弹出l1，访问l1，转向l1->right；
l1->right不为nullptr，故需要将L入栈，然后......；
一直重复上述过程即可；
(1) 基本顺序
D
/ \
L R
先序遍历： L --> R --> D
(2) 通过迭代实现：
/ d
/ / \
/ l1 r1
/ / \
/ l2 r2
/ => 对任何以d为根节点的子树，执行以下过程（称之为LRD过程）：
因为需要访问完L后才能访问R，访问完R后才能访问D，故先将L(d,l1,l2)按斜线方向入栈（即沿left入栈）；
对每个出栈的节点：
<1>如果：没有右子树，或者右子树已经访问完毕，则访问之，然后继续弹出节点，继续<1>过程；
<2>否则：转向R(r2,r1)，再将R当成新子树的根节点d，执行LRD过程；
后序遍历 : l2 - r2 - l1 - r1 - d
层次遍历即是“一行接一行”地遍历；
d
/ \
l1 r1
/ \
l2 r2
层次遍历 : d - l1 - r1 - l2 - r2
将遍历的顺序，看成一个队列：d最先入队，故最先访问；
r2最后入队，故最后访问；
二叉树接口
二叉树的基本操作，可以沿用至接下来要讲的Binary Search Tree等，这里列个表总结下。
| 内容 | 接口 |
|---|---|
| 二叉树节点 | Binary Node |
| 节点高度 | Binary Node Height() |
| 树节节点 | Binary Tree Root() |
| 先序遍历 | Binary Tree PreOrder() |
| 中序遍历 | Binary Tree InOrder() |
| 后序遍历 | Binary Tree PostOrder() |
| 层次遍历 | Binary Tree LayerOrder() |
Binary Search Tree
二叉搜索树(BST)，着重于查找，而且是快速的查找。
查找节点
- 查找的优势
为了快速查找，做如下约定：
D
/ \
L R
对于二叉树的任何一个节点，有大小关系： L <= D <= R，即BST的中序遍历是有序的；
这样，二叉搜索树的查找，每经过一次比较，就能减小一半的查找范围（和二分查找法类似了）。
简单C式的代码实现：
Node* Search (Node* x, Data ele)
{
if (!x || x->data == ele)
return node;
return Search(x->data < ele ? x->left : x->right);
}
- 查找的不足
对于单链二叉树，二叉搜索树的查找优势就没了，如：
r
\
r1
\
r2
...
二叉搜索树就成了线性查找了。
基于二叉搜索树的优势与不足，我们需要做如下思考：
为了保证二叉搜索树的优势，对于树中的每一个节点，需要使得
(1). 左子树与右子树尽可能接尽满二叉树；
(2). 左子树与右子树的高度尽可能接尽；
接下来的AVL Tree、Splay Tree、RebBlack Tree均是为尽可能达到上述两点，一般统称为平衡二叉树(Balanced Binary Search Tree, BBST)。
插入节点
r
/ \
a b
/ \ / \
w x y z
/
*(NULL)
根据二叉搜索树的Search算法，最终查找得到的是一个节点，或是已存在的节点，或是NULL节点。
如：查找一个位于(a,x)区间的数据，最终返回的就是x的left节点，
即 '*' 所表示的NULL节点，将新数据插入到x->left处即可。
删除节点
- 直接后继节点
因为要保证二叉树的有序性，删除节点比插入节点稍麻烦点，需要先明白什么是节点的直接后继。
节点r在中序遍历下，其后面的节点d即为r的直接后继，如下所示：
根据有无右子树，可做如下判定，
(1)有右子树：r为当前节点，d为r的直接后继，即r右子树中最靠左（最小）的节点；
r
/ \
L a
/ \
d c
\
b
(2)无右子树：r为当前节点，d为r的直接后继，即“将r包含于其左子树中的最低祖先节点”；
e
/ \
d R
/ \
b c
/ \
a r
/
L
- 删除节点
删除节点麻烦的原因就是，删除节点后，需要找到顶替原来位置的新节点，并且能够保证中序遍历的有序性。所以，直接后继就是一个理想的顶替节点，如下所示：
待删除的节点为d，根据d的孩子节点，可以如下判定，
(1) 没有孩子节点 ： 直接删除d即可
(2) 只有左孩子节点 或 只有右孩子节点
a a
/ \ / \
T0 b T0 b
/ \ => / \
T1 d T1 c (d)
/
c
将d->right和d->left顶替在d的位置；
(3) 同时有左右孩子节点
d c
/ \ / \
T0 b T0 b
/ \ => / \
c T1 d T1
\ / \ \ / \
a T2 T3 a T2 T3
节点c为节点d直接后继，交换c和d，然后按情况(1)或(2)删除d；
通过以上图解，可以看到，直接后继节点的作用是将有两个孩子的节点，转化成最多只有一个孩子的节点。其实接替节点也可以使用如下节点：待删除节点左子树中最大的节点，或右子树中最小的节点。
BST接口
BST的查找等基本操作，各种二叉搜索树均可以沿用，这里列个表总结下。
| 特点 | 内容 |
|---|---|
| 查找节点 | BST Search() |
| 插入节点 | BST Insert() |
| 删除节点 | BST Remove() |
| 旋转调整(后面会讲) | BST Rotate() |
AVL Tree
AVL Tree即也称为AVL平衡树。这里所谓的平衡，就是直接从上一节(Binary Search Tree)中“查找节点”的(1)(2)出发，使得二叉搜索树的“形状”尽可能的接尽“等腰三角形”。
AVL平衡定义
对任一节点v，平衡的相关定义如下
理想平衡 : height(v->left) = height(v->right) 即左子树树高与右子树树高相等
平衡因子 : height(v->left) - height(v->right) 即左子树树高与右子树树高的差
AVL平衡 : -2 < 平衡因子 < 2 即平衡因子的范围为[-1,1]
AVL平衡树，即是树中所有节点均达到AVL平衡，如以下等形式：
r r r
/ \ / \ / \
a b a b a b
/ / \
c c d
失衡与复衡
- 插入节点引起AVL失衡
(1)插入节点，引起树失衡的基本情况共4种：
(1) (2) (3) (4)
g g g g
/ \ / \ / \ / \
p t t p p t t p
/ \ \ /
v v v v
/ / / /
i i i i
g,p,v,t四个节点原本可以达到AVL平衡，但插入节点i做为v的子节点后，就会引起节点g失衡；
（因为插入节点i，使得g的高度变化，从而引起g的平衡因子超范围，即引起g失衡）。
这里估且设定 g->parent 节点为 x；
(2)恢复平衡的方法，即将g,p,v三个基本节点调整到以下形状：
(1) (2) (3) (4)
p p v v
/ \ / \ / \ / \
v g g v p g g p
/ \ / / \ \ / \
i t t i i t t i
需要注意的是：
恢复平衡后，g所在位置(即现在的p,v节点处)节点的高度也会同样恢复；
所以从 x 节点以上的所有祖先节点高度均不会变化，即全树恢复平衡。
- 删除节点引起AVL失衡
(1)插入节点，引起树失衡的基本情况共4种：
(1) (2) (3) (4)
g g g g
/ \ / \ / \ / \
p t t p p t t p
/ \ \ /
v v v v
g,p,v,t四个节点原本可以达到AVL平衡，但删除节点t后，就会引起节点g失衡；
（因为删除节点t，使得g的高度变化，从而引起g的平衡因子超范围，即引起g失衡）。
这里估且设定 g->parent 节点为 x；
(2)恢复平衡的方法，即将g,p,v三个基本节点调整到以下形状：
(1) (2) (3) (4)
p p v v
/ \ / \ / \ / \
v g g v p g g p
需要注意的是：
恢复平衡后，g所在位置(即现在的p,v节点处)节点的高度可能再次发生变化，可能引起g->parent失衡；
所以，需要自 x 节点开始，沿着 parent 方向，检测所有祖先节点是否发生失衡，直至树根节点Root；
旋转调整
旋转调整(BST Rotate)是BST的基本过程，不仅可以使得AVL树恢复平衡，还可以保证AVL树中序遍历的有序性，之后的RedBlack Tree也会用到。
示意图如下(包括对称情况)：
(1)单旋:
zag(旋转gp) | zig(旋转gp)
g p | g p
/ \ / \ | / \ / \
T0 p => g v | p T3 => v g
/ \ / \ / \ | / \ / \ / \
T1 v T0 T1 T2 T3 | v T2 T0 T1 T2 T3
/ \ | / \
T2 T3 | T0 T1
(2)双旋:
zig-zag(先zig旋转pv，再zag旋转gv) | zag-zig(先zag旋转pv，再zig旋转gv)
g v | g v
/ \ / \ | / \ / \
T0 p g p | p T3 p g
/ \ / \ / \ | / \ / \ / \
v T3 => T0 T1 T2 T3 | T0 v => T0 T1 T2 T3
/ \ | / \
T1 T2 | T1 T2
(3) 代码实现思路
先根据g,p,v之间的父子节点关系，分清是哪种类型，然后代入a,b,c的位置；
同样，子节点T0~T3则代入w,x,y,z的位置。
b
/ \
a c
/ \ / \
w y x z
时间复杂度
AVL平衡树的查找、插入、删除操作，最坏情况下的时间复杂度均为O(logn)，这里的n为节点数。但AVL平衡的维持，需要额外借助高度或者说平衡因子，以及旋转操作。特别地，删除/插入节点后的旋转操作，增加了算法时间消耗。
| 操作 | 时间复杂度 |
|---|---|
| 查找 | O(logn) |
| 插入 | O(logn) |
| 删除 | O(logn) |
Splay Tree
伸展树(Spaly Tree)是通过间接的方式，使得二叉树接尽平衡。
伸展过程
伸展树的核心即是伸展，伸展过程，是基于一个这样的考量，如下图所示：
将经常访问的节点，移到树根节点Root处；这样，随着时间的推移，在Root附近将聚集越来越多的经常访问的节点，可以加快了搜索速度。同时，伸展过程最好能控制好树的高度。
* -----
/ \ Root附近聚集了经常访问的节点，可以加快搜索速度
/ \ -----
/ \
/__ \
\__ \ 访问底层的节点仍需要较长时间，最长的时间和树的高度有关，所以需要控制好树的高度
\___\ -----
- 伸展原理
伸展的目的是通基本伸展过程，使目标节点v向上移，直至成为根节点Root；
原则是优先双层伸展，直至最后只剩下一层，才使用单层伸展。
(1)双层伸展
zag-zag(先zag旋转gp，再zag旋转pv) | zig-zig(先zig旋转gp，再zig旋转pv)
g v | g v
/ \ / \ | / \ / \
T0 p => p T3 | p T3 => T0 p
/ \ / \ | / \ / \
T1 v g T2 | v T2 T1 g
/ \ / \ | / \ / \
T2 T3 T0 T1 | T0 T1 T2 T3
|
(与AVL旋转相同) | (与AVL旋转相同)
zig-zag(先zig旋转pv，再zag旋转gv) | zag-zig(先zag旋转pv，再zig旋转gv)
双旋: | 双旋:
g v | g v
/ \ / \ | / \ / \
T0 p g p | p T3 p g
/ \ / \ / \ | / \ / \ / \
v T3 => T0 T1 T2 T3 | T0 v => T0 T1 T2 T3
/ \ | / \
T1 T2 | T1 T2
(2)单层伸展
zig: | zag:
p v | p v
/ \ / \ | / \ / \
v T2 => T0 p | T0 v => p T2
/ \ / \ | / \ / \
T0 T1 T1 T2 | T1 T2 T0 T1
- 伸展效果
伸展过程既可以使目标节点聚在Root附尽，也控制好树的高度。
查找'1':
伸过数次伸展，'1'成为了根节点，而树的高度也减小了一半；
8 8 8 8 1
/ / / / => \
7 7 7 1 (伸展1,8) 8
/ / / \ /
6 6 6 6 6
/ / / => / \ / \
5 5 1 (伸展1,6,7) 4 7 4 7
/ / \ / \ / \
4 4 => 4 2 5 2 5
/ / (伸展1,4,5) / \ \ \
3 1 2 5 3 3
/ => \ \
2 (伸展1,2,3) 2 3
/ \
1 3
查找'3':
伸过数次伸展，'3'成为了根节点，'1'仍在根节点附近，树的高度再度减小一半；
1 1 1 3
\ \ \ => / \
8 8 3 (伸展1,3) 1 6
/ / / \ \ / \
6 6 => 2 6 2 4 8
/ \ / \ (伸展3,6,8) / \ \ /
4 7 3 7 4 8 5 7
/ \ => / \ \ /
2 5 (伸展3,2,4) 2 4 5 7
\ \
3 5
查找、插入、删除
查找过程中刚查找的节点，插入过程中新插入的节点，删除过程中待删除的节点，均可认为是经常访问的节点。值得注意的是，伸展树的查找、插入、删除，依靠查找操作均会改变树的拓扑结构（因为都会进行伸展过程）。
- 插入与删除节点
a r
/ \ \
b c a
/ \ => / \
d e Splay d c
/ \
r b
\
e
若插入的节点x(x<r)：先查找x，最终会到达r节点，之后将r伸展到根节点，然后将x作为r的左孩子插入树中。
若要删除节点r： 同样先查找r，最终会到达r节点，之后将r伸展到根节点，然后删除r，重新合并r的左右子树。
相对于AVL平衡树，伸展树不需要平衡因子，更易编程实现，而伸展树查找、插入、删除的时间复杂度同样为O(logn)，与AVL平衡树相当。
| 操作 | 时间复杂度 |
|---|---|
| 查找 | O(logn) |
| 插入 | O(logn) |
| 删除 | O(logn) |
RebBlack Tree
红黑树，顾名思义，就是节点有颜色的二叉搜索树。
基本性质
红黑树约定：
- 1.树根：必为黑；
- 2.外部节点(NIL节点)：均为黑（外部节点，或说NIL节点，即是一个为NULL的黑色叶子节点）；
- 3.其余节点：若为红，则子节点只能为黑；
- 4.从任一节点到其每个（子孙）外部节点：途中路径经过的黑节点数相同；
红黑树的查找沿用BST的Search即可；不过，对于红黑树的每次插入/删除节点，均要保证上述4点仍然成立。
AVL树为了保证平衡因子在[-1,1]之间，失衡时需要进行较多的旋转操作。红黑树相对于AVL树来说，牺牲了部分平衡性，以换取减少插入/删除时旋转操作，整体性能优于AVL树。
插入节点
插入节点需要先用BST Search得到新节点插入的位置。新插入的节点均初始化为红色（如果设为黑色，就会导致根节点到NIL节点的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换和树旋转来调整）。根据临近节点的颜色，进行相应的调整。
插入节点示意图：
设新插入节点为x，x的父节点为p，p的父节点为g，x的叔父节点为u(也即p的兄弟节点)；
带有R的节点为红，未做特殊说明则为黑；
x为红，p为黑，则节点插入完成；
x为红，p也为红，即为双红冲突问题。
(1) (2) (3) (4)
g g g g
/ \ / \ / \ / \
pR u pR u u pR u pR
/ \ / \
xR xR xR xR
双红问题普遍情况有以上4种，且均是两两对称形式，调整方法是类似的；
还有特殊情况就是，新插入的节点x就是根节点。
针对不同的情况，进行相应的调整（以第(1)(2)种情况为例，(3)(4)情况对称，调整类似）：
- (RR1)x是Root节点
xR => xB
将x染成黑色即可。
- (RR2)p为红（则g必为黑），u为黑（子树T3的根节点为u）
p,x均为红，违返了约定3；直接将x染成黑，则违反了约定4。
先用BST Rotate的单旋zig，再重染色 | 先用BST Rotate的双旋zig-zag，再重染色
g | g
/ \ p | / \ x
pR T3[u] / \ | pR T3[u] / \
/ \ => xR gR | / \ => pR gR
xR T2 / \ / \ | T0 xR / \ / \
/ \ T0 T1 T2 T3(u) | / \ T0 T1 T2 T3(u)
T0 T1 | T1 T2
调整前，T0~T3向上的第一个黑节点为子树根节点g；
变换后，T0~T3向上的第一个黑节点为仍为子树根节(p或x)，同时满足约定3和4；
故调整前后，子树根节点到（子孙）外部节点所经过的黑节点数不变。
- (RR3)p为红（则g必为黑），u为红（子树T3的根节点为u）
重染色，递归检测g的双红问题
g gR | g gR
/ \ / \ | / \ / \
pR T3[uR] p T3[u] | pR T3[uR] p T3[u]
/ \ => / \ | / \ => / \
xR T2 xR T2 | T0 xR T0 xR
/ \ / \ | / \ / \
T0 T1 T0 T1 | T1 T2 T1 T2
调整前后，pu变黑，但g变红，故从g到其每个（子孙）外部节点上的黑节点数量仍不变；
但因为g的父节点可能为红，故需要继续对g进行双红检测。
删除节点
删除节点同样需要先用BST Search得到待删除节点的位置，然后用BST Remove删除节点。之后再根据删除节点和接替节点的颜色，进行相应的调整。
删除节点示意图：
设x为待删除的节点，r为接替x所在位置的节点（且r为其所在子树的根节点），p为x父节点，s为x兄弟节点；
带有R的节点为红，未做特别说明则为黑；
根据BST Remove算法，在删除x时，x必定最多只有一个子树分支。
x红，r黑，p黑 | x黑，r红，p红或黑
p p | p p
/ \ / \ | / \ / \
s xR => s T[r] | s x => s T[r]
\ | \
T[r] | T[rR]
若x和r只有一个为红，则将r染黑即可；
若x和r均为黑，删除节点x后，节点p-r所在路径的黑节点数少了1，此即为双黑问题。
双黑调整原理：通过旋转和染色，使得节点p-r所在路径黑节点数加1，
或使得节点p-s所在路径黑节点数减1，再递归调整。
针对不同的双黑情况，进行相应的调整：
- (BB1)s为黑，且s至少有一个红子节点，p可黑可红
先BST Rotate，再染色：
s继承p的颜色，tp变黑 | t继承p的颜色，sp变黑
p | p
/ \ s | / \ t
s T3[r] / \ | s T3[r] / \
/ \ => t p | / \ => s p
tR T2 / \ / \ | T0 tR / \ / \
/ \ T0 T1 T2 T3[r] | / \ T0 T1 T2 T3[r]
T0 T1 | T1 T2
调整前后，T0~T3到子树根节点经过的黑节点如下所示：
T0 - s - p T0 - t - s | T0 - s - p T0 - s - t
T1 - s - p => T1 - t - s | T1 - s - p => T1 - s - t
T2 - s - p T2 - p - s | T2 - s - p T2 - p - t
T3 - x - p T3 - p - s | T3 - x - p T3 - p - t
可以看到，在调整后，节点p-r所在路径黑节点数加了1（即节点s或t）。
且不改变T0~T2所在路径黑节点的数量。
- (BB2.1)s为黑，且s两个子节点均为黑，p为红
重染色：s变红，p变黑
pR p
/ \ / \
s T2[r] => sR T2[r]
/ \ / \
T0 T1 T0 T1
s变红，p-s所在路径黑节点数减1；
p变黑，p-s和p-r所在路径黑节点数均加1；
最终，p-s和p-r所在路径黑节点数不变；
- (BB2.2)s为黑，且s两个子节点均为黑，p为黑
重染色（s变红），再递归对p进行双黑检测；
p p
/ \ / \
s T2[r] => sR T2[r]
/ \ / \
T0 T1 T0 T1
s变红，p-s所在路径黑节点数减1；
p颜色不变，所以p-s和p-r所在路径的黑节点数均减1，故需要对p继续进行双黑检测。
- (BB3)s为红，则p必为黑，s子节点必为黑
先旋转：t选取与s同侧的（s为p的左子节点，则t也选s的左子节点），这样只需要一次旋转；
再染色：s变黑，p变红；
再对r进行双黑检测：因为p为红，故以pR-T2-T3形成的子树必为(BB1)或(BB2.1)情况。
p
/ \ s
sR T3[r] => / \
/ \ t pR
t T2 / \ / \
/ \ T0 T1 T2 T3[r]
T0 T1
p变红，p-r所在路径黑节点数再次减少了1，共减少了2；
s变成p的父节点，p-r所在路径黑节点数加1，共减少了1，故需要对r继续进行双黑检测。
附：代码实现
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 [ yehuohan@gmail.com ]