二叉搜索树和平衡二叉树

二叉搜索树（BST）

对于每个节点，左子树中所有值均小于自己，右子树中所有值均大于自己。中序遍历一棵 BST，即能得到有序的数据。
所以对于查找来说，将相当于是根据中序遍历的结果进行操作：
- 查找指定 key：当前节点小于 key，向右查找，否则向左查找。
- 查找最小 key：不停向左查找。
- 查找后继：右子树的最左节点；如果没有右子树，则向上查找直到自己所在的子树是某个节点的左子树。
插入：从根节点开始，当前节点小于待插入的值，就向右，否则向左，直到遇见 null 为止，就是正确的插入位置。
删除分三种情况：
- 待删除的节点没有儿子：直接删除
- 待删除的节点有一个儿子：将儿子提升到被删除的节点原来的位置
- 待删除的节点有两个儿子：找到被删除节点的后继，将其提升到被删节点原来的位置。（相当于将后继提升上来再删除后继）
  - 如果后继就是右儿子，就直接将右儿子提升上来
  - 如果后继不是右儿子，先将后继提升上来，再将后继的右子树变成后继原先父节点的左子树（后继一定是其原先父节点的左儿子，且自己没有左儿子）
BST 操作的时间复杂度和树高成正比，最坏情况下会退化成链表，时间复杂度也就退化成了 O(n)，有很多改进版的 BST 可以让树尽量平衡，比如 SBT，AVL 树，红黑树。
reference

Size Balanced Tree（SBT）

平衡树的一种，通过保证每棵子树的大小大于其侄子子树的大小来保证平衡，即
Code
1
2
s[T.right] ≥ s[T.left.left], s[T.left.right]
s[T.left] ≥ s[T.right.right], s[T.right.left]

保证不了任一节点对应的两棵子树的最大高度差为 1，反例：

Code

        o
       / \
      /   \
     /     \
    /       \
   A         o   
  / \       / \
 /   \     /   \
o     o   B     o
         /       \
        o         o
       /           \
      o             o

如 A 节点对应的子树大小为 3，B 节点是 A 节点的侄子，对应的子树大小也为 3。但是根节点的左右两棵子树高度差为 2。

问题在于只限制了子树的大小关系，一棵子树可以每层铺满，像完全二叉树那样，而另一棵可以一直往下长，这两棵子树虽然大小接近，但是高度会越差越大。

AVL Tree

任何一个节点的左右两棵子树高度差不能超过 1。
定义某节点的平衡因子为该节点左子树高度减去右子树高度，显然 AVL 树的任意节点平衡因子绝对值小于等于 1。
在插入节点时，可能会导致多个节点失衡（平衡因子绝对值大于 1），找到最小失衡子树，将其旋转以达到重新平衡：
- 如果左子树比右子树高，就右旋：右旋节点的左儿子上升到右旋节点的位置，左儿子的右子树变成右旋节点的左子树，右旋节点变成原先左儿子的右儿子。
- 如果右子树比左子树高，就左旋。

但有时仅旋转一次是不够的，而且也不能只旋转失衡子树，考虑这样一棵树：

Code

    A                        A                          E
   / \                      / \                        / \
  B   C                    E   C                      B   A
 / \           -->        /               -->        / \   \
D   E                    B                          D   F   C
   /                    / \
  F                    D   F

节点 F 的插入导致节点 A 成为最小失衡节点，试图右旋 A，但是发现旋转完了以后 B 又失衡了。所以正确的旋转方式是先左旋 B（尽管一开始 B 并没有失衡），然后再右旋 A。

总结一下，有四种旋转方式，对应着四种由插入导致的平衡被破坏的情况：

插入方式	旋转方式
插到左儿子的左子树（LL）	右旋根节点
插到右儿子的右子树（RR）	左旋根节点
插到左儿子的右子树（LR）	先左旋左儿子，再右旋根节点
插到右儿子的左子树（RL）	先右旋右儿子，再左旋根节点

表格中的根节点即为最小失衡子树的根节点。

删除的情况和 BST 一样，删除后如果失衡了需要重新平衡，按照上述表格操作即可。
reference

红黑树

