１ 平衡二叉排序树（ 又称 ＡＶ 树）
１．１ 一棵非空的平衡二叉排序树具有如下性质 （ １） 左子树与右子树的高度之差的绝对值小于 １； （ ２） 左子树和右子树也是平衡二叉排序树。
１．２ 平衡因子
平衡因子是指结点的左子树深度和右子树深度 之差。对于一棵平衡二叉平衡排序树而言， 其所有结 点的平衡因子只能是－ １， ０， １。
如图 ５ 所示是一棵平衡二叉排序树， 当插入一个 机 新结点 １５ 后， 失去平衡， 如图 ６， 经 过 前 面 的 调 整 方 （总
图 １ 所示； ②在左子树的右子树上插入一个新结点
法得到一棵平衡二叉排序树如图 ７ 所示。
第
二
六
收稿日期： ２００７－ ０７－ １０ 修稿日期： ２００７－ ０８－ １７
关键词： 平衡因子； 平衡二叉排序树； 数据结构
０ 引言
Ｎ， 即 ＬＲ 型（ Ｌｅｆｔ，Ｒｉｇｈｔ） ，如图 ２ 所示。
《数据结构》课程是计算机专业的核心课程， 在信 息 科 学 中 具 有 重 要 的 地 位 。学 好 《数 据 结 构 》是 提 高 软 件设计水平的关键性步骤。同时， 《数据结构》是硕士 研究生考试计算机类专业的必考科目， 也是相关专业 的 考 试 科 目 。考 试 大 纲 中 明 确 指 出 要 熟 练 掌 握 手 工 绘 制平衡二叉排序树。
图 １２
图 １３
图１４
详细调整步骤如下： 第一步： 以平衡因子为－ １ 的结点 ４０ 作为根结点 （ 这里有两个平衡因子为－ １ 的结点， 可选择靠近根结 点的那个； 第二步： 平衡因子为－ １ 的结点 ４０ 的左右子树采 用相邻赋予， 即： 把结点 ３０ 给予结点 ２０， 作为其右子 树； 第三步： 以平衡因子为－ ２ 的结点及其子树作为 根结点的左子树， 根结点的右子树则由原平衡因子 为－ １ 的结点的右子树代替。
则： 图 ８ 和图 ９ 调整后恢复平衡的图如图 １０ 和
图 １１。
图５
图６
图７
详细调整步骤如下： ①把平衡因子为 １ 的结点 ２５ 作为根结点 （ 这里 结点 ２０ 的平衡因子也是 １， 依然采取就近原则， 取 ２５ 作为根结点） ； ②平衡因子为 １ 结点 ２５ 其原有的左右子树采用 相邻赋予， 即： 把结点 ３０ 给予结点 ４０， 作为它的左子 树； ③取平衡因子为 ２ 的结点 ４０ 其原有的右子树作 为根结点的右子树； 结点 ２５ 的左边没有结点， 则把其 左子树作为根结点的左子树。
实践与经验
巧绘平衡二叉排序树
潘兆庆 １ ， 周彩根 ２
（ １． 盐城师范学院黄海学院信息科与技术学院， 盐城 ２２４００２； ２．盐城师范学院信息科学与技术学院， 盐城 ２２４００２）
摘 要： 一棵失衡的二叉树会出现根结点平衡因子是 ２ 和－ ２ 的两种失衡情况， 此时需要采取适 当的方法对其进行调整， 使之平衡。结合学习实践， 给出了绘制平衡二叉排序树的巧妙 方法， 辅以实例加以说明。
（总
ｓｔｕｄｙ ｐｒａｃｔｉｃｅ， ｇｉｖｅｓ ａ ｓｋｉｌｌｆｕｌ ｗａｙ ｔｏ ｄｒａｗ ｔｈｅ ｂａｌａｎｃｅ ｂｉｎａｒｙ ｔｒｅｅ， ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｔｈｅ
第
二
ｒｕｌｅｓ ｉｓ ｄｅｍｏｎｓｔｒａｔｅｄ ｂｙ ｓｅｖｅｒａｌ ｅｘａｍｐｌｅｓ．
六
Ｋｅｙｗｏｒｄｓ ： Ｂａｌａｎｃｅ Ｆａｃｔｏｒ； Ｂａｌａｎｃｅ Ｂｉｎａｒｙ Ｔｒｅｅ； Ｄａｔａ Ｓｔｒｕｃｔｕｒｅ
第三步： 插入结点 ｋ； 第四步： 插入结点 ｍ； 第 五 步 ： 对 由 结 点 ｐ，ｋ，ｍ 构 成 的 树 ， 遵 循 根 结 点 平衡因子是 ２ 的情况进行调整； 第六步： 插入结点 ｌ； 第七步： 遵循根结点平衡因子是－ ２ 的情况对第 六步形成的失衡二叉树排序进行调整； 第八步： 插入结点 ｂ； 第九步： 对有结点 ｉ，ｅ，ｂ 构成的树， 遵循根结点平 衡因子是 ２ 的情况进行调整， 得到所要绘制的 ＡＶＬ 树。
２ 失衡二叉排序树
平衡因子为 １ 的结点作为根结点； 第二步： 把平衡因子为 １ 的结点的左右子树采用 相邻赋予， 即若它的左边有结点， 则把左子树给予它 左边的结点， 作为其右子树， 没有则保持。同理， 若它 的右边有结点， 则把的右子树给予它右边的结点， 作 为其左子树， 没有则保持； 第三步： 经第二步后， 以原平衡因子为 ２ 的结点
５ 结语
熟练掌握平衡二叉排序树的生成， 不仅可以提高 算法的有效性， 提高程序的运行效率， 还可以使在竞 争激烈的入学考试中处于有利地位。
参考文献 ［１］耿国华等． 数据结构— ——Ｃ 语言描述． 西安： 西安电子科
技大学出版社， ２００２， ２ ［２］苏仕华． 数据结构与算法． 合肥： 中国科学技术大学出版
则现根结点的左子树或右子树由原平衡因子为 １ 的 现
结点的左子树或右子树替代。
代
图 １ 和图 ２ 调整后恢复平衡的图如图 ３ 和图 ４。 计
当给一棵平衡二叉树的左子树插入一个新结点，
（ ２） 实例解析
算
致使其失去平衡。此时出现两种情况： ①在左子树的 左 子 树 上 插 入 一 个 新 结 点 Ｎ， 即 ＬＬ 型 （ Ｌｅｆｔ，Ｌｅｆｔ） ， 如
现
代
计
算
机
（总
图８
图９
第
二
（ １） 调整方法
六
第一步： 以平衡因子为－ １ 的结点作为根结点；
九
第二步： 把平衡因子为－ １ 的结点的左右子树采
期
）
!" ＭＯ Ｄ Ｅ Ｒ Ｎ Ｃ ＯＭＰ Ｕ Ｔ Ｅ Ｒ ２００７．１０
图 １０
图 １１
（ ２） 实例解析 如图 １２ 所示是一棵平衡二叉排序树， 当插入一 个新结点 ７０ 后， 失去平衡， 如图 １３， 经过上面的调整 方法得到一棵平衡二叉排序树如图 １４ 所示。
作为其左子树， 没有则保持；
第三步： 经第二步后， 以原平衡因子为－ ２ 的结点
及其子树作为根结点的右子树， 以原根结点的左结点
图３
图４
及其子树作为现根结点的左子树。在此过程中， 如果
原平衡因子为－ １ 的结点， 它的左边或右边没有结点，
则现根结点的左子树或右子树由原平衡因子为 １ 的
结点的左子树或右子树替代。
３．２ 根结点平衡因子是－ ２ 的失衡情况
当给一棵平衡二叉树的右子树插入一个新结点 Ｎ， 致使其失去平衡。此时出现两种情况： ①在右子树 的 右 子 数 上 插 入 一 个 新 结 点 Ｎ， 即 ＲＲ 型 （ Ｒｉｇｈｔ， Ｒｉｇｈｔ） ， 如图 ８ 所示；②在右子树的左子树上插入一个 新结点 Ｎ， 即 ＲＬ 型（ Ｒｉｇｈｔ，Ｌｅｆｔ） ，如图 ９ 所示。
实践与经验
４ 综合运用
题 ： 按 下 列 次 序 输 入 关 键 字 ： ｅ，ｉ，ｐ，ｋ，ｍ，ｌ，ｂ，试 画 出 ＡＶＬ 树的构造与调整过程。【山东大学 １９９２ 年硕士研 究生入学试题】
解： 详细解答过程如图：
过程描述： 第二步： 遵循根结点平衡因子是－ ２ 的 情况对第一步形成的失衡二叉排序树进行调整；
社， ２００４， １ ［３］陈守孔等． 算法与数据结构考研试题精析． 北京： 机械工
业出版社， ２００４， １０
Ｄｒａ ｗｉｎｇ Ｂａ ｌａ ｎｃｅ Ｂｉｎａ ｒｙ Ｔｒｅ ｅ
ＰＡＮ Ｚｈａｏ－ ｑｉｎｇ１ ， ＺＨＯＵ Ｃａｉ－ ｇｅｎ２
现
（１． Ｃｏｌｌｅｇｅ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｃｏｌｌｅｇｅ ｏｆ Ｈｕａｎｇｈａｉ， Ｙａｎｃｈｅｎｇ Ｎｏｒｍａｌ Ｃｏｌｌｅｇｅ， Ｙａｎｃｈｅｎｇ ２２４００２；
代
计
２． Ｃｏｌｌｅｇｅ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｙａｎｃｈｅｎｇ Ｎｏｒｍａｌ Ｃｏｌｌｅｇｅ， Ｙａｎｃｈｅｎｇ ２２４００２）
算
机
Ａｂｓ ｔｒａｃｔ： Ｆｏｒ ａ ｂｉｎａｒｙ ｔｒｅｅ ｏｆ ｕｎｂａｌａｎｃｅ， ｔｈｅｒｅ ａｐｐｅａｒｓ ｔｈｅ ｂａｌａｎｃｅ ｆａｃｔｏｒ ｏｆ ｃｒｕｎｏｄｅ ｏｆ ｒｏｏｔ ｉｓ ２ ａｎｄ － ２ ａｎｄ ｓｈｏｕｌｄ ｔａｋｅ ｐｒｏｐｅｒ ｍｅｔｈｏｄ ｔｏ ａｄｊｕｓｔ ｓｏ ａｓ ｔｏ ｍａｋｅ ｉｔ ｂａｌａｎｃｅ． Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ
九
作者简介： 潘兆庆（ １９８６－ ） ， 男， 江苏南京人， 研究方向为计算机免疫、人工智能
期
ＭＯ Ｄ Ｅ Ｒ Ｎ Ｃ ＯＭＰ Ｕ Ｔ Ｅ Ｒ ２００７．１０ !" ）
实践与经验
用相邻赋予， 即若它的左边有结点， 则把左子树给予
它左边的结点， 作为其右子树， 没有则保持。同理， 若
它的右边有结点， 则把的右子树给予它右边的结点，
概念： 当给一棵平衡二叉排序树插入一个结点
及其子树作为根结点的右子树， 以原根结点的左结点
时， 出现绝对值大于 １ 的平衡因子， 此时称平衡二叉
及其子树作为现根结点的左子树。在此过程中， 如果
排序树失去平衡。
原平衡因子为 １ 的结点， 它的左边或右边没有结点，
３ 平衡二叉排序树失衡情况及其调整方法 ３．１ 根结点平衡因子是２ 的失衡情况
九
期
ＭＯ Ｄ Ｅ Ｒ Ｎ Ｃ ＯＭＰ Ｕ Ｔ Ｅ Ｒ ２００７．１０ !" ）