7 查找与排序
7.1
7.1
最
最
优
优
二
二
分
分
树
树
（
（
最
最
优
优
二
二
叉
叉
搜
搜
索
索
树
树
）
）
• 二叉搜索树
1. 若它的左子树不空，则左子树上所有
结点的值均小于它的根节点的值；
2. 若它的右子树不空，则右子树上所有
结点的值均大于它的根节点的值；
3. 它的左、右子树也分别为二叉搜索树
45
12
53
3
37
24
100
61
90
78
在随机的情况下，二叉查找树的平均查找长度
和 是等数量级的
搜索方法：
若根结点的关键字值等于搜索的关
键字，查找成功。
否则，若小于根结点的关键字值，
搜索其左子树。若大于根结点的关键字
的值，则搜索其右子树。
在左右子树上的操作类似。
例: (1)查找k=24
(2)查找k=60
45
53
100
61
12
3
90
78
37
24
一
一
、
、
最
最
优
优
二
二
分
分
树
树
的
的
搜
搜
索
索
在一般情况下，P（i）为具有 i 个结点二分搜索树的平均查找长度。
P（n,i）= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n
n-1
P（n）= ∑ P（n,i）/ n
i=0
= 1.465log
2
n
i个关键字<
第一个关键字
N-i+1个关键字
>第一个关键字
53
9337
24
45
12
P（n,i）= P（6, 3）
= [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6
= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6
注意：这里 P(3)、P(2) 是具有 3 个结点、2 个结点的
二叉排序树的平均查找长度。 在一般情况下，
P（i）为具有 i 个结点二叉排序树的平均查找 长度。
P(3) ＝ （1+2+2）/ 3 = 5/3
P(2) ＝ （1+2）/ 2 = 3/2
45
53
100
61
12
3
90
78
37
24
若二叉树为空：
则生成根结点。
若二叉树非空：
（1）利用二分搜索树的搜索方法，找出被插结
点的父结点。
（2）判断被插结点是其父结点的左孩子或右孩
子？将其作为叶子结点插入。
例7-1-1：以{ 45，53，12，37，24，100，3，61，90，78
}
为例构造二分搜索树。
二
二
、
、等概率情形的
二
二
分
分
搜
搜
索
索
树
树
的
的
建
建
立
立
