平衡二叉树(AVL)的查找、插入和删除

1、平衡二叉树（AVL ）查找、插入和删除小组成员：陈 静 101070009陈丹璐 101070006陈 娇 101070008平衡二叉树的查找、插入和删除第5页共38页目录平衡二叉树（AVL ） 1.查找、插入和删除1.问题描述2.设计说明3.（一）ADT3.（二）算法思想5.（三）数据结构.12（四）程序结构与流程 1.3运行平台及开发工具 .15I/O 格式1.5算法复杂度分析 1.8源代码1.8小结37问题描述利用平衡二叉树实现一个动态查找表。平衡二叉树的查找、插入和删除(1)实现动态查找表的三种基本功能：查找、插入和删除。(2)初始时，平衡二叉树为空树，操作界面给出创建、查找、插入和删

2、除和退出五种操作供选择。每种操作均要提示输入关键字。创建时，根据提示输入数据，以-1为输入数据的结束标志，若输入数据重复，则给出已存在相同关键字的提示，并不将其插入到二叉树中。在查找时，如果查找的关键字不存在，则显示不存在查找的关键字，若存在则显示存在 要查找的关键字。插入时首先检验原二叉树中是否已存在相同第3页共38页-3 -的关键字，若没有则进行插入并输出二叉树，若有则给出已有相同关键字的提醒。删除时首先检验原二叉树中是否存在要删除的关键字，若有则进行删除后并输出二叉树，若没有则给出不存在要删除的关键字的提醒。(3 )平衡二叉树的显示采用中序遍历的方法输出，还可以根据输出数据是否有序验证

3、对平衡二叉树的操作是否正确。设计说明（一）ADTADT Bala ncedBi naryTree数据对象D : D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标志的数据元素的关键字。数据关系R:数据元素同属一个集合。基本操作P:void R_Rotate(BSTree & p);初始条件：二叉树存在，且关键字插入到以*p为根的二叉树的左子树的左孩子上；操作结果：对以*p为根的二叉排序树作右旋处理初始条件：二叉树存在，且关键字插入到以*p为根的二叉树的右子树的右孩子上；操作结果：对以*p为根的二叉排序树作左旋处理void LeftBala nce(BSTree &T);初始

4、条件：二叉树存在，且关键字插入到T所指节点为根的二叉树的左子树的右孩子上;操作结果：对以指针 T所指结点为根的二叉树作左平衡旋转处理void RightBala nce(BSTree &T);初始条件：二叉树存在，且关键字插入到T所指节点为根的二叉树的右子树的左孩子上;操作结果：对以指针 T所指结点为根的二叉树作右平衡旋转处理bool In sertAVL(BSTree &T,i nt e,bool &taller);初始条件：T存在，且e与二叉树的原有关键字不同；操作结果：插入结点e平且平衡化；bool SearchBST(BSTree &T,i nt key);初始条件：T存在且元素key

5、与某关键字相同；操作结果：查找元素 key是否在树T中void Prin tBST(BSTree T);初始条件：T存在操作结果：按中序遍历输出二叉树的元素void CreatBST(BSTree &T);初始条件：T为空操作结果：创建平衡二叉树,(注意:以输入-1为二叉树建立的结束)void LeftBala nce_div(BSTree &p,i nt & shorter);操作结果：删除结点时左平衡旋转处理void RightBalance_div(BSTree &p,int &shorter);初始条件：T存在操作结果：删除结点时右平衡旋转处理void Delete(BSTree q,

6、BSTree &r,int &shorter);初始条件：T存在且节点删除成功操作结果：删除结点int DeleteAVL(BSTree &p,int x,int &shorter);初始条件：操作结果：平衡二叉树的删除操作 ADT Bala ncedBi naryTree(二) 算法思想1、查找在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素，若查找成功,则返回指向该数据元素结点的指针，否则返回空指针。如果树 T为空，则查找不成功，返回空指针；当树T非空时，如果根指针T所指数据元素的关键字等于key，则查找成功，返回根指针T,否则在左子树中继续查找，若还未找到，则继续在右子树

7、中进行查找，直到找到 该数据元素或树T为空为止。bool SearchBST(BSTree &T,int key)if(!T) return false;else if(EQ(key,T-data) return true;else if(LT(key,T-data) return SearchBST(T-lchild,key);else return SearchBST(T-rchild,key);2、插入(一) 若T为空树，则插入一个数据元素为e的新节点作为T的根节点，树长高，树的深度增加1。(二) 若待插入的数据元素e与T的根节点的关键字相同，则不进行插入。(三) 若待插入的数据元素e小

8、于根节点的关键字，且在T的左子树上不存在与 e相等的数据元素，那么将e插入到T的左子树上。下面就插入到左子树之后，就不同的情况进行处理： 若之前T的根节点的平衡因子为-1，将根节点的平衡因子变为0, T的深度不变； 若之前T的根节点的平衡因子为0,就将根节点的平衡因子变为1，T的深度增加； 若之前的T的根节点的平衡因子为1，那么当其左子树的根节点的平衡因子为1的时候，需要进行单向右旋处理，并且在右旋处理之后，将根节点和其右子树根节点的平衡因子改为0,树的深度不变；当其左子树的根节点的平衡因子为-1的时候，要进行先左后右的双向旋转平衡，并在旋转之后，修改根节点和其左右子树的根节点的平衡因子，树的

9、深度不(四) 若待插入的数据元素e大于根节点的关键字，且在T的右子树上不存在与 e相等的数据元素，那么将e插入到T的右子树上。下面就插入到右子树之后，就不同的情况进行处理： 若之前T的根节点的平衡因子为 1，将根节点的平衡因子变为0, T的深度不变； 若之前T的根节点的平衡因子为 0,就将根节点的平衡因子变为1，T的深度增加； 若之前的T的根节点的平衡因子为-1，那么当其右子树的根节点的平衡因子为-1的时候，需要进行单向左旋处理，并且在左旋处理之后，将根节点和其左子树根节点的平衡因子改为0，树的深度不变；当其右子树的根节点的平衡因子为1的时候，要进行先右后左的双向旋转平衡，并在旋转之后，修改根

10、节点和其左右子树的根节点的平衡因子，树的深度不变。/插入结点e,若T中不存在和e相同关键字的结点，则插入一个数据元素为e的新结点，并返回1，否则返回0bool In sertAVL(BSTree &T,i nt e,bool &taller)if(!T)插入新结点，树长高，置taller为trueT = (BSTree)malloc(sizeof(BSTNode);T-data = e;T-lchild = T-rchild =NULL;T-bf = EH; taller = true;第9页共38页平衡二叉树的查找、插入和删除第13页共38页elseif(EQ(e,T-data) /树中已存

11、在和有相同关键字的结点则不再插入taller = false;printf(已存在相同关键字的结点n”);return 0;if(LT(e,T-data) /应继续在*T的左子树中进行搜索if(!I nsertAVL(T-lchild,e,taller)return 0;/ 未插入if(taller) / 已插入到*T的左子树中且左子树”长高”switch(T-bf) / 检查*T的平衡度case LH: /原本左子树比右子树高，需要作左平衡处理LeftBala nce(T);taller = false; break;case EH: /原本左子树、右子等高，现因左子树增高而使树增高T-bf

12、 = LH;平衡二叉树的查找、插入和删除taller = true; break;case RH: II原本右子树比左子树高，现左、右子树等高T-bf = EH;taller = false; break;else II应继续在*T的右子树中进行搜索if(!l nsertAVL(T-rchild,e,taller)return 0;/ 未插入if(taller) /已插入到*T的右子树中且右子树长高”switch(T-bf) / 检查*T的平衡度case LH: /原本左子树比右子树高，现左、右子树等高T-bf = EH; taller = false; break;case EH: II原本

13、左子树、右子等高，现因右子树增高而使树增高T-bf = RH; taller = true; break;case RH: II原本右子树比左子树高，需要作右平衡处理RightBala nce(T); taller = false; break;平衡二叉树的查找、插入和删除return 1;/ln sertAVL3、删除元素的删除，有三种情况，分别是：(1 )被删除的结点是叶子；(2 )被删除的结点只有左子树或者只有右子树；(3)被删除的结点既有左子树，也有右子树。具体实现如下：int DeleteAVL(BSTree &p,int x,int &shorter)int k;BSTree q;

14、if(p=NULL)printf(不存在要删除的关键字！!n);return 0;else if(xdata)在p的左子树中进行删除平衡二叉树的查找、插入和删除k=DeleteAVL(p-lchild,x,shorter); if(shorter=1)LeftBala nce_div(p,shorter); return k;else if(xp-data) 在p的右子树中进行删除k=DeleteAVL(p-rchild,x,shorter);if(shorter=1)RightBala nce_div(p,shorter);return k;elseq=p;if(p-rchild=NULL)

15、 /右子树空则只需重接它的左子树p=p-lchild;free(q);shorter=1;第15页共38页平衡二叉树的查找、插入和删除else if(p-lchild=NULL)左子树空则只需重接它的右子树p=p-rchild;free(q);shorter=1;else/左右子树均不空Delete(q,q-lchild,shorter);if(shorter=1)LeftBala nce_div(p,shorter);p=q;return 1;(三)数据结构本实验中平衡二叉树采用二叉链表的方式进行存储。定义如下:typedef struct BSTNodeint data;平衡二叉树的查找、

16、插入和删除int bf; /结点的平衡因子struct BSTNode *lchild,*rchild;左、右孩子指针BSTNode,*BSTree;(四)程序结构与流程本程序包括四个模块，分别为主函数、AVL的创建、AVL的查找函数、AVL的插入函数、AVL的删除函数。流程图如下：主函数定义如下：主函数主要是根据输入的数字选择要对平衡二叉树进行的操作，创建、查找、删除或者是插入。void mai n()int in put,search;bool taller=false;int shorter=0;BSTree T,T1,T2;平衡二叉树的查找、插入和删除T=(BSTree)malloc(

17、sizeof(BSTNode);T=T仁T2=NULL;while(1)printf(1.创建 t2.查找 t3.插入 t4.删除 t5.退出 *n);printf(”请输入您所需的操作功能:t);scan f(%d, &in put);getchar();switch(i nput)case 1:CreatBST(T); break;case 2:printf(请输入你要查找的关键字);scanf(%d,&search); getchar();if(SearchBST(T,search)prin tf( 该二叉树 中存在关键字%d ，查找成功!n,search);else printf(查找

18、失败!n”);break;case 3:printf(请输入你要插入的关键字);scanf(%d,&search); getchar();平衡二叉树的查找、插入和删除In sertAVL(T,search,taller);Prin tBST(T); break;case 4:printf(请输入你要删除的关键字);scanf(%d,&search); getchar();DeleteAVL(T,search,shorter);Prin tBST(T); break;case 5:break;default:pri ntf( 输入错误，请重新选择。”);break;printf(tt按任意键继续

19、)； getchar();运行平台及开发工具该程序在 Windows XP/07上运行良好，使用Microsoft Visual C+ 6.0I/O格式输入：该程序要求输入数据为整型数据，并以-1作为输入数据的结束标志,开发。创建过程中若输入相同的数据只会生成一个关键字并给出输入数据相同的提示。平衡二叉树的查找、插入和删除因为中序遍历平衡二叉树的得输出：该程序对于对平衡二叉树的输出采用中序遍历的方法。到的结果肯定为有序的，所以可以据此判断对于平衡二叉树操作的正确性。 测试数据：1、创建输入数据：34、45、12、22、34、56、76、11、-45、23、-1 ;进行平衡二叉树的 创建，运行结

20、果如下图:衣Fi & Microsoft Visual 5tudiQ My Pr*ject5 DdbuQ AVLffiU. exe 1 一创建霊査我丸插入4 一删除札退出興 请输人骸所需命操作功能：I请输入关德亍以丄沽束建立帀衡二叉朴宀 请输入关縫宇 以-上结朿建立平衡二貝树=45 请输关變乔以-丄结宋建立平衡二叉恂：12 请输入去龍字t以T结東建立半衡二叉树：22 请输入关縫孚C臥7喀束建立平衝民树仁泗己存在胡司关權字的结点请输入光键三飞以丄结束建立平衡一貝树汚石 请输入关键宇以-丄结朿建立平衡二叉榊）=?6 请输人关犍乔以7结宋建立平衡二叉枕：11K输人关犍字龙以-理吉果建立平衡二叉树:-

21、45:输入关犍字以7结束建立平衝二圮树”備-酯 111222 S3 34455676伽软拼音半； 2、查找【查找23】运行结果:查找在原有二叉树上已存在的关键字:平衡二叉树的查找、插入和删除查找在原有二叉树上不存在的数据:【查找24】运行结果:ttA2.鉴1入入失mJJJ3、插入在1的基础上进行插入，分两种情况：插入与原二叉树关键字不重复的数据:【插入99】运行结果如下：阖45? 4 =93 :搖功Ha33-& 关插入已存在原二叉树中的数据:【插入22】运行结果如下：匚创健2.1115&功屢23 乳集的 留字22 孩入僭SS-S戈12xfltl味S*退岀* 3介号 St Tfi 994、删除删

22、除在原有平衡二叉树上已存在的关键字:【删除22】运行结果如下：睥插列權裁3_集 黑232.所殊11專11建入入9? 出兀n?276删除在原有平衡二叉树上不存在的数据:【删除98】运行结果如下:第23页共38页99退入肇t*2a番关特211您ffigll建入入在平衡二叉树的查找、插入和删除第25页共38页算法复杂度分析在平衡二叉树上进行查找的过程和二叉排序树相同，因此，在查找的过程中与给定值进行比较的关键字个数不会超过数的深度。因此平衡二叉树查找的时间复杂度主要由树的深度决定。我们首先分析深度为 h的平衡树所具有的最少结点数。假设以N (h)表示深度为h的平衡树含有的最少结点数，显然，N (0)

23、 =0 , N(1)=1 ，N(2)=2，并且N(h)=N(h-1)+N( h-2)，在通过归纳法可以求出这个N(h)，反之，在知道n的情况我们也可以推导出h的最大值，所以最后可以得到在平衡二叉树上查找的时间复杂度是T(n)=0( log 2n)。同样的插入和删除的时间复杂度也为0( log 2n)。源代码#in elude #in elude #in elude #defi ne EQ(a,b) (a)=(b) #defi ne LT(a,b) (a)(b)#defi ne LH +1 / 左高#defi ne EH 0 / 等高#defi ne RH -1 / 右高typedef stru

24、ct BSTNodeint data;int bf; /结点的平衡因子struct BSTNode *lchild,*rchild;左、右孩子指针BSTNode,*BSTree;void R_Rotate(BSTree &p); /对以*p为根的二叉排序树作右旋处理void L_Rotate(BSTree &p); /对以*p为根的二叉排序树作左旋处理void LeftBala nce(BSTree &T); /对以指针T所指结点为根的二叉树作左平衡旋转处理void RightBala nce(BSTree &T);/对以指针T所指结点为根的二叉树作右平衡旋转处理bool InsertAVL(

25、BSTree &T,int e,bool &taller);插入结点 ebool SearchBST(BSTree &T,int key);/查找元素 key 是否在树T 中void Prin tBST(BSTree T);/按中序遍历输出二叉树的元素void CreatBST(BSTree &T); /创建平衡二叉树,（注意:以输入-1为二叉树建立的结束）void LeftBala nce_div(BSTree & p,i nt &shorter);/删除结点时左平衡旋转处理void RightBala nce_div(BSTree &p,int &shorter);/删除结点时右平衡旋转处

26、理void Delete(BSTree q,BSTree &r,int &shorter);/删除结点intDeleteAVL(BSTree & p,i nt x,i nt &shorter);/平衡二叉树的删除操作平衡二叉树的查找、插入和删除void mai n()int in put,search;bool taller=false;int shorter=0;BSTree T,T1,T2;T=(BSTree)malloc(sizeof(BSTNode);T=T 仁T2=NULL;while(1)printf(1.创建 t2.查找 t3.插入 t4.删除 t5.退出 *n); printf

27、(请输入您所需的操作功能:t);scan f(%d, &in put);getchar();switch(i nput)case 1:CreatBST(T); break;case 2:printf(请输入你要查找的关键字);scanf(%d,&search); getchar();平衡二叉树的查找、插入和删除if(SearchBST(T,search)prin tf( 该二叉树 中存在关键字d ,查找成功!n,search);else printf(” 查找失败!n);break;case 3:printf(请输入你要插入的关键字);scanf(%d,&search); getchar();

28、In sertAVL(T,search,taller);Prin tBST(T); break;case 4:printf(请输入你要删除的关键字);scanf(%d,&search); getchar();DeleteAVL(T,search,shorter);Prin tBST(T); break;case 5:break;default:pri ntf(输入错误，请重新选择。”);break;printf(tt按任意键继续)； getchar();平衡二叉树的查找、插入和删除/对以*p为根的二叉排序树作右旋处理丄L型平衡旋转法void R_Rotate(BSTree &p)BSTree

29、lc;1c = p-lchild; /lc 指向的*p左子树根结点p-lchild = lc-rchild; /lc的右子树挂接为*p的左子树lc-rchild = p;p = lc; /p 指向新的结点/对以*p为根的二叉排序树作左旋处理，RR型平衡旋转法 void L_Rotate(BSTree &p)BSTree rc;rc = p-rchild; /rc 指向的*p右子树根结点p-rchild = rc-lchild; /rc的左子树挂接为*p的右子树rc-lchild = p;p = rc; /p 指向新的结点平衡二叉树的查找、插入和删除/对以指针T所指结点为根的二叉树作左平衡旋转处

30、理，LR型平衡旋转法void LeftBala nce(BSTree &T)BSTree lc,rd;Ic = T-lchild; /lc 指向*T的左子树根结点switch(lc-bf) / 检查*T的左子树的平衡度，并作相应平衡处理case LH: /新结点插入在*T的左孩子的左子树上，要作单右旋处理T-bf = lc-bf = EH;R_Rotate(T); break;case RH: /新结点插入在*T的左孩子的右子树上，要作双旋处理rd = lc-rchild; /rd 指向*T的左孩子的右子树根switch(rd-bf) / 修改*T及其左孩子的平衡因子case LH:T-bf

31、= RH; lc-bf = EH; break;case EH:T-bf = lc-bf = EH; break;case RH:T-bf = EH; lc-bf = LH; break;rd-bf = EH;L_Rotate(T-lchild); / 对*T的左子树作左旋平衡处理R_Rotate(T); /对*T作右旋平衡处理第29页共38页平衡二叉树的查找、插入和删除/对以指针T所指结点为根的二叉树作右平衡旋转处理，RL型平衡旋转法void RightBala nce(BSTree &T)BSTree rc,ld;rc = T-rchild; /rc 指向*T的右子树根结点switch(r

32、c-bf) / 检查*T的右子树的平衡度，并作相应平衡处理case RH: /新结点插入在*T的右孩子的右子树上，要作单左旋处理T-bf = rc-bf =EH;L_Rotate(T); break;case LH: /新结点插入在*T的右孩子的左子树上，要作双旋处理ld = rc-lchild; /ld 指向*T的右孩子的左子树根switch(ld-bf) / 修改*T及其右孩子的平衡因子case LH: T-bf = EH; rc-bf = RH; break;case EH: T-bf = rc-bf =EH; break;case RH: T-bf = LH; rc-bf = EH;

33、break;第#页共38页e的新结点,平衡二叉树的查找、插入和删除Id-bf = EH;R_Rotate(T-rchild);对*T的右子树作左旋平衡处理L_Rotate(T); II对*T作左旋平衡处理II插入结点e,若T中不存在和e相同关键字的结点，则插入一个数据元素为 并返回1，否则返回0bool In sertAVL(BSTree &T,i nt e,bool &taller)if(!T)II插入新结点，树长高，置taller为trueT = (BSTree)malloc(sizeof(BSTNode);T-data = e;T-lchild = T-rchild =NULL;T-bf

34、 = EH; taller = true;elseif(EQ(e,T-data) II树中已存在和有相同关键字的结点则不再插入平衡二叉树的查找、插入和删除taller = false;printf(”已存在相同关键字的结点n”);return 0;if(LT(e,T-data)/应继续在*T的左子树中进行搜索if(!I nsertAVL(T-lchild,e,taller)return 0;/ 未插入if(taller) / 已插入到*T的左子树中且左子树”长高”switch(T-bf) / 检查*T的平衡度case LH: /原本左子树比右子树高，需要作左平衡处理LeftBala nce(T

35、);taller = false; break;case EH: /原本左子树、右子等高，现因左子树增高而使树增高T-bf = LH;taller = true; break;case RH: /原本右子树比左子树高，现左、右子树等高T-bf = EH;taller = false; break;第#页共38页平衡二叉树的查找、插入和删除else /应继续在*T的右子树中进行搜索 if(!l nsertAVL(T-rchild,e,taller)return 0;/ 未插入if(taller) /已插入到*T的右子树中且右子树长高”switch(T-bf) / 检查*T的平衡度case LH:

36、 /原本左子树比右子树高，现左、右子树等高T-bf = EH; taller = false; break;case EH: /原本左子树、右子等高，现因右子树增高而使树增高T-bf = RH; taller = true; break;case RH: /原本右子树比左子树高，需要作右平衡处理RightBala nce(T); taller = false; break;return 1;/ln sertAVL平衡二叉树的查找、插入和删除/查找元素key是否在树T中bool SearchBST(BSTree &T,int key)if(!T) return false;else if(EQ(

37、key,T-data) return true;else if(LT(key,T-data) return SearchBST(T-lchild,key);else return SearchBST(T-rchild,key);/中序遍历平衡二叉树void Prin tBST(BSTree T)if(T)Prin tBST(T-lchild); printf( %d ,T-data);Prin tBST(T-rchild);第35页共38页平衡二叉树的查找、插入和删除/创建平衡二叉树，(注意：以输入-1为二叉树建立的结束)void CreatBST(BSTree &T)int e;bool t

38、aller=false;T = NULL;printf(n请输入关键字(以-1结束建立平衡二叉树):)；scan f(%d, &e);getchar();while(e != -1)In sertAVL(T,e,taller);printf(n请输入关键字(以-1结束建立平衡二叉树):);scan f(%d, &e);getchar();taller=false;printf(平衡二叉树创建结束，中序遍历平衡二叉树：n);if(T) Prin tBST(T);else printf(这是一棵空树.n);void LeftBala nce_div(BSTree &p,i nt &shorter)

39、BSTree p1,p2;if(p-bf=1) p结点的左子树高，删除结点后p的bf减1,树变矮p-bf=0; shorter=1;else if(p-bf=O)/p结点左、右子树等高，删除结点后p的bf减1,树高不变p-bf=-1; shorter=0;else /p 结点的右子树高p1= p-rchild;/p1指向p的右子树if(p1-bf=0)/p1结点左、右子树等咼，删除结点后p的bf为-2,进行左旋处理,树高不变L_Rotate(p);p1-bf=1;p-bf=-1;平衡二叉树的查找、插入和删除else if(p1-bf=-1)/p1的右子树高，左旋处理后，树变矮L_Rotate(

40、p);p1-bf=p-bf=0; shorter=1;else /p1的左子树高，进行双旋处理(先右旋后左旋)，树变矮p2=p1-lchild;p2-rchild=p1;p-rchild=p2-lchild;p1-lchild=p2-rchild;p2-lchild=p;if(p2-bf=0)p-bf=0; p1-bf=0;else if(p2-bf=-1)p-bf=1;p1-bf=0; elsep-bf=0;第37页共38页平衡二叉树的查找、插入和删除p1-bf=-1;p2-bf=0;P=P2； shorter=1;/删除结点时右平衡旋转处理void RightBala nce_div(BSTree & p,i nt &shorter) BSTree p1,p2;if(p-bf=-1)p-bf=0; shorter=1;else if(p-bf=0)p-bf=1; shorter=0;第#页共38页p-lchild=p2-rchild;平衡二叉树的查找、插入和删除elsep仁p-lchild;if(p1-bf=0)R_Rotat