在之前的文章中，我们初步了解了二叉查找树（又称二叉排序树），这使我们意识到使用特定策略的查询可以显著提高查找效率。本文将进一步探讨二叉树的演进。由于树相关算法较多且相对复杂，因为我后续将拆解讲述，细嚼慢咽。
二叉排序树
二叉排序树的特点如下：
1）在树中的任意节点，其左子树中的每个节点的值都小于该节点的值，而右子树的值都大于该节点的值。
2）二叉查找树的查找、插入和删除操作的平均时间复杂度都是O(log n)，其中n为树中的节点数，因此它是一种非常高效的查找数据结构。
3）由于其特殊的结构，二叉排序树能够支持快速的查找、插入和删除操作。
线性查找和二叉查找树的效率对比：Binary and Linear Search Visualization
缺点：
在数据分布不佳的情况下，二叉查找树可能会出现左右子树极度不平衡的情况，导致树的退化成为链表，这时查找操作的时间复杂度就会变为O(n)，相当于执行了全表扫描。而在最理想的情况下，当二叉查找树是一棵完全二叉树或者满二叉树时，查找、插入和删除操作的时间复杂度与树的高度成正比，即O(高度)。完全二叉树的高度小于等于log2n（其中n为节点个数），因此在最理想情况下，二叉查找树的时间复杂度为O(logn)。
二叉查找树左右子树极度不平衡，退化成为链表时候，相当于全表扫描，时间复杂度就变为了O(n)，插入速度没影响，但是查询速度变慢，比单链表都慢，每次都要判断左右子树是否为空，需要保证二叉查找树一直保持平衡，就需要用到平衡二叉树。
平衡二叉树
AVL树，全称Adelson-Velskii和Landis树，是一种被称为平衡二叉查找树的特殊数据结构。在AVL树中，每个节点的左右子树高度差不超过1，这种平衡性保证了树的结构是稳定的。当插入或删除数据导致AVL树失去平衡时，会通过调整节点来重新平衡树结构。
由于平衡二叉树的插入和删除操作时间复杂度均为O(logn)，因此它具有高效的查找性能，远远快于非平衡的二叉查找树。
其实现平衡二叉树的方式，有红黑树、Treap和伸展树等。
核心思想
在插入或删除节点时，如果发现子树不平衡，则对子树进行旋转操作，使其重新达到平衡。
旋转操作有三种，根据哪边的高度较低就进行相应的旋转，以提升树的高度：
- 左旋LL旋转
- 右旋RR旋转
- 左右LR双旋和右左RL双旋
动画效果演示：AVL Tree Visualzation
以上图为例，通过平衡二叉树实现时，其分布如下：
二叉搜索树的时间复杂度介于O(log2N)到O(n)之间，如果退化成单链表，时间复杂度就是顺序查找，为O(n)，以上情况如果是平衡二叉树，查找效率会提高到O(log2N)。
缺点：
1）平衡二叉树的高度等于每次查询数据时磁盘IO操作的次数。假设磁盘每次寻道时间为10毫秒，在处理大量数据时，查询性能会变差。
对于100万条数据，log2(N)约为20次磁盘IO操作，总时间为20*10=0.2秒。这里，log2(N)表示需要将2提升多少次方才能得到N。例如，log2(8)等于3，所以2的20次方等于1048576，因此需要进行20次磁盘IO操作。
2）平衡二叉树不支持高效的范围查询。在进行范围查询时，需要多次从根节点遍历，导致查询效率较低。
