论文部分内容阅读
摘要 ：
本文根据平衡二叉树的构造原理，提出了利用平衡二叉树进行内部排序的思想，据此完成了对应的算法设计，并通过典型实例进行验证和效率分析。
关键词：平衡二叉树 内部排序
Analysis and Design for Internal Sort Algorithm
Based on AVL tree
ZOU Yong-lin TANG Xiao-yang
（school of computer science and engineering，
Changshu Institute of Technology， 215500）
Abstract
According to the principle of AVL tree constructing， the ideal of sorting by using the AVL tree was developed and the algorithm was designed and implemented in this paper. Finally， the correctness and the efficiency for this algorithm were validated and analysed through the example.
Keywords
AVL tree， internal sort
【中图分类号】G642
1.引言
在数据结构课程教学的理论和实践中，有关内部排序的常用方法，一般将它们分为五大类[1][2][3]：插入、交换、选择、归并和基数排序；并且，大多采用顺序表或链表（队）结构讨论各种算法的具体实现过程。
实际上，并不是所有的内部排序算法都必须使用线性表对应的存储结构来描述。不妨换一种思路，二叉排序树（BST树）和平衡二叉树（AVL树）作为动态查找表结构，它们具有一个基本特点，就是进行中序遍历可以得到一个按结点关键字值递增有序的序列；并且对于平衡二叉树而言，进行一次中序遍历的过程，其时间复杂度为O（log2n）。因此，利用构造平衡二叉树的方法，同样可以实现对一个无序序列进行排序的目的。
2.构造平衡二叉树的基本过程
由平衡二叉树的原理可知，将一个无序序列构造成一棵平衡二叉树时，为了确保其平均查找长度与树的深度相当，在每次插入一个新结点时，需要判断是否失去平衡，从而决定是否需要进行平衡处理以及如何进行平衡处理。
如果一棵平衡二叉树，由于插入一个新结点导致失去平衡，则重新恢复平衡的调整方法有4种，分别是：单向右旋、单向左旋、先左后右和先右后左。具体过程是：首先找到最小不平衡子树，根据其根的平衡因子的值和对应的形态，选择采用不同的方法来恢复其平衡性。
3. 算法设计
根据上述原理，可选择二叉链表存储结构，设计构造平衡二叉树的算法。为了实现待排序关键字中可能存在重复关键字的情形，可对平衡二叉树的定义稍作修改，允许在平衡二叉树中存在值相同的结点；同时，为了确保其稳定性，约定将后续的值相同的关键字以其右子树中的新结点插入。
算法主要代码如下：
#define LH 1 //左高
#define EH 0 //等高
#define RH -1 //右高
#define Num 20
#define true 1
#define false 0
int taller；
typedef struct BSTnode //平衡二叉树的结点结构
{
int data； //关键字
int bf； //平衡因子
struct BSTnode *lc，*rc； //左右指针
}BSTnode；
int InsrtAVL（BSTnode *T，BSTnode *newNode，BSTnode **Tr，int taller）
{ //在平衡二叉树中插入一个新元素
if （newNode->datadata） //在T的左子树中搜索插入
{
if （T->lc==NULL） //T的左子树为空树，直接插入
{
taller=true； T->lc=newNode；
}
else //非空，找到插入点再插入
InsrtAVL（T->lc，newNode，&（T->lc），taller）；
if （taller） //判断平衡性
switch （T->bf）
{
case LH： //进行左平衡处理
LeftBalance（T，Tr）； taller=false； break；
case EH：
T->bf=LH； taller=true； break；
case RH：
T->bf=EH； taller=false； break；
}
}
else //在T的右子树中搜索插入
{
if （T->rc==NULL） //T的右子树为空树，直接插入
{
taller=true； T->rc=newNode； }
else //非空，找到插入点再插入
InsrtAVL（T->rc，newNode，&（T->rc），taller）；
if （taller） //判断平衡性
switch （T->bf）
{
case LH：
T->bf=EH； taller=false； break；
case EH：
T->bf=RH； taller=true； break；
case RH： //进行右平衡处理
RightBalance（T，Tr）； taller=false； break；
}
}
return 1；
}
void LeftBalance（BSTnode *T，BSTnode **Tr） //左平衡处理
{
BSTnode * B_node，*C_node；
B_node=T->lc；
switch （B_node->bf）
{
case LH： //单向右旋
T->bf=B_node->bf=EH； R_Rotate（T，Tr）； break；
case RH：
C_node=B_node->rc；
switch （C_node->bf）
{
case LH：
T->bf=RH； B_node->bf=EH； break；
case EH：
T->bf=B_node->bf=EH； break；
case RH：
T->bf=EH； B_node->bf=LH； break；
}
C_node->bf=EH；
L_Rotate（B_node，&（T->lc））； //先左旋后右旋
R_Rotate（T，Tr）；
}
}
void RightBalance（BSTnode *T，BSTnode **Tr） //右平衡处理
{
BSTnode * C_node，*B_node；
B_node=T->rc；
switch （B_node->bf）
{
case RH： //单向左旋
T->bf=B_node->bf=EH； L_Rotate（T，Tr）； break；
case LH：
C_node=B_node->lc；
switch （C_node->bf）
{
case RH：
T->bf=LH； B_node->bf=EH； break；
case EH：
T->bf=B_node->bf=EH； break；
case LH：
T->bf=EH； B_node->bf=RH； break；
}
C_node->bf=EH；
R_Rotate（B_node，&（T->rc））； //先右旋后左旋
L_Rotate（T，Tr）；
}
}
void R_Rotate（BSTnode *P，BSTnode **Tr） //右旋
{
BSTnode *lch；
lch=P->lc；
P->lc=lch->rc；
lch->rc=P；
P=lch；
*Tr=P；
}
void L_Rotate（BSTnode *P，BSTnode **Tr） //左旋
{
BSTnode * rch；
rch=P->rc；
P->rc=rch->lc；
rch->lc=P；
P=rch；
*Tr=P；
}
int MidOrder（BSTnode *T） //中序遍历平衡二叉树
{
int l，r；
if （！T） return 0；
l=MidOrder（T->lc）；
printf（"%d，"，T->data）；
r=MidOrder（T->rc）；
return l+r+1；
}
int main（）
{
int n=0，x，i，len；
int datas[Num]；
BSTnode *newNode；
while（scanf（"%d"，&x）==1） //输入待排序关键字序列
{datas[n]=x；n++；}
len=n；
printf（"Init datas：＼n"）； //第一个关键字作为根
printf（"%d， "，datas[0]）；
newNode=（BSTnode *）malloc（sizeof（BSTnode））； newNode->data=datas[0]；
newNode->lc=NULL；
newNode->rc=NULL；
newNode->bf=EH；
Root=newNode；
for （n=1；n {
printf（"＼nInsert：%d， "，datas[n]）； //构造新结点
taller=true；
newNode=（BSTnode*）malloc（sizeof（BSTnode））；
newNode->data=datas[n]；
newNode->lc=NULL；
newNode->rc=NULL；
newNode->bf=EH；
i=InsrtAVL（Root，newNode，&Root，taller）； //插入
}
printf（"＼nMid_order：＼n"）； //中序遍历输出排序结果
MidOrder（Root）；
return 0；
}
4.算法分析
4.1排序结果与平衡二叉树的状态变化
假设一个给定的待排序序列，包含12个关键字，初始形态如下：
int datas[Num]={20，12，6，28，16，36，32，10，2，30，8，32}；
采用上述算法进行排序，排序过程和平衡二叉树的状态变化如图1所示。
上述过程和结果符合平衡二叉树构造的原理，结果完全正确。
4.2算法分析
采用构造平衡二叉树的方法进行排序，其排序思想非常简单，只要根据给定的待排序关键字序列，从无到有依次将每个关键字正确插入平衡二叉树即可。待所有待排序关键字插入完成后，最终进行一次中序遍历，就可得到正确的排序结果。整个算法的关键在于完成平衡二叉树的构造。
对于上述算法，从时间需求上看，由于在一棵包含n个结点的平衡二叉树中插入一个新结点时，由其平衡性，查找插入位置需要进行的关键字比较的个数不超过平衡二叉树的深度，故插入操作的时间复杂度为O（log2n），整个排序过程共需要插入n个关键字，因此，算法的时间效率均为O（nlog2n）；从空间需求分析，除了需要在排序过程中动态申请n个平衡二叉树结点和少量搜索指针外，不再需要额外的存储空间，因而存储空间的需求也低。另外，根据本文对平衡二叉树定义的修改约定，上述算法是一个稳定的排序算法。
图1平衡二叉树的状态变化和排序结果
5.结语
以上根据平衡二叉树的概念和基本特性，讨论了借助构造平衡二叉树的方法进行内部排序的算法设计，并利用一个典型实例对该算法进行了验证；最后，对算法的时间效率、空间需求和稳定性作了分析和讨论，得到了正确的结果。
本文通过将动态查找与内部排序的方法相结合，提出了基于平衡二叉树构造的排序算法，并就其算法设计、效率和稳定性进行分析，达到了预期目的。这种引导学生将课程知识前后串联、融会贯通、综合分析与设计的思想方法，对于培养学生的发散性思维和创新意识，具有十分重要的示范促进作用和深远的影响。
参考文献：
[1] 严蔚敏等，数据结构（C语言版），清华大学出版社，2009.2
[2] 邹永林等，数据结构与算法教程，机械工业出版社，2004.9
[3] 秦锋等，数据结构（C++版），北京林业出版社、北京大学出版社，2006.9
本文根据平衡二叉树的构造原理，提出了利用平衡二叉树进行内部排序的思想，据此完成了对应的算法设计，并通过典型实例进行验证和效率分析。
关键词：平衡二叉树 内部排序
Analysis and Design for Internal Sort Algorithm
Based on AVL tree
ZOU Yong-lin TANG Xiao-yang
（school of computer science and engineering，
Changshu Institute of Technology， 215500）
Abstract
According to the principle of AVL tree constructing， the ideal of sorting by using the AVL tree was developed and the algorithm was designed and implemented in this paper. Finally， the correctness and the efficiency for this algorithm were validated and analysed through the example.
Keywords
AVL tree， internal sort
【中图分类号】G642
1.引言
在数据结构课程教学的理论和实践中，有关内部排序的常用方法，一般将它们分为五大类[1][2][3]：插入、交换、选择、归并和基数排序；并且，大多采用顺序表或链表（队）结构讨论各种算法的具体实现过程。
实际上，并不是所有的内部排序算法都必须使用线性表对应的存储结构来描述。不妨换一种思路，二叉排序树（BST树）和平衡二叉树（AVL树）作为动态查找表结构，它们具有一个基本特点，就是进行中序遍历可以得到一个按结点关键字值递增有序的序列；并且对于平衡二叉树而言，进行一次中序遍历的过程，其时间复杂度为O（log2n）。因此，利用构造平衡二叉树的方法，同样可以实现对一个无序序列进行排序的目的。
2.构造平衡二叉树的基本过程
由平衡二叉树的原理可知，将一个无序序列构造成一棵平衡二叉树时，为了确保其平均查找长度与树的深度相当，在每次插入一个新结点时，需要判断是否失去平衡，从而决定是否需要进行平衡处理以及如何进行平衡处理。
如果一棵平衡二叉树，由于插入一个新结点导致失去平衡，则重新恢复平衡的调整方法有4种，分别是：单向右旋、单向左旋、先左后右和先右后左。具体过程是：首先找到最小不平衡子树，根据其根的平衡因子的值和对应的形态，选择采用不同的方法来恢复其平衡性。
3. 算法设计
根据上述原理，可选择二叉链表存储结构，设计构造平衡二叉树的算法。为了实现待排序关键字中可能存在重复关键字的情形，可对平衡二叉树的定义稍作修改，允许在平衡二叉树中存在值相同的结点；同时，为了确保其稳定性，约定将后续的值相同的关键字以其右子树中的新结点插入。
算法主要代码如下：
#define LH 1 //左高
#define EH 0 //等高
#define RH -1 //右高
#define Num 20
#define true 1
#define false 0
int taller；
typedef struct BSTnode //平衡二叉树的结点结构
{
int data； //关键字
int bf； //平衡因子
struct BSTnode *lc，*rc； //左右指针
}BSTnode；
int InsrtAVL（BSTnode *T，BSTnode *newNode，BSTnode **Tr，int taller）
{ //在平衡二叉树中插入一个新元素
if （newNode->data
{
if （T->lc==NULL） //T的左子树为空树，直接插入
{
taller=true； T->lc=newNode；
}
else //非空，找到插入点再插入
InsrtAVL（T->lc，newNode，&（T->lc），taller）；
if （taller） //判断平衡性
switch （T->bf）
{
case LH： //进行左平衡处理
LeftBalance（T，Tr）； taller=false； break；
case EH：
T->bf=LH； taller=true； break；
case RH：
T->bf=EH； taller=false； break；
}
}
else //在T的右子树中搜索插入
{
if （T->rc==NULL） //T的右子树为空树，直接插入
{
taller=true； T->rc=newNode； }
else //非空，找到插入点再插入
InsrtAVL（T->rc，newNode，&（T->rc），taller）；
if （taller） //判断平衡性
switch （T->bf）
{
case LH：
T->bf=EH； taller=false； break；
case EH：
T->bf=RH； taller=true； break；
case RH： //进行右平衡处理
RightBalance（T，Tr）； taller=false； break；
}
}
return 1；
}
void LeftBalance（BSTnode *T，BSTnode **Tr） //左平衡处理
{
BSTnode * B_node，*C_node；
B_node=T->lc；
switch （B_node->bf）
{
case LH： //单向右旋
T->bf=B_node->bf=EH； R_Rotate（T，Tr）； break；
case RH：
C_node=B_node->rc；
switch （C_node->bf）
{
case LH：
T->bf=RH； B_node->bf=EH； break；
case EH：
T->bf=B_node->bf=EH； break；
case RH：
T->bf=EH； B_node->bf=LH； break；
}
C_node->bf=EH；
L_Rotate（B_node，&（T->lc））； //先左旋后右旋
R_Rotate（T，Tr）；
}
}
void RightBalance（BSTnode *T，BSTnode **Tr） //右平衡处理
{
BSTnode * C_node，*B_node；
B_node=T->rc；
switch （B_node->bf）
{
case RH： //单向左旋
T->bf=B_node->bf=EH； L_Rotate（T，Tr）； break；
case LH：
C_node=B_node->lc；
switch （C_node->bf）
{
case RH：
T->bf=LH； B_node->bf=EH； break；
case EH：
T->bf=B_node->bf=EH； break；
case LH：
T->bf=EH； B_node->bf=RH； break；
}
C_node->bf=EH；
R_Rotate（B_node，&（T->rc））； //先右旋后左旋
L_Rotate（T，Tr）；
}
}
void R_Rotate（BSTnode *P，BSTnode **Tr） //右旋
{
BSTnode *lch；
lch=P->lc；
P->lc=lch->rc；
lch->rc=P；
P=lch；
*Tr=P；
}
void L_Rotate（BSTnode *P，BSTnode **Tr） //左旋
{
BSTnode * rch；
rch=P->rc；
P->rc=rch->lc；
rch->lc=P；
P=rch；
*Tr=P；
}
int MidOrder（BSTnode *T） //中序遍历平衡二叉树
{
int l，r；
if （！T） return 0；
l=MidOrder（T->lc）；
printf（"%d，"，T->data）；
r=MidOrder（T->rc）；
return l+r+1；
}
int main（）
{
int n=0，x，i，len；
int datas[Num]；
BSTnode *newNode；
while（scanf（"%d"，&x）==1） //输入待排序关键字序列
{datas[n]=x；n++；}
len=n；
printf（"Init datas：＼n"）； //第一个关键字作为根
printf（"%d， "，datas[0]）；
newNode=（BSTnode *）malloc（sizeof（BSTnode））； newNode->data=datas[0]；
newNode->lc=NULL；
newNode->rc=NULL；
newNode->bf=EH；
Root=newNode；
for （n=1；n
printf（"＼nInsert：%d， "，datas[n]）； //构造新结点
taller=true；
newNode=（BSTnode*）malloc（sizeof（BSTnode））；
newNode->data=datas[n]；
newNode->lc=NULL；
newNode->rc=NULL；
newNode->bf=EH；
i=InsrtAVL（Root，newNode，&Root，taller）； //插入
}
printf（"＼nMid_order：＼n"）； //中序遍历输出排序结果
MidOrder（Root）；
return 0；
}
4.算法分析
4.1排序结果与平衡二叉树的状态变化
假设一个给定的待排序序列，包含12个关键字，初始形态如下：
int datas[Num]={20，12，6，28，16，36，32，10，2，30，8，32}；
采用上述算法进行排序，排序过程和平衡二叉树的状态变化如图1所示。
上述过程和结果符合平衡二叉树构造的原理，结果完全正确。
4.2算法分析
采用构造平衡二叉树的方法进行排序，其排序思想非常简单，只要根据给定的待排序关键字序列，从无到有依次将每个关键字正确插入平衡二叉树即可。待所有待排序关键字插入完成后，最终进行一次中序遍历，就可得到正确的排序结果。整个算法的关键在于完成平衡二叉树的构造。
对于上述算法，从时间需求上看，由于在一棵包含n个结点的平衡二叉树中插入一个新结点时，由其平衡性，查找插入位置需要进行的关键字比较的个数不超过平衡二叉树的深度，故插入操作的时间复杂度为O（log2n），整个排序过程共需要插入n个关键字，因此，算法的时间效率均为O（nlog2n）；从空间需求分析，除了需要在排序过程中动态申请n个平衡二叉树结点和少量搜索指针外，不再需要额外的存储空间，因而存储空间的需求也低。另外，根据本文对平衡二叉树定义的修改约定，上述算法是一个稳定的排序算法。
图1平衡二叉树的状态变化和排序结果
5.结语
以上根据平衡二叉树的概念和基本特性，讨论了借助构造平衡二叉树的方法进行内部排序的算法设计，并利用一个典型实例对该算法进行了验证；最后，对算法的时间效率、空间需求和稳定性作了分析和讨论，得到了正确的结果。
本文通过将动态查找与内部排序的方法相结合，提出了基于平衡二叉树构造的排序算法，并就其算法设计、效率和稳定性进行分析，达到了预期目的。这种引导学生将课程知识前后串联、融会贯通、综合分析与设计的思想方法，对于培养学生的发散性思维和创新意识，具有十分重要的示范促进作用和深远的影响。
参考文献：
[1] 严蔚敏等，数据结构（C语言版），清华大学出版社，2009.2
[2] 邹永林等，数据结构与算法教程，机械工业出版社，2004.9
[3] 秦锋等，数据结构（C++版），北京林业出版社、北京大学出版社，2006.9