12最佳和平衡二叉排序树.pdf

《12最佳和平衡二叉排序树.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、面向21世纪课程教材普通高等教育“十一五”国家级规划教材北京市高等教育精品教材教育部普通高等教育精品教材算法与数据结构第十二讲最佳和平衡二叉排序树1张乃孝等编著《算法与数据结构—C语言描述》7高级字典结构•7.4最佳二叉排序树•7.5平衡二叉排序树27.4最佳二叉排序树对同一关键码集合,不同的元素插入顺序,可能构造n!个不同(高度和形态)的二叉排序树!哪种二叉排序树的检索效率最高？具有最小平均比较次数！3扩充的二叉排序树扩充的二叉排序树的对称序周游序列:–从最左下(记号为0)的外部结点开始;–以最右下(记号为n)的外部结点结束;–所有内/外部结点都是交叉排列:第i个内部结点位于第i

2、-1个外部结点和第i个外部结点之间;外部结点代表位于其相邻的两个内部结点关键码之间的所有不属于当前字典的关键码集合.对检索来说:–如果被检索结点位于二叉树中第i层,比较次数为i+1;–如果该结点不存在,只有找到一个外部结点时确定检索失败,比较次数为此外部结点的层数.4平均比较次数在扩充的二叉排序树里，检索一个关键码的平均比较次数为:nn1En()=∑∑pli(i++1)qlii′wii=10=其中li是第i个内部结点的层数,l'i是第i个外部结点的层数,pi是检索第i个内部结点关键码的频率,qi是被检索的关键码属于第i个外部结点关键码集合的频率,qi,pi也叫结点的权nn.

3、wpq=∑∑ii+ii=10=pi/w是检索第i个内部结点关键码的概率,qi/w是被检索的关键码属于第i个外部结点关键码集合的概率.5最佳二叉排序树最佳二叉排序树:E(n)最小的二叉排序树。–根结点的关键码确定,左右子树的关键码集合也惟一确定;–左右子树也是最佳二叉排序树。–如何构造最佳二叉排序树?等概率的检索不等概率的检索6等概率的检索假设字典的关键码满足：key<<

4、外部路径长度.EPL=IPL+2*n若内部路径长度IPL最小,则平均比较次数E(n)最小!7最小平均比较次数要使得E(n)最小，则二叉树需满足∶除最下层的叶结点度数均为0外，只有倒数第二层结点的度数可以小于2，其它结点度数必须等于2。这样的二叉排序树IPL为：0+1+1+2+2+2+2+3+……nlog2n+1IPL=∑log22k=(n+1log)n−+22k=1平均比较次数E(n)是O(log2n)!8等概率的最佳二叉排序树的构造(1)先将字典元素的关键码排序;(2)对每个关键码按二分法在排序关键码序列中执行检索,将检索中遇到的还未在二叉排序树中的关键码

5、插入二叉排序树中。–使用二叉排序树的插入算法。9•考虑K={5,10,18,25,27,41,51,73,99}构造算法(不计排序)的时2间代价为7O(nlog2n);51检索时间代价10为O(log2n).7145813929510不等概率的检索例子：给定关键码集合K={A,B,C},权集合{5,1,2}和{4,3,1,1},构造一个具有三个内部结点,四个外部结点的最佳二叉排序树.采用等概的方法构造的不一定最佳：11不等概率最佳二叉排序树的构造给定排序的关键码集合{key,key,…,key}和两个权集合12n{p,…,p}和{q,q…,q},其中p是检索内部结点i的概率,1n0

6、1niq是被检索关键码属于外部结点j的关键码集合的概率。j问题:要求构造一棵最佳二叉排序树,即构造出一棵二叉排序树,使下面的函数达到最小(E(n)一定也达到最小)：nn∑p(l+1)+∑ql′iiiii=1i=0上式称为包含n个内部结点和n+1个外部结点的二叉排序树的花费,记作C(0,n)。最佳二叉排序树里的任何子树都最佳。12记法说明设对应key,key,…,key的内部结点为12nv1,…,vn，外部结点为e0,e1,…,en用T(i,j)代表包含内部结点vi+1,…,vj和外部结点ei,ei+1…,ej的最佳二叉排序树,权的总和记为W(i,j),其根记为R(i,j),花费记为C(

7、i,j)。–例：T(0,1)表示包含内部结点v1，以及外部结点e0,e1的最佳二叉排序树–T(2,5)表示包含内部结点v3,v4,v5以及外部结点e2,e3,e4,e5的最佳二叉排序树。13构造最佳二叉排序树的主要思想从小到大地构造T(i,j).–步骤1：构造包含一个内部结点:T(0,1),T(1,2),…,T(n-1,n);–步骤2：构造包含二个内部结点:T(0,2),T(1,3),…,T(n-2,n);