algorithm - AVL 树 - 为什么某些节点的左右子节点的高度必须相差 1？

Question

某个节点的左右子节点的高度相差 2 有什么问题？

这是我第一次接触 AVL 树，我似乎无法理解为什么它是必须的？

真的，孩子相差2岁有什么问题？

问候

Answer 1

这就是AVL树的概念，左右孩子的高度最多不能相差一个。

来自维基百科

在 AVL 树中，任何节点的两个子子树的高度最多相差 1。

由于它是平衡的，这使得搜索为 0(logn)，因此它比非平衡二叉树更快，其中所有元素都可能在左侧，使其为 0(n)

Answer 2

根据定义，平衡二叉树只能相差一个。如果您查看在 AVL 树上运行的算法，您会发现该属性始终保持不变。

虽然可以制作某种高度最多相差 +- 2 的数据结构，但这样做并没有真正的好处。通过将其保留为 +- 1，您可以创建一个更简单的自平衡数据结构。