数据结构第六章 平衡树.doc

1、6.5 平 衡 二 叉 树平 衡 二 叉 树 （ balanced binary tree） 是 对 二 叉 搜 索 树 的 一 种 改 进 。 二 叉 搜 索树 有 一 个 缺 点 ， 那 就 是 树 的 结 构 事 先 无 法 预 料 ， 随 意 性 很 大 ， 它 只 与 结 点 的值 和 插 入 次 序 有 关 ， 往 往 得 到 的 是 一 棵 很 不“平 衡 ”的 二 叉 树 。 二 叉 搜 索 树 与 理想 平 衡 树 相 差 越 远 ， 树 的 高 度 就 越 高 ， 其 运 算 时 间 就 越 长 ， 在 最 坏 的 情 况 下 ，就 是 对 单 链 表 进 行 运 算 的

2、时 间 ， 其 时 间 复 杂 度 由O( n)变 为 O(n)， 从 而 部 分 或2log全 部 地 丧 失 了 利 用 二 叉 搜 索 树 组 织 数 据 的 优 点 。 为 了 克 服 二 叉 搜 索 树 的 这 个缺 点 ， 需 要 在 插 入 和 删 除 结 点 时 对 树 的 结 构 进 行 必 要 的 调 整 ， 使 二 叉 搜 索 树始 终 处 于 一 种 平 衡 的 状 态 ， 即 始 终 成 为 一 种平 衡 二 叉 树 (balanced binary tree)， 简 称 平衡 树 。 当 然 它 不 是 理 想 平 衡 树 ， 因 为 那 将 使 调 整 操 作 更

3、 为 复 杂 ， 使 调 整 带 来的 好 处 得 不 偿 失 。本 节 将 首 先 讨 论 平 衡 树 的 定 义 和 调 整 操 作 ， 然 后 讨 论B_树 的 定 义 以 及 查 找 、插 入 和 删 除 等 运 算 。6.5.1平 衡 二 叉 树 的 定 义平 衡 二 叉 树 简 称 平 衡 树 是 由 阿 德 尔 森 一 维 尔 斯 基 和 兰 迪 斯(Adelson-Velskii and Landis)于 1962 年 首 先 提 出 的 ， 所 以 又 称 为AVL树 。 平 衡 树 的 定 义 是 ： 若 一 棵二 叉 树 中 每 个 结 点 的 左 、 右 子 树 的 高

4、 度 至 多 相 差 ， 则 称 此 树 为平 衡 树 。 我 们 把 二 叉 树 中 每 个 结 点 的 左 子 树 高 度 减 去 右 子 树 的 高 度 定 义 为 该结 点 的 平 衡 因 子 (balance factor)， 因 此 ， 平 衡 树 中 每 个 结 点 的 平 衡 因 子 只 能 是1,0 或 -1。 图 7-6(a)是 一 棵 平 衡 树 ， 图 7-6(b)和 图 7-6(c)分 别 是 一 棵 非 平 衡 树 ， 每 个 结 点 的上 方 所 标 数 字 为 该 结 点 的 平 衡 因 子 。虽 然 平 衡 树 的 平 衡 性 比 理 想 平 衡 树 要 差

5、一 些 ， 但 理 论 上 已 经 证 明 ： 具 有n 个 结点 的 平 衡 树 的 高 度 在 任 何 情 况 下决 不 会 比 具 有 相 同 结 点 数 的 理 想 平 衡 树 高 出45%以 上 。 因 此 ， 在 平 衡 树 上 进 行 查 找 运 算 虽 比 理 想 平 衡 树 要 慢 一 些 ， 但 通常 比 任 意 生 成 的 二 叉 搜 索 树 快 得 多 ， 当 然 ， 其 时 间 复 杂 度 的 数 量 级 表 示 仍 为O( n).2log1 2 36 -1 15-1 -1 -2 20 -1 48 0 10 -2320 0 0 016 2 30 0 650 5 012

6、 1 600 0 0 28 0 450 25(a)平 衡 (b) 非 平 衡 (c)非 平 衡图 7-6 带 平 衡 因 子 的 二 叉 树当 向 一 棵 平 衡 树 插 入 一 个 新 结 点 时 ， 若 插 入 后 ， 某 些 结 点 的 左 、 右 子 树的 高 度 不 变 ， 则 就 不 会 影 响 这 些 结 点 的 平 衡 因 子 ， 因 而 也 不 会 因 为 这 些 造 成不 平 衡 ； 若 插 入 后 某 些 结 点 的 左 子 树 高 度 增 加 （ 右 子 树 高 度 增 加 的 情 况与 之 类 似 ）， 则 就 影 响 了 这 些 结 点 的 平 衡 因 子 ， 具

