文件名称：平衡事叉搜索树-cis_orcad 本地数据库配置方法
文件大小：5.89MB
文件格式：PDF
更新时间：2024-06-28 07:12:10
数据结构 邓俊辉
第7章 搜索树 §7.3 平衡事叉搜索树 221100 实现这类平衡二叉搜索树的基本构思大致相同：首先适度地放宽平衡性的评判标准，以 扩大平衡树的覆盖范围及其在所有二叉搜索树中所占的比例；然后，按照某一准则对所有可 能的搜索树做等价类划分。这些划分方案的精妙之处在于，不仅保证了每一等价类都包含一 棵（适度平衡意义下的）平衡搜索树，而且更重要地，经动态修改之后不再平衡的任一搜索 树，都可以足够低廉的时空成本，经等价变换之后恢复为与之等价的一棵平衡搜索树。 7.3.3 等价二叉搜索树 最直接的等价关系由中序遍历确定：二叉树相互等价，当且仅当其中序遍历序列相同。 图7.9 由同一组兯11个节点组成，相于等价癿两棵事叉搜索树 （事者在拓扑上癿差异，由阴影矩形和阴影囿形分删标出） 以图7.9中的一对二叉搜索树为例，二者均由同一组节点组成。尽管节点之间的拓扑联 接关系并不完全一致，但因其各自的中序遍历序列完全相同，故二者属于同一等价类。 由该图也不难看出，虽然等价二叉搜索树中各节点的垂直高度可能有所不同，但水平次 序完全一致。这一特点可概括为“上下可变，左右不乱”，它也是以下等价变换的基本特性。 7.3.4 等价变换与局部调整 尽管按照以上等价关系，任何一棵二叉搜索树都与某完全二叉树等价，但为了把失衡二 叉搜索树转换为等价的完全二叉树，将不得不花费线性量级的时间。现实可行的策略是，通 过少量的局部调整，使之尽快恢复平衡。最常用的此类局部调整，就是围绕特定节点的旋转。 zig旋转和zag旋转 如图7.10(a)，设节点c是v的左孩子，X和Y分别是c 的左、右子树，Z为v的右子树（可能为空）。 所谓围绕v的zig旋转操作（记作zig(v)），即重新 调整这两个节点与三棵子树的联接关系：v作为c的右孩 子，X作为c的左子树，Y和Z分别作为v的左、右子树。调 整后的效果如图(b)。 可见，尽管局部联接关系以及子树根均有变化，但中 序遍历子序列依然是{..., X, c, Y, v, Z, ...}，故 zig旋转属于等价变换。 图7.10 zig(v)：顸时针旋转操作