跳到主要内容

東京大学 情報理工学系研究科 コンピュータ科学専攻 2016年2月実施 問題3

Author

kainoj, 祭音Myyura

Description

Answer the following questions concerning binary search trees. Here, the height of a node is defined as the maximum of the graph distance from the node to one of its descendant leaf nodes. For example, a node with no children is of height 0. The height of a tree is defined as the height of its root.

(1) Suppose that we have the following binary search tree.

         9
/ \
4 12
/ \ / \
2 7 10 14
/
6

Let us apply the following operations to the above tree, in the shown order.

  • (i) Insert 3
  • (ii) Insert 8
  • (iii) Delete 4
  • (iv) Delete 9

Depict the state of the tree after each operation.

(2) Answer the minimum and maximum tree heights of a binary search tree with nodes.

We call a binary search tree balanced if every node of it satisfies the following conditions:

  • In case the node has two children, the heights of the left and right child subtrees differ by at most .
  • In case the node has only one child, the height of the child subtree is .

Answer the following questions.

(3) Answer the minimum and maximum tree heights of a balanced binary search tree with nodes. Depict a tree with the maximum height, and one with the minimum height.

(4) Answer the minimum tree height of a balanced binary search tree with nodes.

(5) Show that the height of a balanced binary search tree with nodes is no more than .

Kai

(1)

(i)

          9
/ \
4 12
/ \ / \
2 7 10 14
\ /
3 6

(ii)

          9
/ \
4 12
/ \ / \
2 7 10 14
\ / \
3 6 8

(iii)

          9
/ \
3 12
/ \ / \
2 7 10 14
/ \
6 8

(iv)

          8
/ \
3 12
/ \ / \
2 7 10 14
/
6

(2)

Minimum height of BST with nodes is . Maximum height: .

(3)

AVL tree with nodes has min. height of (full binary tree), and max. height of . See following:

            3
/ \
2 1
/ \ /
1 0 0
/
0

(4)

Just – it's a full binary tree.

(5)

Show that the height of a balanced binary tree (AVL) with nodes is no more than .

Let's consider the smallest possible AVL trees wrt number of nodes. Let indicate minimum number of nodes in a balanced tree of height . The minimum tree of nodes and height consists of a root, a minimum subtree of of height and a minimum subtree of height :

Taking log both sides: .