平衡二叉搜索树 & AVL 树 学习笔记
2018-03-08 本文已影响29人
专职跑龙套
平衡二叉树
平衡二叉树（Balanced Binary Tree），其每个结点的左子树和右子树的高度最多差 1，严格定义是：
- 一棵空树是平衡二叉树
- 若 T 是一棵非空二叉树，其左、右子树为 TL 和 TR ，令 hl 和 hr 分别为左、右子树的深度。当且仅当
- TL 、 TR 都是平衡二叉树
- |hl － hr| ≤ 1
当然，二叉排序树（Binary Search Tree）有的性质它都有：
- 二叉排序树中任一结点：
- 其左子树中任一结点的关键字必小于该结点的关键字
- 其右子树中任一结点的关键字必大于该结点的关键字
- 二叉排序树中，各结点关键字是惟一的
- 按中序遍历该树所得到的中序序列是一个递增有序序列
例如：
AVL树
非AVL二叉树
平衡二叉树优缺点
平衡二叉树的优点：
- 不会出现普通二叉查找树的最差情况。其查找的时间复杂度为O(logN)。
平衡二叉树的缺点：
- 为了保证高度平衡，动态插入和删除的代价也随之增加。红黑树这种更加高效的查找结构可以解决这个问题。
- 在大数据量查找环境下（比如说系统磁盘里的文件目录，数据库中的记录查询 等），所有的二叉查找树结构（BST、AVL、RBT）都不合适。如此大规模的数据量，全部组织成平衡二叉树放在内存中是不可能做到的。
那么把这棵树放在磁盘中吧。问题就来了：假如构造的平衡二叉树深度有1W层。那么从根节点出发到叶子节点很可能就需要1W次的硬盘IO读写。
所有二叉查找树结构的查找代价都与树高是紧密相关的，能否通过减少树高来进一步降低查找代价呢。我们可以通过多路查找树的结构来做到这一点。 参见 多路搜索树 & B 树 & B+树 学习笔记
AVL 树
AVL 树是最早的平衡二叉树实现之一。
平衡二叉树或者说 AVL 树的查找基本与二叉查找树相同。
在每一次插入数值之后，树的平衡性都可能被破坏，这时可以通过一个简单的操作来矫正平衡–旋转。
旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。
插入节点时分四种情况，四种情况对应的旋转方法是不同的：
- LL（在a的左子树根节点的左子树上插入节点而破坏平衡）：右旋转
- RR（在a的右子树根节点的右子树上插入节点而破坏平衡）：左旋转
- LR（在a的左子树根节点的右子树上插入节点而破坏平衡）：先左旋后右旋
- RL（在a的右子树根节点的左子树上插入节点而破坏平衡）：先右旋后左旋
LL 右旋转
LL（在a的左子树根节点的左子树上插入节点而破坏平衡）：右旋转
如下图所示：
由于插入的新的节点 3，所以导致树的平衡性被破坏。因此需要对 7->5->3 这个子树进行右旋转。
LL 右旋转
那如果节点 5 本来就有了右子树呢？照样右旋转，只要把原来 5 的右子树 6 变成旋转后的 7 的左子树就行了。因为 5 的右子树 6 肯定比 5 大，但是也肯定比 7 小的：
image
RR 左旋转
RR（在a的右子树根节点的右子树上插入节点而破坏平衡）：左旋转
如下图所示：
由于插入的新的节点 15，所以导致树的平衡性被破坏。因此需要对 10->13->15 这个子树进行左旋转。
RR 左旋转
LR 先左旋再右旋
LR（在a的左子树根节点的右子树上插入节点而破坏平衡）：先左旋后右旋
如下图所示：
由于插入的新的节点 6，所以导致树的平衡性被破坏。因此需要对 7->5->6 这个子树进行先左旋后右旋。
LR 先左旋再右旋
RL 先右旋再左旋
RL（在a的右子树根节点的左子树上插入节点而破坏平衡）：先右旋后左旋
如下图所示：
由于插入的新的节点 11，所以导致树的平衡性被破坏。因此需要对 10->13->11 这个子树进行先右旋再左旋。
RL 先右旋再左旋
