Skip to content

東京大学 情報理工学系研究科 コンピュータ科学専攻 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.

1
2
3
4
5
6
7
         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 \(n\) 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 \(1\).
  • In case the node has only one child, the height of the child subtree is \(0\).

Answer the following questions.

(3) Answer the minimum and maximum tree heights of a balanced binary search tree with \(7\) 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 \(n\) nodes.

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

Kai

(1)

(i)

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

(ii)

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

(iii)

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

(iv)

1
2
3
4
5
6
7
          8
       /     \
      3       12
    /   \    /  \
   2     7  10  14
        /
       6

(2)

Minimum height of BST with \(n\) nodes is \(\lfloor \log_2n\rfloor\). Maximum height: \(n-1\).

(3)

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

1
2
3
4
5
6
7
            3
        /       \
       2         1
     /   \     /
    1     0   0
   /
  0

(4)

Just \(\lfloor \log_2n\rfloor\) – it's a full binary tree.

(5)

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

Let's consider the smallest possible AVL trees wrt number of nodes. Let \(N(h)\) indicate minimum number of nodes in a balanced tree of height \(h\). The minimum tree of \(n\) nodes and height \(h\) consists of a root, a minimum subtree of of height \(h-1\) and a minimum subtree of height \(h-2\):

\[ \begin{aligned} n = N(h) &= 1 + N(h-1) + N(h-2) \\ &\geq 1 + 2 \cdot N(h-2) && \text{because } N(h) > N(h-1) \\ &> 2 \cdot N(h-2) \\ &\geq 2^{\frac{h}{2}} \end{aligned} \]

Taking log both sides: \(h \leq 2\cdot \log_2(n)\).