关于二叉排序树的各种操作,都离不开查找,因此查找是十.ppt

关于二叉排序树的各种操作，都离不开查找，因此查找是十分重要的操作！ 对于有 n 个关键码的集合，其关键码有 n! 种不同排列，可构成不同二叉搜索树有 用树的搜索效率来评价这些二叉搜索树。 查找成功的平均查找长度 查找不成功的平均查找长度 在树中增加失败结点(外部结点), 它们是搜索失败时到达的结点, 物理上实际不存在。 增加了外部结点的二叉搜索树称为扩充二叉搜索树。 例，已知关键码集合 { a1, a2, a3 } = { do, if, to }，对应搜索概率 p1, p2, p3, 在各搜索不成功间隔内搜索概率分别为 q0, q1, q2, q3。可能的二叉搜索树如下所示： 扩充二叉搜索树 * * 二叉搜索树性能分析 (棵) 二叉搜索树性能分析 在扩充二叉搜索树中 ○表示内部结点，包含了关键码集合中的某一个关键码； □表示外部结点，代表各关键码间隔中的不在关键码集合中的关键码。 在每两个外部结点间必存在一个内部结点。 do if to q0 q1 p1 q2 p2 q3 p3 (a) do if to q0 q1 q2 q3 p1 p2 p3 (b) 扩充二叉搜索树 do if to (d) q0 q1 p1 q2 p2 q3 p3 do if to q0 q1 p1 q2 p2 q3 p3 (c) do if to q0 q1 p1 q2 p2 q3 p3 (e) 一棵扩充二叉搜索树的搜索成功的平均搜索长度ASLsucc可以定义为该树所有内部结点上的权值 p[i]与搜索该结点时所需的关键码比较次数c[i] (= l[i])乘积之和： 搜索不成功的平均搜索长度ASLunsucc为树中所有外部结点上权值q[j]与到达外部结点所需关键码比较次数c[j](= l[j]-1)乘积之和： 设树中所有内、外结点的搜索概率都相等： p[i] = 1/3, 1 ? i ? 3 q[j] = 1/4, 0 ? j ? 3 do if to q0 q1 p1 q2 p2 q3 p3 (a) 图(a): ASLsucc = 1/3*( 3 + 2 +1 ) = 6/3 = 2 ASLunsucc = 1/4*( 3 + 3 +2 + 1 ) = 9/4 设树中所有内、外结点的搜索概率都相等： p[i] = 1/3, 1 ? i ? 3 q[j] = 1/4, 0 ? j ? 3 图(b): ASLsucc = 1/3*( 2 + 1 + 2 ) = 5/3 ASLunsucc = 1/4*( 2 + 2 + 2 + 2 ) = 8/4 do if to q0 q1 q2 q3 p1 p2 p3 (b) 设树中所有内、外结点的搜索概率都相等： p[i] = 1/3, 1 ? i ? 3 q[j] = 1/4, 0 ? j ? 3 图(c): ASLsucc = 1/3*( 3 + 2 + 1 ) = 2 ASLunsucc = 1/4*( 3 + 3 + 2 + 1 ) = 9/4 do if to q0 q1 p1 q2 p2 q3 p3 (c) 设树中所有内、外结点的搜索概率都相等： p[i] = 1/3, 1 ? i ? 3 q[j] = 1/4, 0 ? j ? 3 图(d): ASLsucc = 1/3*( 3 + 2 + 1 ) = 2 ASLunsucc = 1/4*( 3 + 3 + 2 + 1 ) = 9/4 do if to (d) q0 q1 p1 q2 p2 q3 p3 设树中所有内、外结点的搜索概率都相等： p[i] = 1/3, 1 ? i ? 3 q[j] = 1/4, 0 ? j ? 3 图(e): ASLsucc = 1/3*( 3 + 2 + 1 ) = 2 ASLunsucc = 1/4*( 3 + 3 + 2 + 1 ) = 9/4 do if to q0 q1 p1 q2 p2 q3 p3 (e) 图(b)的情形所得的平均搜索长度最小。 一般把平均搜索长度达到最小的扩充二叉搜索树称作最优二叉搜索树。 在相等搜索概率的情形下，最优