最优二叉搜索树.ppt

1 最优二叉搜索树 Optimal Binary Search Trees 2 ?1二叉搜索树?2最优二叉搜索树?3最优二叉搜索树问题描述?4最优子结构性质?5递归计算最优值?6算法 3 是一棵空树或者满足以下的性质: 每个结点作为搜索对象,它的关键字是互不相同的。对于树上的所有结点,如果它有左子树左子树,那么左子树上所有结点的关键字都小于该结点的关键字。对于树上的所有结点,如果它有右子树右子树,那么右子树上所有结点的关键字都大于该结点的关键字。 1 二叉搜索树 4 xal wan wil wen wim wul zol yo zom xul yu m xem yon zi 搜索过程:从根结点开始,如果根为空,则搜索不成功;否则使用待搜索值与根结点比较,如果待搜索值等于根结点关键字,则搜索成功返回,如果小于根结点,则向左子树搜索;如果大于根结点,则向右子树搜索。 1 二叉搜索树 5 ?对于一个给定的关键字集合,可能有若干不同的二分检索树?如对保留字的子集 Name : 1 2 3 4 5 for if loop repeat while 的两棵二分检索树为 if for while loop repeat if while loop repeat for ab 考虑 a图和 b图中最坏比较次数和平均比较次数 1 二叉搜索树 6 构造不同的二叉搜索树就有不同的性能特征。二叉搜索树 a在最坏情况下找一个标识符需要 4次比较,而 b表示的二分检索树最坏情况下只需 3次比较。假设只作成功的检索并且检索每个标识符的概率相同,则两棵二分检索树在平均情况下各需要 12/5 和 11/5 次比较。 if for while loop repeat if while loop repeat for ab 1 二叉搜索树 72、最优二叉搜索树?存在的两个问题? 1 在实际中也会遇到不成功检索的情况。? 2 在实际中,不同标识符会有不同的检索概率。?对给定的标识符集合,希望给出构造二分搜索树的方法,使得所构造的二分搜索树具有最优的性能。 2 最优二叉搜索树 8 ?扩充二叉树:当二叉树里出现空的子树时, 就增加新的、特殊的结点——空树叶。对于原来二叉树里度数为 1的分支结点,在它下面增加一个空树叶;对于原来二叉树的树叶,在它下面增加两个空树叶。?扩充二叉树是满二叉树,新增加的空树叶(以下称外部结点)的个数等于原来二叉树的结点(以下称内部结点)个数加 1。在实际中也会遇到不成功检索的情况 2 最优二叉搜索树 9 xal wan wil wen wim wul zol yo zom xul yu m xem yon zi AA代表其值处于 wim 和 wul 之间的可能关键码集合 2 最优二叉搜索树 10 ?设 S={x1, x2, ··· , xn} 是一个有序集合,且 x1, x2, ··· , xn 表示有序集合的二叉搜索树利用二叉树的顶点存储有序集中的元素,而且具有性质: ?存储于每个顶点中的元素 x 大于其左子树中任一个顶点中存储的元素,小于其右子树中任意顶点中存储的元素。二叉树中的叶顶点是形如(xi, xi+1) 的开区间。在二叉搜索树中搜索一个元素 x ?(1) 在二叉树的内部顶点处找到: x = xi ?(2) 在二叉树的叶顶点中确定: x∈ (xi , xi+1) 2 最优二叉搜索树