P5
211275022田昊东¶
6.6¶
6.9: (1)¶
-
0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 -
成功的平均搜索长度：\(\frac1{10}(1+1+1+1+1+1+1+4+1+2)=1.400\)
-
不成功的平均搜索长度：\(\frac1{13}(2+1+3+2+1+5+4+3+2+1+5+4+3)=2.769\)
6.10¶
-
\[ 设表的大小至少为x\\ \alpha=150/x\\ (1+1/(1-150/x))/2<=2\\ x>=225 \]
-
即至少为 \(225\)
6.12¶
- 平均读盘1.5次就是说查询一次平均检查记录的数目为\((30/2+30+(60-30)/2)/2=30\)
- 至少设置桶的数目 \(15000/30=500\)
7.2¶
- 成功：\((1+2+\dots+14)/14=7.5\)
- 失败：\((1+2+\dots+14+14)/15=7.933\)
7.3¶
- 成功：\((1+2*2+4*3+7*4)/14=3.214\)
- 失败：\((3+14*4)/15=3.933\)
7.8¶
- 初始的二叉搜索树：
- 删除for之后的二叉搜索树：
- 重新插入for的二叉搜索树（不相同）：
7.15¶
- 最终结果
7.16¶
- 删除MAY：叶子节点可以直接删除
- 删除FEB：用中序遍历前继替代
