【精品课件】检索.pptVIP

第9章　检索 9.1 检索的基本概念 9.2 线性表的检索 9.2.2二分法检索 9.2.3分块检索 9.3 二叉排序树 9.4丰满树和平衡树 9.4.1丰满树 9.4.2平衡二叉排序树 9.5最佳二叉排序树和Huffman树 9.5.1扩充二叉树 9.5.2最佳二叉排序树 9.5.3 Huffman树 9.6 B-树 9．6．2 B-树的基本操作 9.7散列表检索 9.7.2散列函数的构造 9.7.3冲突处理 a1 b0 1 1 a3 3 a2 b1 4 2 b2 3 a4 b3 2 3 b4 1 a2 4 a1 b0 1 1 b1 2 a3 b2 3 3 a4 b3 2 3 b4 1 花费 53 42 总权 20 20 a3 3 a2 4 b2 3 a1 b0 1 1 b1 2 a4 b3 2 3 b4 1 a4 2 b4 1 a2 4 a1 b0 1 1 b1 2 a3 b2 3 3 b3 3 花费 C[0，4]=C[0，2]+C[3，4]+20=41 50 总权 20 20 （d）包括四个内部结点的最佳二叉排序树 9.8 结点关键字k1，k2，k3，k4，k5为一个有序序列，它们的相对使用频率分别为p1=6，p2=8，p3=12，p4=2，p5=16，外部结点的相对使用频率分别为q0=4，q1=9，q2=8，q3=12，q4=3，q5=2。试构造出有序序列k1，k2，k3，k4，k5所组成的最优查找树。 习题 ? 对于包括n个关键码的集合，构造最佳二叉排序树过程中需要进行C[i，j]（0?ij?n）的计算次数为： 给定n个结点k1，k2，…，kn，它们的权分别是W（ki）（1?i?n），现要利用这n个结点作为外部结点（叶子结点）去构造一棵扩充二叉树，使得带权外部路径长度 WPL= 达到最小值，其中wki为外部结点ki的权值，?ki是从根结点到达外部结点ki的树枝长度。具有最小带权外部路径长度的二叉树称为Huffman树。 例如4个结点k1，k2，k3，k4，分别带权10，16，20，6。利用它们作为外部结点分别构造了以下三棵扩充二叉树（还有其它形式的扩充二叉树）如图9.13所示。 （a） （b） （c） 图9.13 具有不同带权路径长度的扩充二叉树 其带权路径长度分别为： （a）WPL=52?2=104 （b）WPL=（16+20）?3+20?2+6?1=154 （c）WPL=（10+6）?3+16?2+20?1=100 其中图9.13（c）所示的扩充二叉树带权外部路径长度最小，可以验证，它恰为Huffman树。一般情况下，权越大的叶子离根越近，那么二叉树的带权外部路径长度就越小。在实际的应用中，分支程序的判断流程可用一棵Huffman树来表示，如果出现概率越大的分枝（条件语句）离根越近，那么所需执行的判断语句就越少，这样便可提高程序的执行效率。 Huffman给出了求具有最小带权外部路径长度的扩充二叉树的方法，通常称为Huffman算法，该算法可描述如下： （1）根据给定的n个权值{w1，w2，…，wn}构造n棵二叉树的集合F={T1，T2，…，Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左、右子树均为空。 （2）在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点权值为其左、右子树根结点的权值之和。 （3）在F中用新得到的二叉树代替这两棵树。 （4）重复（2）、（3）过程，直到F中只含有一棵树为止。 root? 6 ? 10 ? 16 ? 20 ? 24 ? 30 具体实现可以采用有序链表存储结构 例如：对于结点序列10、16、20、6、30、24 ，构造huffman树的过程如下： （1）建立有序链表 （2）从链表中截取前面二棵根结点权值最小的树作为左右子树，生成一棵新的子树，并将新子树按其根的权值插入有序链表中去，如此循环，直到只剩一棵树为止。 root 6 16 20 24 30 10 16 1 root 6 16 20 24 30 10 16 32 2 root 6 16 20 24 30 10 16 32 44 3 root 6 16 20 24 30 10 16 32 44 62