Question

平衡二叉树是二叉排序树吗?

Answer 1

是的。

衡二叉树（balanced binary tree）是一种特殊的二叉排序树，它或者为空树，或者每个结点的左右子树都是平衡二叉树，也就是每个结点的左右子树的高度之差只能是－1,0,1三种情况。

平衡二叉树又称AVL树，是由苏联的Georgy Adelson-Velsky和E.M.Landis发明的，并以他们的名字命名。

平衡二叉树的平衡状况由平衡因子（Balance Factor,BF)来衡量。平衡因子定义为当前结点的左子树高度减去右子树的高度之差，其可能取值只有－1,0,1。叶结点的BF都是0。

平衡二叉树的应用价值：

如果能维持平衡二叉树的结构，检索操作就能在O(log n)时间内完成，实现高效检索。

最小不平衡子树：

距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树。（指BF超出合法值）。

最小非平衡子树：

包含插入结点位置，其根结点的BF是1或－1的最小子树。（指BF非0，但BF在合法值范围内）。

以上内容参考：百度百科-平衡二叉查找树