7、体 又 分 为 三 种 情 况 ：(1)若 插 入 前 一 部 分 结 点 的 左 子 树 高 度 为h 与 右 子 树 的 高 度 h 相LR等 ， 即 平 衡 因 子 为 ， 则 插 入 后 将 使 平 衡 因 子 变 为 ， 但 仍 符 合平 衡 的 条 件 ， 不 必 对 它 们 加 以 调 整 ；(2)若 插 入 前 一 部 分 结 点 的 h 小 于 h ， 即 平 衡 因 子 为 -1， 则 插 入LR后 将 使 平 衡 因 子 变 为 ， 平 衡 更 加 改 善 ， 不 必 对 它 们 进 行 调 整 ；(3)若 插 入 前 一 部 分 结 点 的 h 大 于 h ， 即 平

8、衡 因 子 为 ， 则 插入 后 将 使 平 衡 因 子 变 为 ， 破 坏 了 平 衡 树 的 限 制 条 件 ， 需 对 它 们加 以 调 整 ， 使 整 个 二 叉 搜 索 树 恢 复 为 平 衡 树 。若 插 入 后 ， 某 些 结 点 的 右 子 树 高 度 增 加 ， 则 也 分 为 相 应 的 三 种 情 况 ， 对 于 第(1)种 情 况 ， 平 衡 因 子 将 由 变 为-1， 不 必 进 行 调 整 ； 对 于 第(2)种 情 况 是 平 衡 因 子 由-1变 为 -2， 则 必 须 对 它 们 进 行 调 整 ； 对 于 第(3)种 情 况 是 平 衡 因 子 由 变 为

9、 ， 平 衡更 加 改 善 ， 也 不 必 进 行 调 整 。假 定 向 平 衡 树 中 插 入 一 个 结 点 后 破 坏 了 其 平 衡 性 ， 则 首 先 要 找 出 唯 一 一棵 最 小 不 平 衡 子 树 ， 然 后 再 调 整 这 个 子 树 中 有 关 结 点 之 间 的 链 接 关 系 ， 使 之成 为 新 的 平 衡 子 树 。 当 然 ， 调 整 后 该 子 树 的 二 叉 搜 索 树 性 质 要 不 变 ， 即 调 整前 后 得 到 的 中 序 序 列 要 完 全 相 同 。 稍 后 便 知 ， 最 小 不 平 衡 子 树 调 整 为 平 衡 子树 后 ， 原 有 其 他

10、 所 有 不 平 衡 子 树 无 需 调 整 ， 整 个 二 叉 搜 索 树 就 又 成 为 一 棵 平 衡 树 。所 谓 最 小 不 平 衡 子 树 是 指 以 离 插 入 结 点 最 近 ， 且 平 衡 因 子 绝 对值 大 于 的 结 点 作 为 根 的 子 树。 如 在 图 7-6(b)中 ， 以 值 为 30 的 结 点 作 根 的 子树 是 该 树 的 最 小 不 平 衡 子 树 ， 分 别 以20 和 36 作 为 根 的 不 平 衡 子 树 不 是 最 小 不 平衡 子 树 ； 在 图 7-6(c)中 ， 以 值 为 32 的 结 点 作 根 的 子 树 是 该 树 的 最 小

11、 不 平 衡 子 树 ，当 然 它 也 是 唯 一 一 棵 不 平 衡 子 树 。 为 了 便 于 讨 论 ， 不 妨 设 最 小 不 平 衡 子 树 的根 结 点 用 表 示 ， 则 调 整 该 子 树 的 操 作 可 归 纳 为 下 列 四 种 情 况 ：(1)LL 型 调 整 操 作它 是 因 在 结 点 的 左(left)孩 子 （ 假 定 用 B 表 示 ） 的 左 (left)子 树 上 插 入 结 点 ，使 得 A 结 点 的 平 衡 因 子 由 1 变 为 2 而 引 起 的 不 平 衡 所 进 行 的 调 整 操 作 。 调 整 过程 如 图 7-7 所 示 ， 图 中 用

