Python - 深夜数据结构与算法之 AVL 树 红黑树
目录
一.引言
二.高级树的简介
1.树
2.二叉树
3.二叉搜索树
4.平衡二叉树
三.AVL 树
◆ 插入节点
◆ 左旋
◆ 右旋
◆ 左右旋
◆ 右左旋
◆ 一般形式
◆ 实际操作
◆ 总结
四.红黑树
◆ 概念
◆ 示例
◆ 对比
五.总结
一.引言
前面我们介绍了二叉树、二叉搜索树、多叉树等基础的树形结构，本文扩展一些新的树类型，例如 AVL 树、红黑树、B 树等等，完善一下整个框架内树的的概念。
二.高级树的简介
1.树
树，这里就不多重复了，包括根节点、左右子节点，分为多个层级的扩散的结构，因为其树形的结构天然的适合使用递归的方法进行遍历与处理。
2.二叉树
只有左右分叉的树即为二叉树， 二叉树主要掌握其三种遍历方式。
- 前序 Pre-order 根-左-右
- 中序 In-Order 左-根-右
- 后序 Post-Order 左-右-根
3.二叉搜索树
通过对数据进行有序编排，二叉搜索树将 o(n) 的搜索复杂度缩减为 o(log2n)，其特点:
左子树所有节点小于根节点
右子树所有节点大于根节点
需要注意，二叉搜索树的中序遍历是升序排列。
◆ 节点查找
只需要与根节点比较即可，小于根节点到左子树，大于2根节点到右子树。 可以看到其查询的时间复杂度就是树的深度即 Level。
◆ 极端情况
当我们构建二叉搜索树时不注意树的结构或者平衡时，其容易出现如上图所示的极端情况，此时二叉树退化为链表，其搜索复杂度也恢复至 o(n)。
4.平衡二叉树
上面这种情况，最简单的平衡方法就是从中间把棍子打断，然后对于左右的棍子依次打断，直到平衡，但是实际情况下我们不会等树发展到这种棍子的状态才进行调整，我们一般在每一步插入元素的时候都会查看当前树是否平衡，并对其进行平衡化的操作。下面我们就了解几种常见的平衡二叉树。
三.AVL 树
AVL 树命名来源于其发明者，其在树中引入了平衡因子即 Balance Factor，该因子的计算为 左子树高度 - 右子树高度 或者 右子树高度 - 左子树高度，因此其值的范围控制在 -1、0、1。这里是高度而不是节点数的原因是二叉树的搜索时间复杂度与其深度即 Level 有关，而不是节点个数 (考虑棍子的极端情况)。当检测到数非平衡时，其会通过四种旋转操作使树达到平衡。
以上面的二叉树为例，每一个节点的平衡因子都基于其左右子树的深度差计算，以 J 为例，右子树深度即 Level 为 4，而左子树的深度为 3，从而其值 = 4 - 3 = 1。 而所有叶子节点左右子树都为 0，所以其值为 0。上面这个树的平衡因子范围在 [-1, 1]，因而其是一颗严格意义上平衡的AVL 树，因此保持一个树的平衡因子在 [-1,1] 范围内，其就是一颗平衡二叉搜索树。
◆ 插入节点
14 增加后平衡因子在 [-1,1] 范围内，因此无需调整。
3 增加后根节点与第一个左节点的平衡因子变为 -2，此时平衡树被打破，需要使用旋转操作进行 reblance，共有四种旋转方式:
◆ 左旋
右右子树的情况，需要进行一次左旋调整为 AVL树。 A < B < C，所以 A B C 有效。
◆ 右旋
左左子树的情况下，依次右旋调整为 AVL 树。 A > B > C，所以 C B A 有效。
◆ 左右旋
左右子树即先一个单独左，再一个单独右，此时满足 A > B && C > B && A > C，结合在一起就是 A > C > B，所以可以先左旋 BC 并调换位置调整为 A > C > B 的左左子树，再右旋得到 B C A。
◆ 右左旋
B > A，B > C，C > A => B > C > A，所以可以切换为右右子树 A C B，再一次左旋即可。
◆ 一般形式
上面介绍了单节点的四种旋转方式，实际场景带子树的情况比较多，上面是几种通用的旋转方法。 我们再从头捋一遍 AVL 树，首先树的查询是基于其深度 Level 来的，所以通过引入平衡因子就能够获得高度差从而衡量一个树是否平衡，当超过1不平衡时，我们可以通过旋转进行 rebalance，此时从单节点推广至多节点，AVL 树的情况大致就这样。
◆ 实际操作
下面基于真实的二叉搜索树进行旋转操作。
- 左左子树
红框所在部分为左左子树，根据一般形式，我们需要把 Pivot = 5 提上去，再把 10 放下来，同时 Pivot 的 Right 挂到 root = 10 的 Left，就得到下面的结果，没理解的同学看一般形式再对应一下:
- 右左子树
红框部分为右左子树，参考上面一般方法， 进行右左旋，先将 15 换到 16，再把 16 改为 15.right，最后把 15 拿上去，9 改为 15.left 即可。
◆ 总结
AVL 树在满足平衡二叉搜索的情况下，每个 Node 都多余存储了一个平衡节点，因此其会有额外的存储负担，其次对于节点的增删，很容易使其成为非平衡的状态，从而频繁引发调整。
四.红黑树
◆ 概念
上面的 AVL 树通过平衡因子维持整个搜索树的平衡，但是由于其因子范围太小 [-1,1] 导致这里调整的频率太高，从而影响了查询的效率，所以为了折中就推出了一些近似平衡二叉树，红黑树就是其中的代表。其允许左右子树之间的高度差在两倍以内，放宽了范围从而较少了调整的次数。
◆ 示例
上面提到五条性质，前三条比较 common，主要看后两条:
- 不能有相临接的两个红色节点
- 任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
Most Important:
从根到叶子的最长的可能路径不多于最短路径的两倍长。
◆ 对比
- AVL 树相比红黑树提供更快的查询效率，因为其更严格的平衡
- 红黑树提供了更快的插入和移除效率，因为 AVL 涉及到过多的旋转调整
- AVL 存储更多，因为其需要 int 存储节点平衡度，而红黑树只需要 bit 存储红或蓝即 0 或 1
- 读多写少适合使用 AVL 树，而工程中二者兼顾，所以红黑树的使用更加普遍例如 map/multimap
五.总结
截止到目前，一些基础的搜索结构与算法我们也了解差不多了，从最基本的树形结构，到并查集、Trie 树、二叉树、完全二叉树、平衡树等等。由于 AVL 树和红黑树的实现相对复杂，所以我们主要掌握其思想以及对应的几种旋转操作即可，做到能够看懂说清。