二叉排序树的建立.ppt

文档介绍：最优二分树(最优二叉搜索树)
二叉搜索树
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)
d1
d1
d3
T1,3
(p3)
d3
k3
d2
(q1)
(q2)
(q3)
k1
(p2)
d1
d1
(q1)
(q2)
k2
(q3)
W(1,3)=10
C(T1,3) = W(1,3)+min{C(T1,1(2))+C(T2,3(2)),C(T1,2(3))+C(T3,3(3))
=10+min{6,7}
=16
d2
例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
例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