蓝桥备赛（18）- 红黑树和 set 与 map（上）

对于二叉搜索树 ， 平衡二叉树 ， 以及红黑树 ， 目前只需要了解背后的原理 ， 不做代码实现的要求 ， 重要的就是了解各种操作的时间复杂度即可 ， 为set 与 map 做铺垫

 

一、二叉搜索树

1.1 基本概念

相较与于堆，二叉搜索树是大小关系更为严格的数据结构。但是并不需要必须是⼀棵完全二叉树，也就是树的形态是任意的。如下图所示，都是二叉搜索树！

构造一棵二叉搜索树的目的  ， 并不是为了排序，而是为了提高查找和输入删除关键字的速度。

1.2 查找操作

二叉搜索树的查找是从根结点开始 ，沿某个分支逐层向下比较的过程，若二叉搜索树非空，先将给定值与根结点的关键字比较，若相等，则查找成功；若不等，如果小于根结点的关键字，则在根结点的左子树上查找，否则在根结点的右子树上查找。二这也是⼀个递归的过程。

根据BST的特性（左 < 根 < 右 )

从根结点开始一路向下找

最坏情况下会从根节点开始，查找到叶子结点。因此时间复杂度是和树的高度有关的，而树高最差会 变成一条单链表，因此时间复杂度为 O(N)

1.3 插入操作

根据BST的特性（左 < 根 < 右 )

从根结点开始一路向下找，找到合适的位置，就直接插入

插入与查找的过程一致，因此时间复杂度为 O(N) 

1.4 构造 BST 树

二叉搜索树的构建就是不断向原来的树中插入新的结点即可。

根据序列 a = {51, 68, 59, 27, 25, 33, 75, 70} ，构造⼀棵二叉排序树

所以时间复杂度最优的情况下是 ： O(logN)

根据序列 a = {25, 27, 33, 59, 75, 51, 70, 68} ，构造⼀棵二叉排序树

在极端条件下 ， 时间复杂度为 O(N)  ---> oh my god ! 骤增了！！！  

在上面两个构造二叉排序树的过程中 ， 虽然结点的值都相同 ， 不同的构造顺序会有不同的二叉搜索树 ， 会影响查找和插入的效率 。 并且 ， 构造序列越有序 ， 二叉搜索树的查找效率就越低 。

1.5 删除操作

对于第三个删除结点的情况 ， 我们一般是把它变成情况一或二

1）若被删除结点是叶子结点，则直接删除   

----> 此时依旧会保持二叉搜索树的性质

2）若被删除结点只有左子树或者右子树，让左子树或者右子树替代

  ----> 此时依旧会保持二叉搜索树的性质

3）若被删除结点有左子树和右子树

删除 50 这个结点，并用直接前驱来替代

删除 50 这个结点，并用直接后继来替代

删除10这个结点：

注意：我们创建二叉搜索树其实并不是为了排序 ， 而是为了快速插入、删除 以及查找元素。因为BST不是那么极端的话 ， 树高维持在  logN 的范围 ， 上述的各种操作其实是很快的 。 但是二叉搜索树的特性并不杜绝极端情况的出现 ！！！

二、平衡二叉树

在介绍二叉搜索树的时候 ， 在某些特定的情况下 ， 二叉搜索树是会退化成单链表 ， 并且各种操作的效率也会明显下降 。因此我们需要一些特别的手段保证这个二叉搜素树的“平衡”，进而保证各种操作的效率 。

2.1 基本概念

平衡二叉树 ， 也称AVL树 ， 它是具有以下性质的二叉搜索树：

1 ） 左右子树的高度差的绝对值不超过1

2 ） 左右子树分别也是平衡二叉树

如下图所示 ， 结点上方的数字表示平衡因子 。 左图是一棵平衡二叉树，右图不是！

2.2 查找操作

平衡二叉树的查找 、 插入 以及 删除操 作基本上与二叉搜索树一致 ， 但是需要处理操作之后的“失衡” 。

重点需要掌握两种处理失衡的操作：

1） 左旋

2） 右旋

由于平衡二叉树会限制树的高度不会过高  ，趋近于 log n 级别 ， 因此时间复杂度为 O(logN）

左旋（结点1）的时候遇到（结点2） “挡着了” ， 

1 ） 结点1 成为右孩子的左子树

2 ） 右孩子原本的左子树（结点2）成为该结点（结点1）的右子树

右旋（结点1）的时候遇到（结点2） “挡着了” ， 

1 ） 结点1 成为左孩子的右子树

2 ） 左孩子原本的右子树（结点2）成为该结点（结点1）的左子树

2.3 插入操作

最小不平衡子树：

在⼆叉搜索树中插入新结点之后，插入路径的点中，可能存在很多平衡因子的绝对值大于 1 的，此时找到 距离插入结点最近的不平衡的点 ，以这个点为根的 子树 就是 最小不平衡子树 。

2.3.1 LL型 - 右单旋

LL 表示： 新结点由于插入在 T 结点的左孩子(L)的左子树(LL)中 ，从而导致失衡。如下图所示：

T失衡了： ---> 让失衡点右旋

案例： 

2.3.2 RR型 - 左单旋

RR 表示：新结点由于插入在 T 结点的右孩子(R)的右子树(RR)中，从而导致失衡。如下图所示：

 T失衡了---> 让失衡点左旋 

案例：

2.3.3 LR型 - 左右双旋

LR 表示：新结点由于插入在 T 结点的左孩子(L)的右子树(LR)中，从而导致失衡。如下图所示：

 T失衡了： -->

1） 失衡点左孩子左旋

2） 失衡点右旋 

案例： 

2.3.4 RL型 - 右左双旋

RL 表示：新结点由于插入在 T 结点的右孩子(R)的左子树(RL)中，从而导致失衡。如下图所示：

 T失衡了： -->

1） 失衡点的右孩子右旋

2） 失衡点左旋 

案例： 

2.4 构造ALV树

平衡二叉树的构造 ， 就是不断向数中插入新的结点：

根据序列 a = {15, 6, 10, 17, 11, 13, 9, 20, 16, 22} ，构造一棵二叉排序树

2.5 删除操作

与插入操作的思想类似，都是先按照二叉搜索树的形式操作，然后想办法使其平衡。具体步骤：

删除结点的时候 ， 调整可能不止一次 ， 因为插入的时候，我们是从根结点开始查找合适的插入位置 ， 是符合BST的特性 ， 但是删除操作的时候 ， 是随机的 。

 例一：删除 30

叶子结点直接删除，删除之后向上到根节点，所有结点都没有失衡，直接结束。

  例二：删除 10 

第⼀次调整：从 10 向上找，第⼀个不平衡子树是以 49 为根的子树，高度最高的儿子是 59，高度最高的孙子是 69，呈现右孩子右孩子，因此仅需对 59 左旋⼀次。

没有第二次调整了，因为所有都已经平衡了 

  例三：删除 57 

第⼀次调整：从 57 向上找，第⼀次出现的不平衡子树是以 49 为根的子树，高度最高的儿子是

45，高度最高的孙子是 47，呈现左孩子右孩子，因此需要让 47 左旋⼀次，然后再右旋⼀次：

 

 

第二次调整：从 47 向上找，发现 59 失衡，找到最高的孩子为 69 号结点，最高的孙子为 76 号结

点，呈现的关系是右孩子右孩子，因此将 69 左旋⼀次：

 

调整结束，因为已经到了根结点，并且根节点是平衡的。