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

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

n为10折半查找判定树和ASL.png

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

月份有序表折半查找.png

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树的状态。

---

3阶B-.PNG

​