红黑树中，
- 每个节点要么是红色，要么是黑色
- 根节点是黑色
- 红色节点不能连续（即红色节点儿子必须是黑色）
- 对于任一节点，从该节点向下遍历至任一叶子节点所经过的黑色节点个数必须相等。
红黑树能保证任意节点左右两棵子树中，高的那个也不会比矮的那个两倍还高。可以这么理解，左右两棵子树遍历到叶子节点的路径要确保黑色节点个数相同，而红色节点又不能连续，所以最长路径是一黑一红交叉出现，而最短路径是全黑，所以长的路径最多是短的路径的两倍长。
红黑树中新插入的节点一定是红色的，如果插到黑色节点上，没有违反任何一条性质，不用修复；如果插到红色节点上，需要根据不同情况进行修复（先将新插入的节点标为待修复节点，并假设父节点为祖父节点的左儿子（若为右儿子由对称性同理可得））：
- 待修复节点的父节点为红色，叔叔节点也为红色：将父亲和叔叔节点都改为黑色，祖父节点改为红色，并将祖父节点标记为待修复节点。
- 待修复节点的父节点为红色，叔叔节点不存在或为黑色（其实空节点也算黑色节点），且待修复节点是其父节点的右儿子：将父节点标记为待修复节点，然后左旋父节点。
- 待修复节点的父节点为红色，叔叔节点不存在或为黑色，且待修复节点是其父节点的左儿子：将父节点改为黑色，祖父节点改为红色，并右旋祖父节点。
重复上述过程直到待修复节点的父节点变成黑色（待修复节点永远为红色）。需要注意的是第二种修复手段执行后必须立刻第三种修复手段再进行下一次是否需要修复的判断（即修复二的结果必将导致修复三的条件出现）：
Code
1
2
3
4
5
6
7
|-------> 1 ----->|
| |
---->|--> 2 ---| |---->
^ | v | |
| |-------> 3 ----->| |
| v
<----------------------------
从红黑树中删除一个节点比较麻烦，前面说过 BST 的删除分三种情况：
- 待删除节点没有儿子：如果该节点是红色节点，正常删除，不需要修复；如果该节点是黑色节点，将该节点被删后留下的空节点标记为待修复节点。
- 待删除节点有一个儿子：如果该节点是红色节点，正常删除并将儿子节点接上来，不需要修复；如果该节点是黑色节点，删掉并将儿子节点接上来后，将儿子节点标记为待修复节点。
- 待删除节点有两个儿子：这种情况本质上是将待删节点的后继提升上来再删除后继，而后继提升上来以后只要继承被删节点的颜色，则被删节点局部的颜色其实没有发生改变，所以这个问题可以化归成删除后继节点，又因为后继节点没有没有左儿子，所以实际上就是待删节点只有一个儿子的情况。
总结一下就是 BST 删除的三种情况可以化归成两种，但是细看一下第一种和第二种好像也没啥区别，所以结论就是如果被删节点是红色的，正常删除，不需要修复；如果被删节点是黑色的，删除并将删除操作发生的节点标记为待修复节点（第一种情况删除发生在叶子节点，被删后待修复节点标记在空节点上；第二种情况删除发生在有一个儿子节点的父节点，被删后待修复节点标记在提升上来的儿子节点上）。下面进行修复。

修复的最终目标是将被顶替的黑色节点中的黑色赋给另外的节点以达到平衡。

首先，如果待修复节点是根节点或者红色节点，直接涂黑，完成修复（也即红 + 黑修复成黑）。

如果待修复节点是黑色节点（即黑 + 黑），就不能将这个多余的黑色赋给自己，需要另寻别的节点，分四种情况：

待修复节点的兄弟节点是红色：此时父节点必为黑色，交换父节点和兄弟节点的颜色并左旋父节点（左旋父节点导致兄弟节点的一个孩子跑到自己这里来了，因为兄弟节点是红色，所以其孩子是黑色，这一步相当于抢了兄弟节点一个黑色孩子）
待修复节点的兄弟节点是黑色，且兄弟节点的儿子均为黑色：将兄弟节点涂红，待修复节点变为父节点（即底下这一层子树修复好了，向上修复）
待修复节点的兄弟节点是黑色，且兄弟节点的儿子左红右黑：交换兄弟节点和兄弟节点左儿子的颜色并右旋兄弟节点（为了方便第四步操作）
待修复节点的兄弟节点是黑色，且兄弟节点右儿子为红色：将兄弟节点的黑色给他的右儿子，将父节点的颜色给兄弟节点，将自己多余的黑色给父节点并左旋父节点（注意这一步多余的黑色已经给出去了，所以修复必然结束）

如此循环直到待修复节点变成根节点或者红色节点，循环结束后将待修复节点涂黑，完成修复。整个循环大致是这样：

Code

|<------------------------------------
|                                    ^
|   |---> 1 ---|  |-------> 2 ------>|
v   |          v  |                  |
---------------------> 3 ---|        |
                  |         v        v
                  |-------> 4 --------->

只可能由第二步或第四步导致循环退出，因为第二步中会上移待修复节点，第四步中会直接给掉多余的黑色（可以通过将待修复节点赋成根节点来强制退出循环）

需要注意的是空节点也被认为是黑色节点，将空节点涂红它还是空节点，且上述方法适用于待修复节点为其父节点的左儿子的情况，若为右儿子由对称性同理可得。

references: