基于平衡二叉树的排序算法分析与设计摘要：本文根据平衡二叉树的构造原理，提出了利用平衡二叉树进行内部排序的思想，据此完成了对应的算法设计，并通过典型实例进行•验证和效率分析。关键词：平衡二叉树内部排序AnalysisandDesignforTnternalSortAlgorithmBasedonAVLtreeZOUYong-linTANGXiao-yang(schoolofcomputerscienceandengineering,ChangshuInstituteofTechnology,215500)AbstractAccordingtotheprincipleofAVLtreeconstructing,theidealofsortingbyusingtheAVLtreewasdevelopedandthealgorithmwasdesignedandimplementedinthispaper・Finally,thecorrectnessandtheefficiencyforthisalgorithmwerevalidatedandanalysedthroughtheexainple・KeywordsAVLtree,internalsort【中图分类号】G6421.引言在数据结构课程教学的理论和实践中，有关内部排序的常用方法，一般将它们分为五大类［3］：插入、交换、选择、归并和基数排序；并且，大多采用顺序表或链表（队）结构讨论各种算法的具体实现过程。实际上，并不是所有的内部排序算法都必须使用线性表对应的存储结构來描述。不妨换一种思路，二叉排序树（BST树）和平衡二叉树（AVL树）作为动态查找表结构，它们具有一个基本特点，就是进行中序遍历可以得到一个按结点关键字值递增有序的序列；并且对于平衡二叉树而言，进行一次中序遍历的过程，其时间复杂度为0（log2n）。因此，利用构造平衡二叉树的方法，同样可以实现对一个无序序列进行排序的目的。2.构造平衡二叉树的基本过程由平衡二叉树的原理可知，将一个无序序列构造成一棵平衡二叉树时，为了确保其平均查找长度与树的深度相当，在每次插入一个新结点时,需要判断是否失去平衡，从而决定是否需耍进行平衡处理以及如何进行平衡处理。如果一棵平衡二叉树，由于插入一个新结点导致失去平衡，则重新恢复平衡的调整方法有4种，分别是：单向右旋、单向左旋、先左后右和先右后左。具体过程是：首先找到最小不平衡子树，根据其根的平衡因子的值和对应的形态，选择采用不同的方法来恢复其平衡性。3.算法设计根据上述原理，可选择二叉链表存储结构，设计构造平衡二叉树的算法。为了实现待排序关键字中可能存在重复关键字的情形，可对平衡二叉树的定义稍作修改，允许在平衡二叉树中存在值相同的结点；同时，为了确保其稳定性，约定将后续的值相同的关键字以其右子树中的新结点插入。算法主要代码如下：#defineLH1//左高#defineEli0//等高#defineRH-1//右高#defineNum20#definetrue1#definefalse0inttaller；typedefstructBSTnode//平衡二叉树的结点结构{intdata；//关键字intbf；//平衡因子structBSTnode*lc,*tc；//左右指针}BSTnode；intInsrtAVL(BSTnode*T,BSTnode*newNode,BSTnode**Tr,inttaller){//在平衡二叉树中插入一个新元素if(newNode->datadala)//在T的左子树中搜索插入if（T-〉lc二二NULL）//T的左子树为空树，直接插入taller=true；T->lc=newNode；}else//非空，找到插入点再插入InsrtAVL(T->lc,newNode,&(T-〉lc),taller)；if(taller)//判断平衡性switch(T->bf){caseLH：//进彳亍左平衡处理LeftBalance(T,Tr)；taller二false；break；caseEH：T->bf=LII；taller二true；break；caseRH：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)//左平衡处理IcaseLil：T->bf二EH；taller=false；break；caseEli：T->bf二RH；taller二true；break；caseRH：//进彳亍右平衡处理RightBalance(T,Tr)；taller二false；break；1JIJreturn1；}voidLefLBalance(BSTnode*T,BSTnode**Tr)[BSTnode*Bnode,*Cnode；Bnode=T->lc；switch(Bnode->bf)caseLH：//单向右旋T-'bf*二Bnode~>b仁EH；RRotate(T,Tr)；break；caseRH：Cnode=Bnode->rc；switch(Cnode~>bf)icaseLII：T->bf二RH；B_node->bf二EH；break；caseEli：T->b仁Bnode~>b仁EH；break；caseRH：T->bf二Eli；B^node->bf=LII；break...