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

Question

如题所述

Answer 1

平衡二叉树不一定是二叉排序树，平衡二叉树是为了避免二叉排序树高度增长过快，降低二叉排序树性能而设的树，二叉排序树当然不可能都是平衡二叉树。

首先平衡二叉树是特殊的二叉排序树，他的结点元素间存在着偏序关系；其次相对于一般的二叉排序树，平衡二叉树的左右子树的深度差也有不超过1层的约束，这样使得平衡树是同种元素序列情况下的深度最小的二叉排序树，这可以减少二叉树元素查找的深度，从而提升平均查找效率。

应用

平衡树可以完成集合的一系列操作， 时间复杂度和空间复杂度相对于“2-3树”要低，在完成集合的一系列操作中始终保持平衡，为大型数据库的组织、索引提供了一条新的途径。

二叉排序树或者是一颗空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根节点的值。

（2）若右子树不空，则右子树所有结点的值均大于或等于它的根结点的值。

（3）左、右子树也分别为二叉排序树。