1
画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
首先，长度为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）
即当n=10时
1）根节点为（10 +1）/2=5
2）根左子树为r[1]~r[4],左子节点为（4+1）/2=2
2->left:(1+1)/2=1
2->right:(3+4)/2=3
2->right->right =4
3）根右子树为r[6]~r[10]，右子节点为( 6+10)/2=8
3->left:(6+7)/2 = 6
3->left->right = 7
3->right:(9+10)/2=9
3->right->right=10
由此递归可得判定树如附件图
平均查找长度
ASL=(1×1+2×2+3×4+4×3)/10=29/10
2
已知如下所示长度为12的表
(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)
(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后##的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
(2)若对表中元素先进行排序构成有序表，求其在等概率的情况下对此有序表进行##折半查找时查找成功的平均查找长度。
(3)按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
1)按字典序完成二叉排序树
Jan
/ \
Feb Mar
/ / \
Apr June May
\ / \
Aug July Sep
\ /
Dec Oct
/
Nov
平均查找长度ASL=（11+22+33+43+52+61)/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=（11+22+34+45）/12 = 37/12
3）平衡二叉树
平均查找长度 ASL = （11+22+34+44+5*1）/12 = 38/12
3
试从空树开始，画出按以下次序向2-3树即3阶B-树中插入关键码的建树过程：20,30,50,52,60,68,70。如果此后删除50和68，画出每一步执行后2-3树的状态。
