跳到主要内容

京都大学 情報学研究科 知能情報学専攻 2021年2月実施 基礎科目 F2-1

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

Answer the following questions about binary search trees.

(1) Draw one binary search tree of smallest height containing the nine elements

{8,13,10,7,1,6,17,14,11}.\{8,13,10,7,1,6,17,14,11\}.

(2) Draw one binary search tree of greatest height containing the same elements.

(3) Suppose each element is queried with equal probability in the tree given in (1). What is the expected number of visited nodes required to find it?

(4) A binary search tree is a complete binary tree with 2d−12^d-1 distinct elements, where dd is a positive integer. If each element is queried with equal probability, what is the expected number of visited nodes required to find it?

题目描述​

回答有关二叉搜索树的问题。

  1. 用元素 {8,13,10,7,1,6,17,14,11}\{8,13,10,7,1,6,17,14,11\} 画一棵高度最小的二叉搜索树。
  2. 用同一组元素画一棵高度最大的二叉搜索树。
  3. 在第 1 问所画的树中等概率查询一个元素，求成功找到该元素所访问结点数的期望。
  4. 一棵二叉搜索树是含 2d−12^d-1 个互异元素的完全二叉树。等概率查询一个元素时， 求成功查找所访问结点数的期望。

Kai​

(1)​

One smallest-height tree is

          10
        /    \
       6      14
      / \    /  \
     1   8  13  17
        /   /
       7   11

Its height is 33 when height is counted by edges, or equivalently it has four levels. No tree of height 22 can contain nine nodes because it can contain at most 23−1=72^3-1=7 nodes.

(2)​

A degenerate binary search tree has the greatest possible height:

1
 \
  6
   \
    7
     \
      8
       \
        10
          \
           11
             \
              13
                \
                 14
                   \
                    17

Its height is 88 edges, or nine levels.

(3)​

In the tree from (1), the numbers of nodes at depths 0,1,2,30,1,2,3 are 1,2,4,21,2,4,2, respectively. A node at depth kk requires k+1k+1 visits. Therefore,

E[N]=1⋅1+2⋅2+4⋅3+2⋅49=259.\boxed{ \mathbb{E}[N] =\frac{1\cdot1+2\cdot2+4\cdot3+2\cdot4}{9} =\frac{25}{9}.}

(4)​

The tree has dd levels. Level kk contains 2k−12^{k-1} nodes, and finding a node on that level requires kk visits. Thus

E[N]=∑k=1dk2k−12d−1=(d−1)2d+12d−1.\begin{aligned} \mathbb{E}[N] &=\frac{\sum_{k=1}^{d}k2^{k-1}}{2^d-1}\\ &=\frac{(d-1)2^d+1}{2^d-1}. \end{aligned}

Hence

E[N]=(d−1)2d+12d−1=d−1+d2d−1.\boxed{\mathbb{E}[N] =\frac{(d-1)2^d+1}{2^d-1} =d-1+\frac{d}{2^d-1}.}
本页目录