英文:
Number of balance operations in an AVL Tree when a sequence of decreasing numbers is inserted
问题
The translation of your content is as follows:
当将 n 个数字（从 n 递减到 1）插入空的 AVL 树时，会有多少次平衡操作？
示例：
AVL 树 旋转次数
--------------- -------------------
8 0
8
┌─┘ 0
7
8 7
┌─┘ ┌─┴─┐ 1
7 → 6 8
┌─┘
6
...等等
我知道答案是 ~(n-logn)，但如何通过归纳证明这一点呢？
英文:
How many balance operations will there be when inserting n numbers (decreasing from n down to 1) into an empty AVL tree?
Example:
AVL tree number of rotations
--------------- -------------------
8 0
8
┌─┘ 0
7
8 7
┌─┘ ┌─┴─┐ 1
7 → 6 8
┌─┘
6
...etc
I know the answer is ~(n-logn), but how to prove this with induction?
答案1
得分: 1
以下是翻译好的部分：
这里有一些不变性（待证明），当我们有一个由添加递减值序列构建的AVL树，节点数为𝑛（𝑛 > 0）时：
-
所有 右子树（任何父节点的）都是完美的。这意味着树中的所有节点的平衡因子都是0，除了从根到最左边叶子的路径上可能有一个或多个节点：它们的平衡因子可能是0或−1（当−1时，表示它们的左子树比右子树高一单位）。
-
树的高度为𝐻<sub>𝑛</sub> = ⌊log<sub><sub>2</sub></sub>𝑛⌋。因此，如果𝑛是2的幂次减1，那么树是完美的树，因此所有平衡因子都为零。
-
旋转的次数为𝑅<sub>𝑛</sub> = 𝑛−1−𝐻<sub>𝑛</sub>
数学归纳法证明
基本情况
当𝑛为1时，这些不变性成立：该树是完美的，𝐻<sub>𝑛</sub>= 0，旋转的次数为𝑛−1−𝐻<sub>𝑛</sub> = 0。
归纳步骤
我们现在假设一个具有𝑛−1个节点的树遵守这些不变性，然后将第𝑛<sup>th</sup>个（具有较小值的）节点添加到该树中。我们可以区分两种情况：
-
𝑛是2的幂次：
插入之前树是完美的（不变性2），因此所有平衡因子都为零：添加操作将使新节点的所有祖先的平衡因子变为−1，并且会增加树的高度𝐻<sub>𝑛</sub> = 𝐻<sub>𝑛−1</sub> + 1。不会发生旋转。我们知道旋转的次数是𝑅<sub>𝑛−1</sub> = 𝑛−2−𝐻<sub>𝑛−1</sub>，因此可以得出𝑅<sub>𝑛</sub> = 𝑛−1−𝐻<sub>𝑛</sub>。不变性成立。
-
𝑛不是2的幂次：
插入之前树不是完美的，到最左边叶子的路径上至少有一个节点的平衡因子为−1。AVL插入算法插入节点后，树的高度会暂时增加，然后算法会沿着路径向上回溯，降低它遇到的节点的平衡因子。它们全部变为−1，直到遇到一个已经平衡因子为−1且现在变为−2的节点𝑋。让我们称𝑋的左子节点为𝑌，它的平衡因子已经从0更新为−1。现在，𝑋需要执行一个简单的向右旋转，其中𝑌取代了它在树中的位置，而𝑋成为了它的右子节点。这个旋转将树的高度再次降低到之前的高度，并且给予𝑌一个平衡因子为0。我们知道𝑋有一个完美的右子树（不变性1），旋转将给𝑋的左子节点（如果有的话）也变得完美（因为该子节点以前是𝑌的右子节点 - 不变性1）。𝑋的平衡因子将变为0，因此它现在根据底层子树根节点来根据树的底层来衡量是否完美，从而保持不变性1：
（N是插入的节点）
AVL插入算法在这里停止，因为没有更多的平衡因子需要更新，也不需要执行旋转。由于高度保持不变，不变性2成立，并且显然𝑛增加了1，这个增加覆盖了新的旋转，因此我们保持了第三个不变性：𝑅<sub>𝑛</sub> = 𝑛−1−𝐻<sub>𝑛</sub>。所有不变性都成立。
总之： 我们通过数学归纳法证明了这些不变性。第三个不变性是我们感兴趣的：
𝑅<sub>𝑛</sub> = 𝑛−1−⌊log<sub><sub>2</sub></sub>𝑛⌋。
英文:
Here are some invariants (to be proved) when we have an AVL tree with 𝑛 nodes (𝑛 > 0) that was constructed by adding a sequence of decreasing values:
-
All right subtrees (of any parent node) are perfect. This means all nodes in the tree have a balance factor that is 0, except maybe one or more nodes that are on the path from the root to the leftmost leaf: they may have a balance factor of 0 or −1 (When −1, this indicates their left subtree is one unit higher than their right subtree).
-
The height of the tree is 𝐻<sub>𝑛</sub> = ⌊log<sub><sub>2</sub></sub>𝑛⌋. By consequence, if 𝑛 is one less than a power of 2, the tree is a perfect tree and thus all balance factors are zero.
-
The number of rotations is 𝑅<sub>𝑛</sub> = 𝑛−1−𝐻<sub>𝑛</sub>
Proof by induction
Base case
These invariants are true when 𝑛 is 1: that tree is perfect, 𝐻<sub>𝑛</sub>= 0, and the number of rotations is 𝑛−1−𝐻<sub>𝑛</sub> = 0.
Induction step
We now assume a tree with 𝑛−1 nodes that obeys the invariants, and we then add the 𝑛<sup>th</sup> node (with smaller value) to that tree. We can distinguish between two cases:
-
𝑛 is a power of 2:
The tree was perfect before insertion (invariant 2) and thus all balance factors were zero: the addition will give all the ancestors of the new node a balance factor of −1, and will increase the height 𝐻<sub>𝑛</sub> = 𝐻<sub>𝑛−1</sub> + 1. No rotations will occur. We know that the number of rotations was 𝑅<sub>𝑛−1</sub> = 𝑛−2−𝐻<sub>𝑛−1</sub> and so it follows that 𝑅<sub>𝑛</sub> = 𝑛−1−𝐻<sub>𝑛</sub>. The invariants hold.
-
𝑛 is not a power of 2:
The tree was not perfect and at least one node on the path to the leftmost leaf had a balance factor of −1. After the AVL insertion algorithm has inserted the node, the tree's height temporarily increases, and the algorithm will backtrack upwards the path to decrease the balance factors of the nodes it meets. They all become −1 until a node 𝑋 is encountered that already had a balance factor of −1 and now has it changed to −2. Let's call 𝑋's left child 𝑌, which already had its balance factor updated from 0 to −1. Now 𝑋 needs a simple rotation to the right, whereby 𝑌 takes its place in the tree, and 𝑋 becomes its right child. This rotation will decrease the tree's height again to what it was before and give 𝑌 a balance factor of 0. We know that 𝑋 has a perfect right subtree (invariant 1), and the rotation will give 𝑋 a left child (if any) that is also perfect (as the child used to be a right child of 𝑌 − invariant 1). The balance factor of 𝑋 will become 0, and so it now roots a perfect subtree whose bottom level is the bottom level of the whole tree, so that invariant 1 remains true:
(N is the inserted node)
The AVL insertion algorithm stops there as there are no more balance factors to update, nor rotations to be performed. As the height remained the same, invariant 2 holds, and as 𝑛 obviously increased with 1, that increase covers for the new rotation and we maintain the third invariant: 𝑅<sub>𝑛</sub> = 𝑛−1−𝐻<sub>𝑛</sub>. All the invariants hold.
In conclusion: we have a proof by induction of the invariants. The third invariant is the one of interest:
𝑅<sub>𝑛</sub> = 𝑛−1−⌊log<sub><sub>2</sub></sub>𝑛⌋.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论