12、长 方 框 表 示 子 树 ， 用 长 方 框 的 高 度 表 示 子 树 的 高 度 ，用 带 阴 影 的 小 方 框 表 示 被 插 入 的 结 点 。 图7-7(a)为 插 入 前 的 平 衡 子 树 ， 、 和a的 子 树 高 度 均 为 h(h 0， 若 h=0， 则 它 们 均 为 空 树 )， A 结 点 和 B 结 点 的 平 衡 因子 分 别 为 1 和 0。 图 7-7(b)为 在 B 的 左 子 树 上 插 入 一 个 新 结 点 ， 以 A 为 根 的 子 树成 为 最 小 不 平 衡 子 树 的 情 况 。 图7-7(c)为 调 整 后 成 为 新 的 平 衡 平 衡

13、 子 树 的 情 况 ，调 整 规 则 是 ： 将 A 的 左 孩 子 B 向 右 旋 转 代 替 成 为 根 结 点 ， 将A 结 点 向 右 下 旋 转成 为 B 的 右 子 树 的 根 结 点 ， 而 B 的 原 右 子 树 则 作 为 结 点 的 左 子 树 。 此 调 整过 程 需 要 修 改 三 个 指 针 ， 如 图7-7(c)中 的 箭 头 所 示 ， 一 是 将 原 指 向 结 点 的 指 针修 改 为 指 向 结 点 ， 二 是 将 孤 右 指 针 修 改 为 指 向 结 点 ， 三 是 将 的 左 指 针修 改 为 指 向 的 原 右 子 树 的 根 结 点 ； 另 外

14、， 还 需 要 修 改 和 结 点 的 平 衡 因子 ， 应 均 被 置 为 0。从 图 7-7 可 以 看 出 ， 调 整 后 对 应 的 中 序 序 列 相 同 ， 即 为BA， 所 以 经 调整 后 仍 保 持 了 二 叉 搜 索 树 的 性 质 不 变 。1 50 2 50 0 450 45 0 60 1 45 0 60 1 30 0 500 30 0 48 0 30 0 48 0 20 0 48 0 600 20(d)插 入 前 (e)插 入 20 后 (f)调 整 后 1 2 0A A B0 1 0B B A h h+1 插 入 前 , , 为 h 中 序 为 BA(a)插 入 前

15、 (b)插 入 后 (c)调 整 后1 10 2 10 1 10 1 9 0 12 2 9 0 12 0 6 0 12 0 6 1 6 0 3 0 9 0 3(a)插 入 前 (b)插 入 3 后 (c)调 整 后1 50 2 50 0 450 45 0 60 1 45 0 60 1 30 0 500 30 0 48 0 30 0 48 0 20 0 48 0600 20(d)插 入 前 (e)插 入 20 后 (f)调 整 后 图 7-8 LL 调 整 实 例图 7-8 是 LL 型 调 整 的 两 个 实 例 ， 其 中 图7-8 中 的 (a)、 (b)、 (c)为 一 例 ， 此 处

16、A结 点 为 9， B 结 点 为 6， 、 、 均 为 空 树 ； 图 7-8 的 (d)、 (e)、 (f)为 另 一 例 ， 此 处aA 结 点 为 50， B 结 点 为 45， 、 、 分 别 为 只 含 有 一 个 结 点 30、 48、 60 的 子 树 。(2)RR 型 调 整 操 作它 是 因 在 A 结 点 的 右 (Right)孩 子 （ 假 定 用 B 表 示 ） 的 右 (Right)子 树 上 插 入 结 点 ，使 得 A 结 点 的 平 衡 因 子 由 -1 变 为 -2 而 引 起 的 不 平 衡 所 进 行 的 调 整 操 作 。 调整 过 程 如图 7-9

17、所 示 。 图 7-9(a)为 插 入 前 的 平 衡 子 树 ， 、 、 子 树 的 高 度 相 同 ， 均 为 h(ha0)， A 结 点 和 B 结 点 的 平 衡 因 子 分 别 为-1 和 0； 图 7-9(b)为 在 B 结 点 的 右 子 树 上 插 放 一 个 新 结 点 ， 使 以 A 根 的 子 树 成 为 最 小 不 平 衡 子 树 的 情 况 ； 图7-9(c)为 调 整 后重 新 恢 复 平 衡 的 情 况 。 调 整 是 ： 将A 的 右 孩 子 B 向 左 上-1 -2 0A A B0 -1 0 h B B A h h+1 插 入 前 , , 为 h 中 序 为

