数据结构中平衡二叉树的教学探讨与研究

朱洪浩

（蚌埠学院 计算机科学与技术系，安徽 蚌埠 233000）

数据结构中平衡二叉树的教学探讨与研究

朱洪浩

（蚌埠学院 计算机科学与技术系，安徽 蚌埠 233000）

平衡二叉树是对二叉排序树的一种改进，又被称为AVL树，平衡二叉树的结构较好，可以提高查找运算的速度.本文分析了权威教材和相关论文中平衡二叉树的调整方法，这些方法学生普遍反映理解和掌握较困难.据此，本文依据平衡因子和二叉排序树的特性，设计出一种基于平衡因子和二叉排序树的平衡二叉树的调整方法，该方法易于理解和掌握.

二叉排序树；平衡因子；平衡二叉树

1 引言

数据结构课程是计算机及相关专业的核心课程，是程序设计的重要理论技术基础[1].在动态查找表中，平衡二叉树被广泛的应用，平衡二叉树又称AVL 树,它是由 Adel，son-Vel，skii和 Landis两位数学家于1962年提出并用他们的名字来命名的.平衡二叉树或者是一棵空树，或者是满足下列条件的二叉排序树：二叉排序树的所有结点的平衡因子为-1、0 和 1.所谓平衡因子 BF（Balance Factor）可定义为某结点左子树的深度减去右子树的深度[2].若二叉树中任一个结点的平衡因子的绝对值大于1，则该二叉树就不是平衡二叉树.

平衡二叉树在插入结点和删除结点时候，会使其变得不平衡.为此，需要对二叉排序树进行调整,使之重新变为平衡二叉树.相关教材和论文中关于平衡二叉树的调整方法较难理解，学生难以接受.笔者通过阅读大量的相关资料，并且总结教学经验，提出了一种易于理解和实用的二叉排序树转换成平衡二叉树方法.

2 平衡二叉树调整方法的文献综述

由于平衡二叉树的重要性，以及学生在学习平衡二叉树调整的过程中，普遍反映对用于平衡二叉树调整的四种方法较难理解，算法复杂.为此，许多学者对平衡二叉树的调整进行了大量的研究.

严蔚敏、吴伟民[1]在《数据结构》（C语言版）一书中二叉排序树调整为平衡二叉树采用左旋转（LL）、右旋转（LR）、先左旋转后右旋转（LR）、先右旋转后左旋转（RL）四种旋转方法.

李春葆[2]在《数据结构教程》（第2版）一书中也是采用了LL、LR、RR、RL四种旋转方法.

朱宇、张红彬[3]在《平衡二叉树的选择调整算法》一文中，提出利用“中为根、小为左、大为右”的调整策略，但本质上仍然是利用旋转的思想.

胡云[4]在《快速构建AVL树》一文中采用“将二叉排序树中的数据进行排序,将中点数据作为根,大于中点的数据构成右子树，小于中点的数据构成左子树，然后采用同样的方法分别对左子树和右子树进行调整.”但从作者举出的实例可以看出，该方法与传统方法得到的平衡二叉树并不一致.

杜薇薇[5]等在《基于平衡因子的AVL树设计实现》一文中则从平衡因子出发,并用数学公式进行了验证了插入和删除操作.

刘绍翰[6]等在《一种简化的AVL树的实现方法》一文提出了高度平衡树(HAVL)它是一种新的AVL树的数学描述.

以上文献中虽然提出了较好的调整方法，但在平衡二叉树的调整基本上仍然是采用旋转的方法进行调整，并没有从根本上解决学生的困惑.笔者在教学中发现学生对二叉排序树的建立普遍能熟练掌握，并且平衡二叉树的前提必须是一棵二叉排序树，为此，本文提出了一种利用平衡因子和构建二叉排序树的方法来实现平衡二叉树的调整，从而解决了学生的困惑.

3 平衡二叉树的调整方法

根据平衡二叉树的定义可知，插入和删除结点造成平衡二叉树不平衡的原因是产生2或者-2的平衡因子，其实，调整的方法只需将以平衡因子为2或者-2为根结点的子二叉排序树重新找一个根结点建立新的子二叉排序树.从而使二叉排序树中的平衡因子都为-1、0或者1，即调整成为平衡二叉树.问题的关键是如何找根结点，即序列中的第一个结点，具体方法如下文所示规则.

3.1 插入结点的调整

插入结点时，可以利用规则一、规则二进行：

规则一 某结点的平衡因子为2时，把以该结点为根的树采用中序遍历的方法进行遍历，即得到一个递增的子序列，同时看该结点的左孩子的平衡因子.

