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 树的情况大致就这样。