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

热心网友 · 2018-4-30 02:00:09

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

NoHow绝不 · 2018-4-30 02:00:10

首先重复下平衡树的定义：
对一棵查找树（search tree）进行查询/新增/删除等动作, 所花的时间与树的高度h 成比例, 并不与树的容量 n 成比例。如果可以让树维持矮矮胖胖的好身材, 也就是让h维持在O(lg n)左右, 完成上述工作就很省时间。能够一直维持好身材, 不因新增删除而长歪的搜寻树, 叫做balanced search tree（平衡树）
满二叉树：
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点（最后一层上的无子结点的结点为叶子结点）。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上.

由此很明显的说，满二叉树不是是平衡树

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

2 个回复