查找树
查找树
sschrodinger
2019/08/16
二叉查找树
二叉查找树（BST）是一棵二叉树，其中每一个节点都包含一个 Comparable 的键（以及其相关的值），且每个节点的键都大于其左子树中的任意节点的键而小于右子树的任意节点的键（即不允许重复）。
如下：
8ed5b0f1fbce498dc80646d75a76d7e.jpg
基本操作
get() 操作
使用 public Value get(Key key) 定义，获得当前 key 的值。实现非常简单，直接递归就行。
put() 操作
使用 public void put(Key key, Value value) 定义，找打当前的 key 并更新，没有找到则者新建节点
min()/max() 操作
使用 public Node min(Node root) 和 public Node max(Node root) 定义，返回 root 中的最小键或者最大键。
如下递归方式可以实现返回最小键：
- 如果根节点的左链接为空，那么这棵树的最小键就是根节点。
- 否则，最小键就是左连接中的最小键
floor(Key key)/ceiling(Key key) 操作
使用 public Node floor(Key key) 和 public Node ceiling(Key key) 定义，返回 root 中该键的向下取整值或者向上取整值。
使用如下的递归方式可以实现 floor(Key key)：
- 如果给定的 key 小于二叉树的根节点的键，那么 floor(key) 一定在左子树中；
- 如果给定的 key 大于根节点，那么只有当根节点右子树中存在小于等于 key 的节点时， floor(key) 才在右子树中，否则根节点就是 floor(key)
如下：
[图片上传中...(1f66416af4b09e8800514d478942357.jpg-7d32d3-1566027254035-0)]
select()/rank() 操作
选择操作使用 public Node select(int index)，选择出排名为 k 的键（即树中正好有 k 个小于他的键）。
为了完成该功能，需要对 Node 节点进行扩充，增加属性 N，代表以该节点为根的子树中的节点总数。
可以使用如下的递归方式找到元素：
- 如果左子树中的节点个数 t > k，继续递归的在左子树查找排名为 k 的键，
- 如果等于 k，返回根节点
- 如果 t < k，递归右子树查找排名为 (k - t - 1) 的键
如下：
1f66416af4b09e8800514d478942357.jpg
排名操作使用 public int rank(Key key)，判断该 key 的排名是多少。
- rank(key) 返回该 key 对应的排名 k
- 如果key 和根相等，返回左子树节点总数 t
- 如果 key 小于根，返回该 key 在左子树的排名
- 如果 key 大于根，返回 t + 1 + 右子树的排名
delete() 操作
首先考虑删除最大键(deleteMax())/最小键(deleteMin())。
由 public Node deleteMax(Node root) 和 public Node deleteMin(Node root) 定义，分别返回被删除之后的树的根节点
最小键一定是没有从根开始遍历没有左子树的节点（左子树的节点一定小于根节点），那么我们就需要不断深入根节点的左子树直到遇到一个空连接，然后将指向该根节点的链接指向该节点的右子树。
如下：
ed6634fb18276565ad2c53fe31dd9eb.jpg
最大键同理。
接下来是其他节点的删除。我们可以使用删除最大键/最小键的思路删除任何只有一个子节点（或者没有子节点）的节点。
但是如果删除的节点有两棵子树，但是删除之后只有一个空出来的链接。删除节点 x 后，可以用他的后继节点填补他的位置。
因为 x 有一个右子节点，因此他的后继节点就是右子树的最小节点。这样的替换仍然能够保证树的有序性，因为 x.key 和他的后继节点的键之间不存在其他的键，而且我们可以通过删除最小键来删除右子节点最小的键。
我们可以通过如下的四个步骤实现节点的删除：
- 将指向即将被删除的节点链接保存为
t- 将
x指向他的后继节点min(t.right)- 将
x的右链接（原本指向一棵所有节点都大于x.key的二叉查找树）指向deleteMin(t.right)，也就是在删除节点之后所有的节点仍然大于x.key的子二叉查找树- 将
x的左链接（本为空）设为t.left（其下所有的键都小于被删除的节点和他的后继节点）
如下：
754b0783e44b2bbcc764e4f2ff2426f.jpg
在实际工程中，也可以使用前驱节点，随机的选用前驱节点和后继节点，以提高效率。
平衡查找树
二插查找树在极端情况下会导致树的不平衡，导致查找效率降为 O(n)，所以需要在创建树的时候保证树的平衡，使得平均查找效率接近 O(logn)。所以提出了 AVL 树和 RB-Tree（红黑树），保证树的相对平衡。
AVL 树
AVL 树，也称平衡二叉搜索树，AVL 是其发明者姓名简写。AVL 树属于树的一种，而且它也是一棵二叉搜索树，不同的是他通过一定机制能保证二叉搜索树的平衡，平衡的二叉搜索树的查询效率更高。
- AVL 树是一棵二叉搜索树。
- AVL 树的左右子节点也是 AVL 树。
- AVL 树拥有二叉搜索树的所有基本特点。
- 每个节点的左右子节点的高度之差的绝对值最多为1，即平衡因子为范围为 [-1,1]。
在增加节点或者删除节点的时候会导致树高的变化，需要在这两个地方保证树高的平衡。
AVL 树的添加
AVL 树有四种添加方式导致不平衡。
- LL 插入方式，插入的节点在 Z 节点的左子树的左子树上
- RR 插入方式，插入的节点在 Z 节点的右子树的右子树上
- LR 插入方式，插入的节点在 Z 节点的左子树的右子树上
- RL 插入方式，插入的节点在 Z 节点的右子树的左子树上
平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。
最小失衡子树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过1的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的，如下。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。
LL 方式通过右旋转的方式让树保持平衡，如下：
image.png
RR 方式通过左旋转的方式让树保持平衡，如下：
image.png
LR 方式通过左右双旋让树保持平衡：
首先以根节点的左节点做左旋转，得到一个 LL 树，如下：
image.png
接着，对 LL 树做右旋转，让树保持平衡，如下：
image.png
RL 方式通过右左双旋让树保持平衡，是 LR 方式的对称。
==综上，对于 AVL 来说，添加操作总能通过最多两次旋转来保证树的平衡。==
AVL 树的删除
在 AVL 树中，采用普通二叉树的方式删除节点，只是需要在不平衡时对二叉树的平衡进行调整。需要删除的节点在较低子树上时，会直接导致树的不平衡。
当调整了最小不平衡树时，有可能会使得子树变得更矮，那么需要再次调整，如下（删除节点 6）：
删除节点 6 之后变成，如下：
1CD96D7859A692DB489FC229A0469244.png
这时，最小不平衡树为节点 5，调整节点 5，如下：
6B9BE20E4DFFA27E54E99D2AD48BAC3D.png
这时，节点 10 又变成了最小不平衡树，需要继续调整（左旋转），如下：
C2995A894CBB833D12C8145C2774D1C6.png
==综上，AVL 树的删除有可能导致整棵树的级联旋转。==
RB-tree 红黑树
首先，我们引入一棵多叉树，2-3 树，来解释红黑树的实现原理。
2-3 查找树
利用树进行查找时，希望树尽量的平衡，这样才能够保证在每一次的查找保证 $O(logn)$ 的复杂度。在动态插入的过程种要维持平衡二叉树的代价太高，所以使用一种新型的平衡树 - 2-3 查找树。
对于一个二叉查找树，他的每一个节点有一个值和两条连接，左连接指向的二叉查找树的值都小于该节点，右连接指向的二叉查找树的值都大于该节点，对于一个整数类型的数组 int[] a = new int[] {1,2,3,4,5,6,7}，他所构成的平衡二叉查找树如下所示：
平衡二叉查找树
现引入 2-3 查找树，定义如下：
定义
- 为一棵空树或由以下节点组成
- 2-节点，含有一个值和两条连接，左连接指向的 2-3 树中的值都小于该节点，右连接指向的 2-3 树的值都大于该节点（类似于查找二叉树）
- 3-节点，含有两个值和三条连接，左连接指向的 2-3 树中的值都小于该节点，中连接指向的 2-3 树的值位于该节点的两个值之间，右连接指向的 2-3 树的值都大于该节点
对于一个字符数组 char[] chars = new char[] {A,C,H,L,P,S,X,E,J,R,M}，他的平衡 2-3 树如下所示：
平衡2-3树
查找
2-3 树查找过程和二叉树相似，略。
添加
在一个只有根节点且是 2-节点的树上添加元素。为了保证平衡，我们需要将该节点替换成一个 3-节点，如下所示：
根-2节点添加
在一个只有根节点且是 3-节点的树上添加元素。为了保证平衡，我们需要将该节点做局部变化，操作如下：首先将该节点临时增加一个值变成 4-节点，然后对四节点进行拆分，变成 3 个 2-节点，如下所示：
根-3节点添加
在一个父节点且是 2-节点，该节点是3-节点的树上添加元素。为了保证平衡，我们需要将该节点做局部变化，操作如下：首先将该节点临时增加一个值变成 4-节点，然后对四节点进行拆分，变成 3 个 2-节点，最后将一个 2-节点 和 父节点合并，如下所示：
2-父 3-子
在一个父节点是 3-节点，该节点是3-节点的树上添加元素。为了保证平衡，我们需要将该节点做局部变化，操作如下：首先将该节点临时增加一个值变成 4-节点，然后对四节点进行拆分，变成 3 个 2-节点，最后将一个 2-节点 和 父节点合并然后递归的对父节点进行操作，直到根节点或者父节点是 2-节点停止，如下所示：
3-父 3-子
删除
由此可见， 2-3 树是由下向上生长的，但是删除操作需要对树进行从上和从下两方面的判断，相对来说，删除非常费时。
红黑树
红黑树是 2-3 树的一种特殊实现，使用标准的查找二叉树代替和一些额外的信息来表示 2-3 树。我们将树中的链接分为两种类型：红连接将两个 2 节点链接起来构成三节点，黑连接代表普通连接。标准定义及性质如下：
- 红连接均为左连接
- 没有任何一个节点同时和两条红连接相连
- 该树是黑色完美平衡的，及任意空连接到根节点的路径上的黑连接数量相同
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（黑节点的数目称为黑高black-height）
因为红连接总为左链接，并且不会有两个节点同时和红连接相连，所以根节点一定是黑连接。
在每一个节点的内部，维护了一个颜色信息，用于存储该节点到他的父节点的节点的链接颜色，如果该节点是红色，则代表他和父节点组成一个 3 节点，为了方便理解，我们可以把红色链接画平，如下：
2BB9B6028D7B5E7804E3A188C7BE8931.png
红黑树的插入
每次将一个节点插入到红黑树时，总会构造一个红色节点插入到红黑树(除了在没有节点时，会直接创建根为黑色的节点)中，但是我们需要对颜色进行调整。
可能会出现两种情况，第一种情况是出现红色右链接，第二种情况是出现两个相连的红连接。需要通过左旋转或者右旋转修复。
我们定义左旋转是将一条红色的右连接旋转得到一条左连接。右连接相反，如下图所示：
左旋转
左旋转的伪代码如下所示：
Node rotateLset(Node h) {
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = red;
}
只需更改他的 color 属性为红，并将他原来自身的 color 属性赋值给右连接节点就行。
同理，右连接示意图如下：
右旋转
NOde rotateRight(Node h) {
node x= h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = read;
}
对于每一个插入，都插入一个红连接。
向单个 2-节点中插入新键。如果新键小于老键，则增加一个红色左连接，否则增加一个红色右连接并进行左旋转，两种情况都能产生一个等效的3-连接，如下所示：
单个2-节点中插入新键
向树底部的 2-节点中插入新键。总是增加一个新的红色连接，如果他的父节点是 2-节点，那么按照如上两种方式调整节点就行。
向一棵双键树（3-节点）中插入新建，分为了三种子情况，第一种情况是新键最大，第二种情况是新键在中间，第三种情况是新键最小。
如下如所示：
3-节点
对于一个节点和两个红色连接直接相联，这种情况等效于一个 4-节点，当将这两个红色连接变黑时，需要将父节点由黑变红，因为这样的变换会在父节点产生一个 3-节点，理由如下：
颜色变换
每产生一个红色连接都会向上传递直到根节点。
==综上，在插入一个节点时，红黑树最多做两次旋转，但是，可能会递归的改变颜色直到根节点==
==从 2-3 树，我们可以看出，在一个路径上，红色节点一定小于等于黑色节点，并且一个路径上可以允许没有红色节点，设 红色节点为 red-num, 黑色节点为 black-num，路径长为 path，则有 0 <= (black-num - rednum) <= path==
红黑树/AVL 树对比
- 如果插入一个 node 引起了树的不平衡，AVL最多只需要 2 次旋转操作，复杂度
O(1), RB-Tree 最坏需要O(logn)复杂度；在删除 node 引起树的不平衡时，最坏情况下，AVL 需要维护从被删 node 到 root 这条路径上所有 node 的平衡性，因此需要旋转的量级O(logN)，而 RB-Tree 最多只需 3 次旋转，只需要O(1)的复杂度。- 其次，AVL 的结构相较 RB-Tree 来说更为平衡，在插入和删除 node 更容易引起 Tree 的 unbalance，因此在大量数据需要插入或者删除时，AVL 需要 rebalance 的频率会更高。因此，RB-Tree 在需要大量插入和删除 node 的场景下，效率更高。自然，由于 AVL 高度平衡，因此 AVL 的 search 效率更高。
map 的实现只是折衷了两者在 search、insert 以及 delete 下的效率。总体来说，RB-tree 的统计性能是高于 AVL 的。
