東京大学 情報理工学系研究科 コンピュータ科学専攻 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
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
(4) Answer the minimum tree height of a balanced binary search tree with
(5) Show that the height of a balanced binary search tree with
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
(3)
AVL tree with
3
/ \
2 1
/ \ /
1 0 0
/
0
(4)
Just
(5)
Show that the height of a balanced binary tree (AVL) with
Let's consider the smallest possible AVL trees wrt number of nodes.
Let
Taking log both sides: