什么叫做平衡二叉树
平衡树指的是,任意节点的子树的高度差都小于等于1。常见的符合平衡树的有,B树(多路平衡搜索树)、AVL树(二叉平衡搜索树)等。平衡树可以完成集合的一系列操作, 时间复杂度和空间复杂度相对于“2-3树”要低,在完成集合的一系列操作中始终保持平衡,为大型数据库的组织、索引提供了一条新的途径。
平衡二叉查找树简称平衡二叉树。由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树,根据科学家的英文名也称为 AVL 树。它具有如下几个性质
1、可以是空树。
2、假如不是空树,任何一个结点的左子树与右子树都是平衡二叉树,并且高度之差的绝对值不超过 1。
平衡之意,如天平,即两边的分量大约相同。