東京大学 情報理工学系研究科 コンピュータ科学専攻 2017年8月実施 専門科目II 問題3

标签：

• Tokyo-University
• Minimum-Nodes-in-Height-Balanced-Binary-Tree
• Fibonacci-Recurrence
• Heap-Order-Assignment-by-Linear-Time-Construction
• Algorithm-Complexity

Author

kainoj, Zephyr, 祭音Myyura

Description

Let $L(v)$ denote the set of leaves in the descendants of node $v$ in a tree, and let $p(v, w)$ denote the number of edges of the simple path from node $v$ to node $w$. For a non-leaf node $v$, $\max_{w \in L(v)} p(v, w)$ is called the height of $v$. Let the height of a leaf be $0$. The height of the root of a tree is called the height of the tree.

Here, we have a binary tree $T_n$ with height $n \geq 0$, in which each node $v$ must have one of the following properties:

• $v$ is a leaf.
• $v$ has only one child, and the height of $v$ is $1$.
• $v$ has two children, and the heights of the two children of $v$ differ by $1$.

Let $N_n$ denote the number of nodes in $T_n$ for $n \geq 0$. Let $r = \frac{1 + \sqrt{5}}{2}$.

Answer the following questions:

(1) Calculate $N_5$.

(2) Express $N_n$ in terms of $N_{n-1}$ and $N_{n-2}$ for $n \geq 2$.

(3) Prove that $N_n \geq r^n$ for every $n \geq 0$.

(4) Prove that $N_n \leq r^{n+2}$ for every $n \geq 0$.

(5) Consider the problem of assigning each of the given $N_n$ integers to a distinct node of $T_n$. The integer assigned to each node $v$ must be no smaller than any of the integers assigned to $v$'s children. Show an $O(r^n)$ algorithm that computes such an assignment, with a proof that the algorithm runs indeed in $O(r^n)$ time. Note that the $N_n$ integers may not be sorted in the input.

题目描述

在一棵树中，记 $L(v)$ 为结点 $v$ 的后代叶结点集合，$p(v,w)$ 为从 $v$ 到 $w$ 的简单路径所含边数。非叶结点 $v$ 的高度定义为 $\max_{w\in L(v)}p(v,w)$，叶结点的高度为 $0$，树根的高度称为树的高度。

给定高度为 $n\ge0$ 的二叉树 $T_n$，其中每个结点 $v$ 必须满足以下三种情形之一：

• $v$ 是叶结点；
• $v$ 只有一个子结点，且 $v$ 的高度为 $1$；
• $v$ 有两个子结点，且两个子结点的高度相差 $1$。

令 $N_n$ 表示 $T_n$ 的结点数，并令 $r=(1+\sqrt5)/2$。回答下列问题。

（1）计算 $N_5$。

（2）对 $n\ge2$，用 $N_{n-1}$ 和 $N_{n-2}$ 表示 $N_n$。

（3）证明对每个 $n\ge0$，都有 $N_n\ge r^n$。

（4）证明对每个 $n\ge0$，都有 $N_n\le r^{n+2}$。

（5）现有 $N_n$ 个未必已排序的整数，需要将它们一一分配给 $T_n$ 的不同结点，并使每个结点上的整数都不小于其任一子结点上的整数。给出完成该分配的 $O(r^n)$ 算法，并证明其运行时间确为 $O(r^n)$。

Kai

Setting: $T_n$ stands for AVL tree of height $n$. Denote $N_n$ for number of nodes in $T_n$.

(1)

$20$

(2)

$$N_n = N_{n-1} + N_{n-2} + 1$$

Bonus: note that $N_n = \text{Fib}_{n+3} - 1$ where $\text{Fib}_0 = 0$.

Proof goes by induction:

$$N(0) = 1 = 2 - 1 = \text{Fib}_3 - 1,$$

$$N(1) = 2 = 3 - 1 = \text{Fib}_4 - 1.$$

Inductive step:

$$N_n = N_{n-1} + N_{n-2} + 1 = (\text{Fib}_{n+2} - 1) + (\text{Fib}_{n+1} - 1) + 1 = \text{Fib}_{n+3}-1$$

(3)

Note that $r^n = r^{n-1} + r^{n-2}$. To see that start with:

$$r^2 = \left(\frac{1+\sqrt{5}}{2}\right)^2 = \frac{1+\sqrt{5}}{2} + 1 = r+1$$

and multiply it by $r^{n-2}$ both sides.

The rest goes by induction.

Base case: $N_0 = 1 \geq r^0$, $N_1 = 2 > r^1$.

Inductive step:

$$N_n = N_{n-1} + N_{n-2} + 1 \geq r^{n-1} + r^{n-2} = r^n$$

(4)

Put $M_n=N_n+1$. Then $M_0=2\leq r^2$, $M_1=3\leq r^3$, and

$$M_n=M_{n-1}+M_{n-2}\leq r^{n+1}+r^n=r^{n+2}.$$

Thus $N_n<M_n\leq r^{n+2}$.

(5)

Assign the integers arbitrarily, then process the nodes in postorder. At each node, repeatedly swap its value with the larger child while that child is larger. Since both child subtrees are already heaps, this produces the required max-heap order.

A sift at the root of a height-$h$ subtree costs $O(h)$. Hence the total cost satisfies

$$C_n=C_{n-1}+C_{n-2}+O(n).$$

Unrolling this recurrence gives

$$C_n=O\left(\sum_{j=0}^n (j+1)r^{n-j}\right) =O(r^n),$$

because $\sum_{j\geq0}(j+1)/r^j$ converges.