最佳二叉搜索树定义 以是检索第个内部结点所代表的关键码 的概率,是被检索的关键码属于第个外 部结点代表的可能关键码集合的概率 我们把检索中平均比较次数最小,也 就是ASL(m)最小的二叉搜索树称作最佳 二叉搜索树 北京大学信息学院 版权所有,转载或翻印必究 Page 36
北京大学信息学院 ©版权所有，转载或翻印必究 Page 36 最佳二叉搜索树定义 ◼ 是检索第i个内部结点所代表的关键码 的概率， 是被检索的关键码属于第i个外 部结点代表的可能关键码集合的概率。 ◼ 我们把检索中平均比较次数最小，也 就是ASL(n)最小的二叉搜索树称作最佳 二叉搜索树 W p1 W qi
什么样的二叉搜索树是最佳的 检索所有结点的概率都相等,即所有结点的权都相等: p1 p pn qo q WWW W2n+1 AS(n)=n,∑(+1)+∑1 n 2n+1 1+n+∑l (+n+e) 2I+3n 2n+1 2n+1 因此,要平均比较次数ASL(n)最小,就是要内 部路径长度Ⅰ最小 北京大学信息学院 版权所有,转载或翻印必究 Page 37
北京大学信息学院 ©版权所有，转载或翻印必究 Page 37 什么样的二叉搜索树是最佳的 ？ ◼ 检索所有结点的概率都相等，即所有结点的权都相等： ◼ 因此，要平均比较次数ASL(n)最小，就是要内 部路径长度I最小 2n 1 1 W q W q W q W p W p W p1 2 n 0 1 n + = == = = == = = = + + + = n i 1 n i 0 i i ( l n l 2n 1 1 (I n E) 2n 1 1 + + + = 2n 1 2I 3n + + = 1 0 1 ( ) ( ( 1) ) 2 1 n n i i i i ASL n l l n = = = + + +
■在一棵二叉树里,路径长度为0的结点仅有 路径长度为1的结点至多有两个,路径长 度为2的结点至多有四个,等等。因此,有n个 结点的二叉树其内部路径长度I至少等于序列: 0,1,1,2,2,2,2,3,3,3,3,3,3,3, 4,4,…的前n项和。这个和写成: ∑log2k」 北京大学信息学院 版权所有,转载或翻印必究 Page 38
北京大学信息学院 ©版权所有，转载或翻印必究 Page 38 ◼ 在一棵二叉树里，路径长度为0的结点仅有一 个，路径长度为1的结点至多有两个，路径长 度为2的结点至多有四个，等等。因此，有n个 结点的二叉树其内部路径长度I至少等于序列: 0，1，1，2，2，2，2，3，3，3，3，3，3，3， 4，4，…的前n项和。这个和写成: = n k 1 log 2 k
可以证明:∑bog2k=(n+1bg2n-21+2 k=1 这种二叉树的特点是只有最下面的两层结点的 度数可以小于2,其它结点度数必须等于2。在所 有结点的权相等的情况下,这样的二叉搜索树是 最佳二叉搜索树,对它进行检索的平均比较次数 为 AsL(n) 2(n+1Log2n」-2,+4+3n (公式12.3) 2n+1 这个ASL(m)是O(og2n)量级的 北京大学信息学院 版权所有,转载或翻印必究 Page 39
北京大学信息学院 ©版权所有，转载或翻印必究 Page 39 ◼可以证明： ◼这种二叉树的特点是只有最下面的两层结点的 度数可以小于2，其它结点度数必须等于2。在所 有结点的权相等的情况下，这样的二叉搜索树是 最佳二叉搜索树，对它进行检索的平均比较次数 为 ◼这个ASL(n)是O(log2n)量级的 log ( 1) log 2 2 log 1 1 2 2 2 = + − + + = n n k k n n 2 log 2 2 2( 1) log 2 4 3 ( ) ( 12.3) 2 1 n n n n ASL n n + + − + + = + 公式
最佳二叉搜索树构造举例 ■首先将集合K里的关键码排序{wan,wen,wi, wim, wul, xal, xem, xul, yo, yon, yum, zi, zol, zom) ■然后用二分法依次检索这些关键码,并把在检 索中遇到的在二叉搜索树里还没有的关键码依 次插入二叉搜索树中。 首先检索序列中的第一个关键码wan,用二分 法检索wan的过程中会依次遇到关键码xem, wil,wan,这就是最先插入二叉搜索树的三个 关键码。 北京大学信息学院 版权所有,转载或翻印必究 Page 40
北京大学信息学院 ©版权所有，转载或翻印必究 Page 40 最佳二叉搜索树构造举例 ◼ 首先将集合K里的关键码排序 {wan，wen，wil， wim，wul，xal，xem，xul，yo，yon，yum， zi，zol，zom} ◼ 然后用二分法依次检索这些关键码，并把在检 索中遇到的在二叉搜索树里还没有的关键码依 次插入二叉搜索树中。 ◼ 首先检索序列中的第一个关键码wan，用二分 法检索wan的过程中会依次遇到关键码xem， wil，wan，这就是最先插入二叉搜索树的三个 关键码