algorithm - AVL 树 - LST 和 RST 之间的最大节点数

Question

我有一个 AVL 树，里面有 n 个节点，左子根树和右子根树的节点的最大差异是多少？

所以我不太确定，但首先让我们用节点填充所有右子树，所以我们填充了 n/2 + 1 个节点，剩下 n - n/2 + 1 个节点已满在左子树中，我现在想在那里插入最小节点，这样高度就不会高于 1。所以我相信我需要添加大约 logn - 1 个节点，就像一条链(总是在右子节点或总是给左边的 child )。

第二个想法，也许建立两个节点链，一个在右子树中，一个在左子树中，这样子树之间的高度不会超过 1。但这不会是我猜的最大差异

有什么想法吗？

Answer 1

根据定义，左右子树最多相差 1。假设较大的高度为 h + 1，而较小的高度仅为 h。

对于较大的，一棵高度h + 1的树中最多的节点是~ 2^h(这种情况一棵完整的树)。

对于较小的，节点数is known to be 1/√5 ((1 + √5)/2)^{h + 3} - 1。

所以，答案是2^h - 1/√5 ((1 + √5)/2)^{h + 3} + 1，服从 2^h + 1/√5 ((1 + √5)/2)^{h + 3} - 1 = n。

对于大的h和n，2^h + 1/√5 ((1 + √5)/2) ^{h + 3} - 1 ~ 2^h，所以 2^h ~ n。

令人惊讶的是(至少对我而言)，差异是Ω(n)。