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

标签：

• Tokyo-University
• Binary-Search-Tree-Insertion-and-Deletion
• Balanced-Binary-Search-Tree-Height-Bounds

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 $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$.

题目描述

回答关于二叉搜索树的下列问题。结点的“高度”定义为该结点到其后代叶结点的最大图距离；例如，无子结点的结点高度为 $0$。树的高度定义为根结点的高度。

（1）对题图所示的二叉搜索树，按顺序执行：

1. 插入 $3$；
2. 插入 $8$；
3. 删除 $4$；
4. 删除 $9$。

画出每次操作后的树。

（2）给出含 $n$ 个结点的二叉搜索树可能具有的最小高度和最大高度。

若二叉搜索树的每个结点均满足以下条件，则称其为平衡二叉搜索树：

• 有两个子结点时，左右子树的高度差不超过 $1$；
• 只有一个子结点时，该子树的高度为 $0$。

继续回答：

（3）给出含 $7$ 个结点的平衡二叉搜索树的最小高度和最大高度，并分别画出达到最大高度和最小高度的树。

（4）给出含 $n$ 个结点的平衡二叉搜索树的最小高度。

（5）证明含 $n$ 个结点的平衡二叉搜索树的高度不超过 $2\log_2 n$。

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 $n$ nodes is $\lfloor \log_2n\rfloor$. Maximum height: $n-1$.

(3)

The minimum height is $2$, attained by

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

The maximum height is $3$, attained by

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

(4)

For $n\ge1$, the minimum is $\lfloor\log_2 n\rfloor$. A complete binary tree with $n$ nodes attains this height and satisfies the balance conditions; assign its keys in increasing inorder to obtain a binary search 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)$ be the minimum number of nodes in a balanced tree of height $h$. A minimum tree of height $h\geq2$ consists of a root and minimum subtrees of heights $h-1$ and $h-2$. Thus $N(0)=1$, $N(1)=2$, and

$$\begin{aligned} N(h) &= 1 + N(h-1) + N(h-2) \\ &\geq 2N(h-2). \end{aligned}$$

Induction gives $N(h)\geq 2^{h/2}$. Therefore $n\geq N(h)\geq 2^{h/2}$, so $h\leq 2\log_2 n$.