已知一组关键字为{25,18,46,2,53,39,32,4,74,67,60,11}。按表中的元素顺序依次插入到一棵初始为空的二叉排序树中，画出该二叉排序树，并求在等概率的情况下查找成功和查找不成功情况下的平均查找长度。

插入顺序为25、18、46、2、53、39、32、4、74、67、60、11。初始为空的二叉排序树如下图所示：

       25
      /  \
     18  46
    /   /  \
   2   39  53
    \    / 
     4  32
        \
        74
        /
       67
      /
     60
    /
   11

在等概率的情况下查找成功和查找不成功情况下的平均查找长度分别为：

对于查找成功的情况，每个元素被查找到的概率均为1/12，因此平均查找长度为(1+2+2+3+3+3+3+4+4+4+4+5)/12=3.08。

对于查找不成功的情况，需要遍历到每个叶子结点才能确定查找失败，因此平均查找长度为(4+3+3+4+4+4+4+5+5+5+5+6)/12=4.42。

相关问题

已知一组关键字为(16,74,60,43,90,46,31,29,88,77,66,09,地址空间为0至12,哈希函数取H(key)=key%13 (1)写出用链地址处理冲突构造哈希表 (2)写出用线性探测再散列处理冲突构造哈希表

(1) 使用链地址处理冲突构造哈希表的方法：

首先，创建一个大小为13的空哈希表，用于存储关键字。

接下来，对于每个关键字，计算其哈希值（使用哈希函数H(key)=key%13），并将其插入到哈希表中对应的链表中。

如果哈希表中对应位置已经存在其他关键字，则将该关键字添加到链表的末尾。

最终，哈希表的结构如下：

0: 60 -> 29
1:
2: 16 -> 90
3: 43 -> 77
4: 74 -> 88
5: 46
6: 31
7:
8:
9: 66 -> 09
10:
11:
12:

(2) 使用线性探测再散列处理冲突构造哈希表的方法：

首先，创建一个大小为13的空哈希表，用于存储关键字。

对于每个关键字，计算其哈希值（使用哈希函数H(key)=key%13）。

如果哈希表中对应位置为空，则将该关键字插入到该位置。

如果哈希表中对应位置已经存在其他关键字，则使用线性探测的方法，依次检查下一个位置是否为空，直到找到一个空位置为止，并将该关键字插入到该位置。

如果哈希表中已经没有更多的空位置，则需要进行再散列操作。在再散列操作中，首先创建一个更大的哈希表，并将所有已经插入的关键字重新插入到新哈希表中。

最终，哈希表的结构如下：

0: 60
1: 16
2: 74
3: 43 -> 46
4: 90
5: 31 -> 77
6: 29 -> 88
7:
8:
9: 66
10:09
11:
12:

.已知一组关键字为(15,28,33,47,52,66,78),采用链地址法处理中卖,暂麦是一个下以d

链地址法是一种常见的哈希表处理冲突的方法。在链地址法中，我们使用一个数组来存储关键字的哈希值，并将哈希值相同的关键字存储在同一个链表中。

对于给定的关键字组(15,28,33,47,52,66,78)，我们可以使用链地址法处理如下：

1. 创建一个长度为N的数组，N是预估的关键字的最大数量。在本例中，最大的关键字是78，所以可以选择数组长度为80。
2. 将关键字通过哈希函数转化为哈希值，并将哈希值取余N，得到关键字在数组中的索引。
- 假设我们使用简单的哈希函数，将关键字除以N，然后取余。
3. 在数组中，为每个索引位置创建一个链表。
4. 遍历关键字组，对于每个关键字，计算其哈希值，并将其插入到对应索引位置的链表中。

使用链地址法处理给定关键字组(15,28,33,47,52,66,78)的过程如下：

1. 创建一个长度为80的数组。数组的每个元素都是链表的头指针，初始值为null。
2. 遍历关键字组：
- 对于关键字15，计算哈希值为15，将其插入到索引为15的链表中。
- 对于关键字28，计算哈希值为28，将其插入到索引为28的链表中。
- 对于关键字33，计算哈希值为33，将其插入到索引为33的链表中。
- 对于关键字47，计算哈希值为47，将其插入到索引为47的链表中。
- 对于关键字52，计算哈希值为52，将其插入到索引为52的链表中。
- 对于关键字66，计算哈希值为66，将其插入到索引为66的链表中。
- 对于关键字78，计算哈希值为78，将其插入到索引为78的链表中。
3. 最终的数组如下：
- 索引0：
- 索引1：
- 索引2：
- ...
- 索引14：
- 索引15：15 -> null
- 索引16：
- ...
- 索引27：
- 索引28：28 -> null
- ...
- 索引32：
- 索引33：33 -> null
- ...
- 索引46：
- 索引47：47 -> null
- ...
- 索引51：
- 索引52：52 -> null
- ...
- 索引65：
- 索引66：66 -> null
- ...
- 索引77：
- 索引78：78 -> null
- ...
- 索引79：

通过链地址法，我们可以很快地找到给定关键字所对应的链表，从而快速进行查找、插入和删除操作。