数据结构-检索.ppt

用（ai+1，ai+2，…，aj）作为内部结点构造最佳二叉排序树T[i，j]的方法可如下进行：分别用ai+1，ai+2，…，aj为根，共考虑j-i棵二叉排序树，以ak为根的二叉排序树其左子树包括ai+1，…，ak-1，而包括这些关键码为内部结点的最佳二叉排序树T[i，k-1]已在前面的步骤确定，C[i，k-1]已求出，而以ak为根的二叉排序树其右子树包括ak+1，ak+2，…，aj，以这些关键码为内部结点的最佳二叉排序树T[k，j]也已在前面的步骤确定，C[k，j]已求出。 对于ik?j，找出使C[i，k-1]+C[k，j]最小的那个k’，以ak’为根，T[i，k’-1]为左子树，T[k’，j]为右子树的那棵二叉排序树就是所求的T[i，j]。其花费C[i，j]等于其根的左子树花费C[i，k’-1]加上右子树花费C[k’,j] ，再加上结点总的权W[i，j]，即C[i,j] =W[i，j] + C[i，k’-1]+ C[k’，j]。 综上所述，T[i，j]是最优查找树必须满足条件： C[i，j]=W[i，j]+ （C[i，k-1]+C[k，j]） （9-20） 假设n=4，且（a1，a2，a3，a4）=（10，18，26，50）；（p1，p2，p3，p4）=（1，4，3，2），（q0，q1，q2，q3，q4）=（1，2，3，3，1），试构造出有序序列a1，a2，a3，a4所组成的最优查找树。 例 首先根据式（9-20）构造包括一个内部结点的最佳二叉排序树，其花费的代价分别是C[0，1]=4，C[1，2]=9，C[2，3]=9和C[3，4]=6，如图9.12（a）所示。 a1 b0 1 1 b1 2 a2 b1 4 2 b2 3 a3 b2 3 3 b3 3 a4 b3 2 3 b4 1 花费 C[0，1]=4 C[1，2]=9 C[2，3]=9 C[3，4]=6 总权 4 9 9 6 （a）包括一个内部结点的最佳二叉排序树 a1 b0 1 1 a2 b1 4 2 b2 3 a2 4 b2 3 a1 b0 1 1 b1 2 a2 b1 4 2 a3 b2 3 3 b3 3 花费 20 C[0，2]=C[0，1]+11=15 C[1，3]=C[2，3]+15=24 总权 11 11 15 （b）包括二个内部结点的最佳二叉排序树 a3 3 b3 3 a2 b1 4 2 b2 3 a3 b2 3 3 a4 b3 2 3 b4 1 a4 2 b4 1 a3 b2 3 3 b3 3 花费 24 C[2，4]=C[3，4]+12=18 21 总权 15 12 12 （b）包括二个内部结点的最佳二叉排序树 a1 b0 1 1 a2 b1 4 2 a3 b2 3 3 b3 3 a2 4 a1 b0 1 1 b1 2 a3 b2 3 3 b3 3 a3 3 b3 3 a2 4 b2 3 a1 b0 1 1 b1 2 花费 41 C[0，3]=C[0，1]+C[2，3]+17=30 32 总权 17 17 17 （c）包括三个内部结点的最佳二叉排序树 a2 b1 4 2 a3 b2 3 3 a4 b3 2 3 b4 1 a3 3 a2 b1 4 2 b2 3 a4 b3 2 3 b4 1 a4 2 b4 1 a2 b1 4 2 a3 b2 3 3 b3 3 花费 36 C[1，4]=C[1，2]+C[3，4]+18=33 42 总权 18 18 18 （c）包括三个内部结点的最佳二叉排序树 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