（1）若左孩子的平衡因子为-1时，则取该左孩子的右孩子结点，并将其移动到序列的最前面，得到一个新的序列，对该序列构造二叉排序树.

（2）若左孩子的平衡因子为1时，则取该左孩子结点，并将其移动到序列的最前面，得到一个新序列，对该序列构造二叉排序树.

规则二 某结点的平衡因子为-2时，把以该结点为根的树采用中序遍历的方法进行遍历，即得到一个递增的子序列，同时看该结点的右孩子的平衡因子.

（1）若右孩子的平衡因子为-1时，则取该右孩子结点，并将其移动到序列的最前面，得到一个新的序列，对该序列构造二叉排序树.

（2）若右孩子的平衡因子为1时，则取该右孩子的左孩子结点，并将其移动到序列的最前面，得到一个新序列，对该序列构造二叉排序树.

3.2 删除结点的调整

删除结点时，要确定删除的结点是否是叶子结点，具体方法见规则三.

规则三

（1）若删除的是叶子结点，直接删除，并且自底向下查看树中的平衡因子，若发现存在平衡因子为2时，采用规则一进行调整，若平衡因子为-2时，则采用规则二进行调整.

（2）若不是叶子结点，首先按照二叉排序树非叶子结点的删除方法即用该结点左子树的最大值（或者右子树的最小值）代替该结点，然后在从二叉排序树中删去它的最大值（或者最小值），同样，自底向下查看树中的平衡因子，若发现存在平衡因子为2时，采用规则一进行调整，若平衡因子为-2时，则采用规则二进行调整.

4 算法描述

4.1 插入结点的算法

平衡二叉树的插入实现算法步骤：

（1）插入结点L（L总是作为新的叶子结点插入的），插入的方法同一般的二叉排序树插入结点一样.

（2）沿着插入结点L的路线返回，逐层回溯.必要时修改L的祖先的平衡因子，发现平衡因子为2或-2时，则利用规则一、规则二找到结点R.

（3）把该二叉排序树进行中序遍历，得到一递增序列，并把结点R移动到该序列的最前面，然后对新形成的序列构造二叉排序树.同时检查树中其它结点，若发现平衡因子为2或-2的结点，进行调整.重复（2）（3）直到所有的结点都保持平衡为止.

（4）回到（1），继续插入新的结点，直到所有的结点都插入完为止.

实例1：输入关键字序列{16,3,7,11,9,26,18,14,15}，构造一棵平衡二叉树[2].

图1 利用规则一、规则二构造AVL树的过程

4.2 删除结点的算法

平衡二叉树的删除实现算法步骤：

（1）用二叉排序树的删除算法找到并删除结点L.

（2）从被删除结点到根结点逐层向上回溯，必要时修改L的祖先结点的平衡因子，发现平衡因子为2或-2时，则利用规则一、规则二找到结点R.

（3）把该二叉排序树进行中序遍历，得到一递增序列，并把结点R移动到该序列的最前面，然后对新形成的序列构造二叉排序树.

（4）如果调整之后，子树的总高度比调整前降低了，仍然要继续回溯，直到所有结点平衡因子都为-1、0、1时，即都保持平衡为止.

实例2：对实例1生成的AVL树，给出删除结点11,9,14的步骤[2].

图2 删除AVL中结点的过程

5 结束语

平衡二叉树的调整是数据结构教学中的重点和难点，学生在学习的过程中对该部分内容难以理解和接受，为了打破这种局面，作者通过阅读大量的资料，总结了此方法，该方法“只需找到新的根结点，重新构造成二叉排序树”即可，通过教学实践发现，本文采用的方法容易被学生理解和掌握，在教学中得到了良好的效果，得到学生的认可.

〔1〕严蔚敏，吴伟民.数据结构(C 语言版)[M].北京：清华大学出版社，2007.

〔2〕李春葆.数据结构教程（第 2版）.北京：清华大学出版社，2007.

〔3〕朱宇，张红彬.平衡二叉树的选择调整算法[J].中国科学院研究生院学报，2006，23（4）:527-533.

〔4〕胡云.快速构建 AVL树[J].安阳师范学院学报，2007（6）：61-63.

〔5〕杜薇薇，张翼燕，瞿春柳.基于平衡因子的AVL树设计实现[J].计算机技术与发展，2010，20（3）:24-27.

〔6〕刘绍翰，高天行，黄志球.一种简化的AVL树的实现方法 [J].三峡大学学报 (自然科学版)，2011，33（1）:85-87.

TP311.12

A

1673-260X（2012）03-0019-03

安徽省自然科学基金项目（11040606M151）资助