绝对平衡树和满二叉树疑问

满二叉树也是相同的树状图,所以绝对平衡树是属于满二叉树的吗?

源自：AVL 树和红黑树 2-1 红黑树与2-3树

收起

1回答

liuyubobobo 回答被采纳获得+3积分 2021-05-15 09:22:22

是的。

这里我说“绝对平衡”，这个“绝对平衡”是我发明的一个词，和“平衡二叉树”中的“平衡”对应。在“平衡二叉树”中，平衡的定义是左右子树的高度差不超过1，则最大为 1。我这里说的“绝对平衡”，就是左右字数的高度差为 0，即高度相同。

一棵树的左右子树高度相等，就是一棵满二叉树：）

继续加油！：）

蓝色的sola 提问者 #1

还有一个疑问, 绝对平衡树和二叉树之间, 除了树结构不会退化以外, 还有什么优势?

2021-05-15 10:11:55
liuyubobobo 回复提问者蓝色的sola #2

这个是最重要的优势。因为 O(n) 和 O(logn) 之间差的十万八千里。其他的优势在这个优势面前不值一提。比如绝对平衡的二叉树可以很容易地使用个数组表示。但是这不是我们追求“平衡”的核心原因。

2021-05-15 18:39:12