文档介绍：最优二分树(最优二叉搜索树)
二叉搜索树
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
一、最优二分树的搜索
煞适檀第争涕劫竖寥坞席惰高踌距基撕宛叔啃蓄却挡咨双萧迭赐蝉功蠢汗二叉排序树的建立二叉排序树的建立
45
53
100
61
12
3
90
78
37
24
若二叉树为空:
则生成根结点。
若二叉树非空:
(1)利用二分搜索树的搜索方法,找出被插结
点的父结点。
(2)判断被插结点是其父结点的左孩子或右孩子?将其作为叶子结点插入。
例3-4:以{ 45,53,12,37,24,100,3,61,90,78 }

为例构造二分搜索树。
二、等概率情形的二分搜索树的建立
等概率时
书敞翌烩备作批散瘦锤悠秀豆伍每刻坡泼橱球雪殷桩宅旱克埂靖峙召残搞二叉排序树的建立二叉排序树的建立
例3-4-2
三、非等概率情形的二分搜索树的建立
联云怨乖招谆欧灼瞧拨饲见精恩芹订泳莆煽称绥滦瘴茎验乃垛浚销办尘志二叉排序树的建立二叉排序树的建立
二叉树T:有n个内点k1,k2,…,kn——查找成功的n种
有n+1个叶子,d0,d1,..,dn——查找失败n+1种
查找成功与不成功的概率
二查找树的期望耗费
pi:ki查找成功的概率
qi: di查找失败的概率
C(T): 树的带权路径长度
(平均查找长度)
depth(ki):ki—根的距离
扼热赫矾离议迟狠勒谬判忍经犁炉沉虽疚踢红视梢症约徊途秒宗函伯瞪斯二叉排序树的建立二叉排序树的建立
C(T)=Tl(i)+Tr(i)+p(i)+W(0,i-1)+w(i+1,n)
ki
Tl(i)
Tr(i)
k1---ki-1
d0---di-1
Ki+1---kn
di---dn
二查找树的期望耗费
紧蓝讼魏嫁岿枕棒瞳踌淬詹杂题患济席顶箔韭胺敌妓滁窄颤拱份侄籍熄帧二叉排序树的建立二叉排序树的建立
例7-1-4 n=4(4个内点),k1<k2<k3<k4 p1=1/16, p2=3/16, p3=2/16, p4=2/16 q0=2/16, q1=1/16, q2=3/16, q3= q4=1/16

k1
(p1)
k1
(p2)
k2
k3
(p3)
(p4)
k4
d1
d0
d1
d2
d2
d3
d3
d4
T1,2
T0,1
T2,3
T3,4
C(T0,1)=C(T0,0)+C(T1,1)+w(0,1)=4
C(T1,2)=C(T1,1)+C(T2,2)+w(1,2)=7
C(T2,3)=C(T2,2)+C(T3,3)+w(2,3)=6
C(T3,4)=C(T3,3)+C(T4,4)+W(3,4)=7
(q0)
(q1)
(q1)
(q2)
(q2)
(q3)
(q3)
(q4)
乙勘抗早卜漓霹烃嫁幕争怪谆楞坐锌赢疤伍獭惠傀侵挞束黄镑霄活藩汛唯二叉排序树的建立二叉排序树的建立

k1
(p1)
k2
(p2)
d1
d0
d2
T0,2
(p2)
d2
k2
d1
(q0)
(q1)
(q2)
k1
(p1)
d1
d0
(q0)
(q1)
k1
(q2)
W(0,2)=10
C(T0,2) = W(0,2)+min{C(T0,0(1))+C(T1,2(1)),C(T0,1(2))+C(T2,2(2))
=10+min{7,4}
=14
d1
例7-1-4 n=4(4个内点),k1<k2<k3<k4 p1=1/16, p2=3/16, p3=2/16, p4=2/16 q0=2/16, q1=1/16, q2=3/16, q3= q4=1/16
舰峨庶匈弯畜粕彝洛伟箍篡中仇卸气寒督患见继挂揪骋攫甩检息釉询狱涎二叉排序树的建立二叉排序树的建立

k2
(p2)
k3
(p3)