最优二叉搜索树专业知识课件.ppt

1二叉搜索树2最优二叉搜索树3最优二叉搜索树问题描述4最优子结构性质5递归计算最优值6算法1是一棵空树或者满足以下的性质:每个结点作为搜索对象,它的关键字是互不相同的。对于树上的所有结点,如果它有左子树,那么左子树上所有结点的关键字都小于该结点的关键字。对于树上的所有结点,如果它有右子树,那么右子树上所有结点的关键字都大于该结点的关键字。1二叉搜索树2xalwanwilwenwimwulzolyozomxulyumxemyonzi搜索过程:从根结点开始,如果根为空,则搜索不成功;否则使用待搜索值与根结点比较,如果待搜索值等于根结点关键字,则搜索成功返回,如果小于根结点,则向左子树搜索;如果大于根结点,则向右子树搜索。1二叉搜索树3对于一个给定的关键字集合,可能有若干不同的二分检索树如对保留字的子集Name:12345foriflooprepeatwhile的两棵二分检索树为ifforwhilelooprepeatifwhilelooprepeatforab考虑a图和b图中最坏比较次数和平均比较次数1二叉搜索树4构造不同的二叉搜索树就有不同的性能特征。二叉搜索树a在最坏情况下找一个标识符需要4次比较,而b表示的二分检索树最坏情况下只需3次比较。假设只作成功的检索并且检索每个标识符的概率相同,则两棵二分检索树在平均情况下各需要12/5和11/5次比较。ifforwhilelooprepeatifwhilelooprepeatforab1二叉搜索树5扩充二叉树:当二叉树里出现空的子树时,就增加新的、特殊的结点——空树叶。对于原来二叉树里度数为1的分支结点,在它下面增加一个空树叶;对于原来二叉树的树叶,在它下面增加两个空树叶。扩充二叉树是满二叉树,新增加的空树叶(以下称外部结点)的个数等于原来二叉树的结点(以下称内部结点)个数加1。在实际中也会遇到不成功检索的情况2最优二叉搜索树7xalwanwilwenwimwulzolyozomxulyumxemyonziAA代表其值处于wim和wul之间的可能关键码集合2最优二叉搜索树8设S={x1,x2,···,xn}是一个有序集合,且x1,x2,···,xn表示有序集合的二叉搜索树利用二叉树的顶点存储有序集中的元素,而且具有性质:存储于每个顶点中的元素x大于其左子树中任一个顶点中存储的元素,小于其右子树中任意顶点中存储的元素。二叉树中的叶顶点是形如(xi,xi+1)的开区间。在二叉搜索树中搜索一个元素x(1)在二叉树的内部顶点处找到:x=xi(2)在二叉树的叶顶点中确定:x∈(xi,xi+1)2最优二叉搜索树9在实际中,不同标识符会有不同的检索概率。设Pi是对ai检索的概率。设qi是对满足ai<X<ai+1,0in的标识符X检索的概率,(假定a0=-且an+1=+)。a1Q(0)E0P(1)a2E1Q(1)P(2)aiP(i)ai+1EiQ(i)P(i+1)anP(n)EnQ(n)2最优二叉搜索树10