18、AB(a)插 入 前 (b)插 入 后 (c)调 整 后7-9 RR 型 调 整 操 作 示 意 图旋 转 代 替 A 成 为 根 结 点 ， 将 A 结 点 向 左 下 旋 转 成 为 B 的 左 子 树 的 根 结 点 ， 而B 的 原 左 子 树 则 作 为 A 结 点 的 右 子 树 。 此 调 整 过 程 同LL 型 调 整 过 程 对 称 ， 要修 改 的 三 个 指 针 如 图 7-9(c)中 的 箭 头 所 示 。 同 样 ， 进 行 RR 型 调 整 前 后 ， 仍 保 持 着二 叉 搜 索 树 的 性 质 不 变 。(3)LR 型 调 整 操 作它 是 因 在 A 结 点

19、的 左 (Left)孩 子 （ 假 定 用 B 表 示 ） 的 右 (Right)子 树 上 插 入 结 点 ，使 得 A 结 点 的 平 衡 因 子 由 1 变 为 2 而 引 起 的 不 平 衡 所 进 行 的 调 整 操 作 。 调 整 过程 如 图 7-10 所 示 。 图 7-10(a)为 插 入 前 的 平 衡 子 树 ， 和 子 树 的 高 度 均 为 h(h 0)，和 子 树 的 高 度 均 为 h+1， 尤 其 是 当 和 子 树 为 空 树 时 ， 则 B 结 点 的 右 子 树a也 同 时 为 空 ， 此 时 C 结 点 将 是 被 插 入 的 新 结 点 ； 插 入 前

20、 结 点 和 结 点 的 平 衡因 子 分 别 为 和 ， 若 存 在 ， 则 结 点 的 平 衡 因 子 为 。 图7-10(b)为 在 B 结 点 的右 子 树 上 插 入 一 个 新 结 点 （ 当B 的 右 子 树 为 空 时 ， 则 为 C 结 点 ， 否 则 为 C 的 左 子 树或 右 子 树 上 带 阴 影 的 结 点 ， 图 中 给 出 在 左 子 树 上 插 入 的 情 况 ， 若 在 右 子 树 上 插入 ， 情 况 类 似 ）， 使 得 以 A 为 根 的 子 树 成 为 最 小 不 平 衡 子 树 的 情 况 ， 此 处A 结 点 和 B结 点 的 平 衡 因 子 是

21、 按 相 反 方 向 变 化 的 ， 而 不 像 前 两 种 操 作 那 样 ， 都 是 按 同 一方 向 变 化 的 。 图 7-10(c)为 调 整 后 的 情 况 ， 调 整 规 则 是 ： 将A 的 左 孩 子 的 右 子 树 的根 结 点 C 提 升 到 A 结 点 的 位 置 ； 将 B 结 点 作 为 C 的 左 子 树 的 根 结 点 ， 而 C 结 点 的 原左 子 树 则 作 为 B 结 点 的 右 子 树 ； 将 A 结 点 作 为 C 的 右 子 树 的 根 结 点 ， 而 C 结 点的 右 子 树 则 作 为 A 结 点 的 左 子 树 。 此 调 整 过 程 比 前

22、 两 种 情 况 要 复 杂 ， 需 修 改五 个 指针 ， 如 图 7-10(c)中 的 箭 头 所 示 。1 2 0A A C0 -1 0 1B 0 B 1 B AC C h+1 h h+1 插 入 前 , 为 h+1 , 为 h 中 序 为 BCA(a)插 入 前 (b)插 入 后 (c)调 整 后图 7-10 LR 型 调 整 操 作 示 意 图从 图 7-10 可 以 看 出 ， 调 整 前 后 对 应 的 中 序 序 列 相 同 ， 即 为 ， 只 是 链 接 次序 不 同 罢 了 ， 但 没 有 影 响 其 二 叉 搜 索 树 的 性 质 。图 7-11 是 LR 型 调 整 操

23、 作 的 两 个 实 例 ， 其 中 图7-11 中 的 (a)、 7-11 中 的 (b)、 7-11中 的 (c)为 一 例 ， 此 处 A 结 点 为 9， B 结 点 为 3， C 结 点 为 6， 它 是 新 插 入 的 结 点 ，、 、 、 均 为 空 树 ； 图 7-11 中 的 (d)、 7-11 中 的 (e)、 7-11 中 的 (f)为 a1 9 2 9 0 6 -1 560 3 -1 3 0 3 0 9 1 34 1 850 6 0 20 074 0 92 0 65 080(a) (b)插 入 6 后 (c)调 整 后 (d)插 入 前-256 -1 561 34 2

24、85 1 34 0 800 20 -174 092 0 20 0 74 -1 850 65 180 0 65 078 0 920 78 (e)插 入 78 后 (f )调 整 后图 7-11 LR 型 调 整 实 例1 2 0A A C0 -1 0 1B 0 B 1 B AC C h+1 h h+1 插 入 前 , 为 h+1 , 为 h 中 序 为 BCA(a)插 入 前 (b)插 入 后 (c)调 整 后图 7-10 LR 型 调 整 操 作 示 意 图另 一 例 ， 此 处 A 结 点 为 85， B 结 点 为 74， C 结 点 为 80, 和 子 树 分 别 为 65 和a92，

25、和 均 为 空 。-1 -2 0A A C0 1 1 0h+1 0 B -1 B A BC C h h+1插 入 前 , 为 h+1 , 为 h 中 序 为 ACB图 7-12 RL 型 调 整 操 作 示 意 图它 是 因 在 A 结 点 的 右 (Right)孩 子 的 左 (Left)子 树 上 插 入 结 点 ， 使 得 A 结 点 的 平衡 因 子 由 -1 变 为 -2 而 引 起 的 不 平 衡 所 进 行 的 调 整 操 作 。 调 整 过 程 如 图7-12 所 示 ， 它同 LR 型 调 整 过 程 对 称 ， 请 读 者 自 行 分 析 。在 上 述 每 一 种 调 整

26、操 作 中 ， 以A 为 根 的 最 小 不 平 衡 子 树 的 高 度 在 插 入 结 点前 和 调 整 后 相 同 ， 所 以 对 除 此 子 树 之 外 的 其 余 所 有 结 点 的 平 衡 性 不 会 产 生 影响 ， 即 原 有 的 平 衡 因 子 不 变 ， 故 按 照 上 述 方 法 将 最 小 不 平 衡 子 树 调 整 为 平 衡子 树 后 ， 整 个 二 叉 搜 索 树 就 成 了 一 棵 新 的 平 衡 树 。下 面 假 定 用 一 组 关 键 字 为(46,15,20,35,28,58,18,50,54)生 成 一 棵 平 衡 的 二 叉 搜 索树 ， 则 生 成 过

27、 程 如 图 7-13 所 示 。46 46 2 20 2015 15 46 15 462 20 35(a) (b) (c)LR 型 调 整 28 (d)20 2 35 3515 35 20 46 20 46 -228 46 15 28 58 15 28 5858 18 50(e)LL 型 调 整 (f)RR 型 调 整 (g) 35 3520 50 20 5015 28 46 58 15 28 46 5818 18 54(h)RL 型 调 整 (i) 图 7-13 建 立 二 叉 平 衡 树 实 例在 二 叉 搜 索 树 的 插 入 和 删 除 运 算 中 ， 采 用 平 衡 树 优 点 是

28、 ： 使 树 的 结 构较 好 ， 从 而 提 高 查 找 运 算 的 速 度 ； 缺 点 是 ： 使 插 入 和 删 除 变 得 复 杂 化 ， 从 而降 低 它 们 的 运 算 速 度 ， 这 是 因 为 ， 在 每 次 运 算 中 ， 不 仅 要 进 行 插 入 和 删 除 结点 ， 而 且 要 检 查 是 否 存 在 有 最 小 不 平 衡 子 树 （ 实 验 表 明 ， 每 两 次 插 入 或 五 次删 除 都 要 平 均 出 现 一 次 不 平 衡 ）， 若 存 在 ， 则 需 要 对 最 小 不 平 衡 子 树 中 有 关 指 针进 行 修 改 。 因 此 ， 采 用 平 衡 树 ， 适 合 于 那 种 二 叉 搜 索 树 一 经 建 立 就 很 少 进 行插 入 和 删 除 运 算 ， 而 主 要 是 查 找 的 应 用 场 合 。