满二叉树为什么不是平衡树

Question

如题所述

Answer 1

满二叉树不是平衡树的原因：
（1）满二叉树：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
（2）平衡树，即平衡二叉树，又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡树，左子节点与右子节点对称。

Answer 2

平衡树的定义分为两部分，它首先是①一种排序树，其次②它的每一个节点的左右子树高度差至多等于1。
我觉得这个问题的重点在于平衡树的前提是一颗排序树！要考虑节点的值。
举个例子，一棵满二叉树，虽然结构上与平衡树的结构要求“每一个节点的左右子树高度差至多等于1”相符合。但假设这棵满二叉树上的左子树上的值不全都比根结构的值大，那它就不满足“是一棵排序数”的要求了。
综上，我认为满二叉树不一定是一颗平衡树。

Answer 3

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