跳到主要内容

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

Author​

kainoj, Zephyr

Description​

Let denote the set of leaves in the descendants of node in a tree, and let denote the number of edges of the simple path from node to node . For a non-leaf node , is called the height of . Let the height of a leaf be . The height of the root of a tree is called the height of the tree.

Here, we have a binary tree with height , in which each node must have one of the following properties:

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

Let denote the number of nodes in for . Let .

Answer the following questions:

(1) Calculate .

(2) Express in terms of and for .

(3) Prove that for every .

(4) Prove that for every .

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

Kai​

Setting: stands for AVL tree of height . Denote for number of nodes in .

(1)​

(2)​

Bonus: note that where .

Proof goes by induction:

Inductive step:

(3)​

Note that . To see that start with:

and multiply it by both sides.

The rest goes by induction.

Base case: , .

Inductive step:

(4)​

Again, by induction.

Base: tree of height has nodes.

Induction:

(5)​

We are tasked with constructing an AVL tree of height while assigning integers to each node such that the AVL properties are preserved. By precomputing subtree sizes using dynamic programming, the assignment process can be streamlined.

Algorithm Steps:

Precompute Subtree Sizes: Use dynamic programming to calculate the sizes of all subtrees up to height . Define to store the size of a tree of height :

This step runs in time.

Main Function fillTree(arr, h):

  • Base case: if , return a tree with a single node containing the first element of arr.
  • Calculate the sizes for left and right subtrees using the precomputed :
  • Use quickSelect to find the (leftSize+1)th smallest element in arr to be the root.
  • Recursively fill the left subtree with the smallest leftSize elements, and the right subtree with the largest rightSize elements.
  • Return the tree.

QuickSelect: This algorithm finds the kth smallest element in an array in average time. It uses a pivot to partition the array and recursively selects the kth element from the appropriate partition.

To rigorously analyze the time complexity of constructing the AVL tree, we use the Akra-Bazzi Theorem, which is a generalization of the Master Theorem and is more suitable for handling recurrences with multiple recursive branches and non-uniform problem sizes.

The time complexity for constructing an AVL tree of height satisfies the following recurrence relation:

Determine for the Akra-Bazzi Theorem:

Hence we have