平衡二叉树

二分搜索树的问题

二分搜索树有一个非常严重的问题，如果数据是按顺序去添加，那么二叉树就会退化成一个链表从而大大降低搜索的效率。例如以 1，2，3，4，5，6 为例，它形成的搜索树如下：

为了解决这个问题，需要在原有的二分搜索树基础上添加一定的机制，使得二分搜索树可以维持为平衡二叉树。AVL 就是最为经典的平衡二叉树。

平衡二叉树的概念

平衡树是计算机科学中的一类数据结构，为改进的二叉查找树。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡树。

• 一个满二叉树是个平衡的二叉树，计算二叉搜索树的平均时间复杂度就是通过满二叉树来进行推导的。在满二叉树的情况下，可以让树的高度达到最低的状态。
• 对于完全二叉树来说，整棵树的叶子节点最大深度值和最小深度值差不会超过1。
• 线段树也是一个平衡二叉树，所有的叶子节点最大深度和最小深度差不会超过1。

参考资料

• 平衡树