data-structures - 带有排序列表的 AVL 树？

Question

在阅读了有关 AVL 树的信息后，我无法摆脱一个问题。如果我们有一个排序的数字列表，例如 [1,2,3,4,5] 并且我们将它们插入 AVL 树中，树不会保持原样，因为它会变成 1-2-3-4-5 （即他们都将成为正确的孩子）。

我问这个是因为我知道在 AVL 树中，对于 T 的每个内部节点 v，v 的子节点的高度最多可以相差 1。

但是如果我们每个节点只有 1 个孩子，我们怎么做这个比较呢？

Answer 1

一棵空树的高度为 0，因此在您的示例中，在添加 1-2-3 之后，1 的左子节点的高度为 0，而右子节点的高度为 2，从而触发了使 2 成为根的旋转。