PATRICIA的特点 每个内部结点都代表一个位的比较,必 然产生两个子结点 所以它是一个满二叉树 进行一次检索,最多只需要关键码位数 次的比较即可 北京大学信息学院 版权所有,转载或翻印必究 Page 26
北京大学信息学院 ©版权所有，转载或翻印必究 Page 26 PATRICIA的特点 ◼ 每个内部结点都代表一个位的比较，必 然产生两个子结点 ◼ 所以它是一个满二叉树 ◼ 进行一次检索，最多只需要关键码位数 次的比较即可
122二叉树结构的改进 平衡的二叉搜索树、伸展树和最 佳二叉排序树,它们都是对二叉 树的结构或者操作规则做部分的 改进以使树保持在一种类似于平 衡的状态,从而达到较好的效率 北京大学信息学院 版权所有,转载或翻印必究 Page 27
北京大学信息学院 ©版权所有，转载或翻印必究 Page 27 12.2二叉树结构的改进 ◼ 平衡的二叉搜索树、伸展树和最 佳二叉排序树，它们都是对二叉 树的结构或者操作规则做部分的 改进以使树保持在一种类似于平 衡的状态，从而达到较好的效率
12.21最佳二叉搜索树 ■根据前面章节的二叉树介绍我们知道对应于关键码集合K:K={xl wan,wil, zol, yo, xul, yum, wen, wim, zi, yon, xem, wul, zom/B= 叉排序树 wa l wil yu ●zm wen yum y 北京大学信息学院 版权所有,转载或翻印必究 Page 28
北京大学信息学院 ©版权所有，转载或翻印必究 Page 28 12.2.1最佳二叉搜索树 ◼ 根据前面章节的二叉树介绍我们知道对应于关键码集合K:K={xal, wan, wil, zol, yo, xul, yum, wen, wim, zi, yon, xem, wul, zom}的二 叉排序树
二叉搜索树的多样性 同一个关键码集合,其关键码插入二叉搜索树 的次序不同,就构成不同的二叉搜索树。 包括n个关键码的集合中,关键码可以有n!种 不同的排列法,因此可以构成n!个二叉搜索树 (其中有相同的) ■可以用检索效率来衡量二叉搜索树 北京大学信息学院 版权所有,转载或翻印必究 Page 29
北京大学信息学院 ©版权所有，转载或翻印必究 Page 29 二叉搜索树的多样性 ◼ 同一个关键码集合，其关键码插入二叉搜索树 的次序不同，就构成不同的二叉搜索树。 ◼ 包括n个关键码的集合中，关键码可以有n!种 不同的排列法，因此可以构成n!个二叉搜索树 (其中有相同的) ◼ 可以用检索效率来衡量二叉搜索树
■如果只计算不同的搜索树,则排列{2,1,3}的 顺序插入关键码与按照排列{2,3,1}的顺序插 入所构成的二叉搜索树完全相同 这种非前序排列的序列,总是可以找到与其相 对应的一个合法前序排列 这m种排列中,只有c2n-C2=n1C2 n+ 就是说n个结点可以构造c,称为 n Catalan函数 北京大学信息学院 版权所有,转载或翻印必究 Page 30
北京大学信息学院 ©版权所有，转载或翻印必究 Page 30 ◼ 如果只计算不同的搜索树，则排列{2，1，3}的 顺序插入关键码与按照排列{2，3，1}的顺序插 入所构成的二叉搜索树完全相同 ◼ 这种非前序排列的序列，总是可以找到与其相 对应的一个合法前序排列 ◼ 这n!种排列中， 只有 ◼ 就是说n个结点可以构造 称为 Catalan函数 1 2 2 2 1 1 n n n n n n n c c c − − = + 2 1 1 n n n c +