平衡树

平衡树是一类改进的二叉查找树。一般的二又查找树的查询复杂度是跟目标结点到树根的距离（即深度）有关，因此当结点的深度普遍较大时，查询的均推复杂度会上升，为了更高效查询，平衡树应运而生了。在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均复杂度偏低

2-3查找树

2-3 查找树是一种能够在动态插入当中保持完美平衡的数据结构，完美平衡即树中的所有空链接到根节点的距离都是相同的。在一棵大小为 N 的 2-3 树中，查找和插入操作访问的结点必然不超过logN个，为了保证查找树的平衡性，我们需要一些灵活性，因此在这里我们允许树中的一个结点保存多个键。
一颗2-3 查找树或为一颗空树，或由以下结点组成

• 2-结点，含有一个键（及其对应的值）和两条链接，左链接指向的 2-3 树中的键都小于该结点，右链接指向的 2-3 树中的键都大于该结点
• 3-结点，含有两个键（及其对应的值）和三条链接，左链接指向的 2-3 树中的键都小于该结点，中链接指向的 2-3 树都位于该结点的两个键之间，右链接指向的 2-3 树中的键都大于该结点

注意：至于 4-结点，则以此类推是含有三个键（及其对应的值）和四条链接，四条链接代表了从小到大的四个范围，这四个范围用三个键切分开

将指向一颗空树的链接称为空链接，一颗完美的 2-3 査找树中的所有空链接到根节点的距离应该是相

查找

要判断一个键是否存在树中，先将它和根节点中的键比较，如果它和其中任意一个相等，查找命中；否则就根据比较的结果找到指向相应区间的连接，并在其指向的子树中递归地继续查找，如果找到了空连接上，查找未命中。

在这里插入图片描述

插入

插入之前，先要对2-3树进行一次未命中的查找:

1. 向2-节点中插入新键：
   如果未命中查找结束于一个2-节点，直接将2-节点替换为一个3-节点，并将要插入的键保存在其中

   
   在这里插入图片描述

2. 向一颗只含3-节点的树中插入新键：
   先临时将新键存入唯一的3-节点中，使其成为一个4-节点，再将它转化为一颗由3个2-节点组成的2-3树，分解后树高会增加1

   
   在这里插入图片描述

3. 向一个双亲节点为2-节点的3-节点中插入新键
   先构造一个临时的4-节点并将其分解，分解时将中键移动到双亲节点中(中键移动后，其双亲节点中的位置由键的大小确定)

   
   在这里插入图片描述

4. 向一个双亲节点为3-节点的3-节点中插入新键
   一直向上分解构造的临时4-节点并将中键移动到更高层双亲节点，直到遇到一个-2节点并将其替换为一个不需要继续分解的3-节点，或是到达树根(3-节点)。

   
   在这里插入图片描述

5. 分解根节点
   如果从插入节点到根节点的路径上全是3-节点，根将最终被替换为一个临时的4-节点，将临时的4-节点分解为3个2-节点，分解后树高会增加1
   [图片上传失败...(image-fbea0e-1599500385478)]

删除

插入之前，先要对2-3树进行一次命中的查找:

1. 删除非叶子节点key
   [图片上传失败...(image-ed24e3-1599500385478)]
2. 除叶子节点key（四种情况）

红黑二叉查找树

核心

红黑二叉查找树背后的基本思想是用标准二叉查找树(完全由2-节点构成)和一些额外的信息(替换3-节点)来表示2-3树。

红黑树中的链接分为两种:

1. 将两个2-节点连接起来构成3-节点的红链接
2. 2-3树中的普通链接为黑链接

将两个-2节点用左斜的红色链接链起来可表示3-节点

一种等价的定义:

红黑树的另一种定义是含有红黑链接并满足下列条件的二又查找树

1. 红链接均为左链接
2. 没有任何一个结点同时和两条红链接相连
3. 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同

一一对应

1. 果将一颗红黑树中的红链接画平，那么所有的空链接到根节点的距离都是相同的
2. 果将由红链接相连的节点合并，得到的就是一颗2-3树

3. 红黑树即是二叉查找树又是2-3树

   
   在这里插入图片描述
   在这里插入图片描述

旋转

在实现某些操作时可能出现红色右链接或是两条连续的红链接，这是不符合红黑树定义的，我们需要对其进行旋转操作，以改变红链接的方向。

左旋转

[图片上传失败...(image-d6e87e-1599500385478)]

右旋转

[图片上传失败...(image-414751-1599500385478)]

向2-节点插入新键

1. 如果新键小于老键，新增一个红色节点，添加后新的红黑树和单个3-节点完全等价

2. 如果新键大于老键，那么新增的红色节点会产生一条红色右链接，需要将其左旋转来修正红色右链接，修正根节点的连接
   [图片上传失败...(image-da5764-1599500385478)]

   
   在这里插入图片描述

向一个3-节点插入新键:

1. 新键小于树中的两个键
2. 新键大小在两者之间
3. 新键大于树中的两个节点

这三种情况都会产生两条红链接同时链接一个节点的情况，我们应该旋转以修正它:
1、新键大于原树中的两个键，新键被链接到3-节点的右节点，此时树是平衡的，根节点为中间大小的键，它有两条红链分别和较小、较大的节点相链。将两条红链的颜色变黑，就得到了一颗由三个节点组成，高为2的平衡树。且能对应一颗2-3树。
即：新节点的链接是3-节点的右链接,转换颜色即可

2、新键小于原树中的两个键，新键被链接到最左边的空链，这时产生了两条连续的左红链，将上层的红链接右旋转使树转换为第(1)种情况
即：新节点的链接是3-节点的左链接，右旋转上层链接再转换颜色

3、新键介于原树中的两个键之间，也会产生两条连续的红链接，一条左红链接一条右红链接，将下层的红链接左旋转使树转换为第(2)种情况
即：新节点的连接时3-节点的中链接，左旋转下层链接，接着右旋转上层，再转 换颜色

在这里插入图片描述
在这里插入图片描述

颜色转换

当原树中根节点各链接出去一个红色链接时，我们应该转换链接的颜色。将链接出去的左右红链接变黑，再将链接到根的链接变红。即将子节点颜色由红变黑，将父节点的颜色由黑变红。

在这里插入图片描述

参考：
查找算法——2-3查找树、左倾红黑树
2-3查找树的插入与删除
红黑二叉查找树

公众号：算法手记