Question

查找|有序表折半查找判定树|二叉排序树|3阶B-树

Answer 1

首先，长度为n的有序表折半查找判定树的构造方法为：
1）当n=0时
​折半查找判定树为空；
2）当n>0时
​根节点mid(root)=(n+1)/2
​根的左子树是有序表r[1]~r[mid-1]的折半查找判定树（递归）
​根的右子树是有序表r[mid+1]~r[n]的折半查找判定树（递归)

即
（5）
（2） （8）

由此递归可得判定树如附件图

平均查找长度
ASL=(1×1+2×2+3×4+4×3)/10=29/10

平均查找长度ASL=（1 1+2 2+3 3+4 3+5 2+6 1)/12 = 42/12 = 3.5

2)排序构成有序表
Jan | Feb | Mar | Apr | May | June | July | Aug | Sep | Oct | Nov |Dec
1 2 3 4 5 6 7 8 9 10 11 12
平均查找长度ASL=（1 1+2 2+3 4+4 5）/12 = 37/12

3）平衡二叉树
平均查找长度 ASL = （1 1+2 2+3 4+4 4+5*1）/12 = 38/12

​