《平衡二叉树AVL的查找插入和删除》由会员分享，可在线阅读，更多相关《平衡二叉树AVL的查找插入和删除（43页珍藏版）》请在金锄头文库上搜索。
1、平衡二叉树AVL 查找、插入和删除小组成员：陈 静 101070009陈丹璐 101070006陈 娇 101070008平衡二叉树的查找、插入和删除第#页共38页目录平衡二叉树AVL 1.查找、插入和删除 1.问题描述2.设计说明3.一ADT3.二算法思想5.三数据结构.12四程序结构与流程 13运行平台及开发工具 .15I/O 格式1.5算法复杂度分析 1.8源代码1.8小结37问题描述利用平衡二叉树实现一个动态查找表。平衡二叉树的查找、插入和删除1)实现动态查找表的三种根本功能：查找、插入和删除。(2) 初始时，平衡二叉树为空树，操作界面给出创立、查找、插入和删除和退出五种操作供选择。每
2、种操作均要提示输入关键字。创立时，根据提示输入数据，以-1为输入数据的结束标志，假设输入数据重复，那么给出已存在相同关键字的提示，并不将其插入到二叉树中。在查找时，如果查找的关键字不存在，那么显示不存在查找的关键字，假设存在那么显示存在要查找的关键字。插入时首先检验原二叉树中是否已存在相同第3页共38页-3 -的关键字，假设没有那么进行插入并输出二叉树，假设有那么给出已有相同关键字的提醒。删除时首先检验原二叉树中是否存在要删除的关键字，假设有那么进行删除后并输出二叉树，假设没有那么给出不存在要删除的关键字的提醒。(3) 平衡二叉树的显示采用中序遍历的方法输出，还可以根据输出数据是否有序验证 对
3、平衡二叉树的操作是否正确。设计说明(一)ADTADT BalancedBinaryTree(数据对象D : D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标志的数据元素的关键字。数据关系R:数据元素同属一个集合。根本操作P:void R_Rotate(BSTree &p);初始条件：二叉树存在，且关键字插入到以*p为根的二叉树的左子树的左孩子上；操作结果：对以*p为根的二叉排序树作右旋处理平衡二叉树的查找、插入和删除初始条件：二叉树存在，且关键字插入到以*p为根的二叉树的右子树的右孩子上；操作结果：对以*p为根的二叉排序树作左旋处理void LeftBalance(BST
4、ree &T);初始条件：二叉树存在，且关键字插入到T所指节点为根的二叉树的左子树的右孩子上;操作结果：对以指针 T所指结点为根的二叉树作左平衡旋转处理void RightBalance(BSTree &T);初始条件：二叉树存在，且关键字插入到T所指节点为根的二叉树的右子树的左孩子上;操作结果：对以指针 T所指结点为根的二叉树作右平衡旋转处理bool InsertAVL(BSTree &T,int e,bool &taller);初始条件：T存在，且e与二叉树的原有关键字不同；操作结果：插入结点 e平且平衡化；bool SearchBST(BSTree &T,int key);初始条件：T存
5、在且元素key与某关键字相同；操作结果：查找元素 key是否在树T中void PrintBST(BSTree T);初始条件：T存在操作结果：按中序遍历输出二叉树的元素void CreatBST(BSTree &T);初始条件：T为空操作结果：创立平衡二叉树,(注意:以输入-1为二叉树建立的结束)void LeftBalance_div(BSTree &p,int &shorter);平衡二叉树的查找、插入和删除初始条件：T存在操作结果：删除结点时左平衡旋转处理void RightBalance_div(BSTree &p,int &shorter);初始条件：T存在操作结果：删除结点时右平衡
6、旋转处理void Delete(BSTree q,BSTree &r,int &shorter);初始条件：T存在且节点删除成功操作结果：删除结点int DeleteAVL(BSTree &p,int x,int &shorter);初始条件：操作结果：平衡二叉树的删除操作 ADT BalancedBinaryTree(二) 算法思想1、查找在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素，假设查找成功,那么返回指向该数据元素结点的指针，否那么返回空指针。如果树 T为空，那么查找不成功，返回空指针；当树T非空时，如果根指针T所指数据元素的关键字等于 key，那么查找成功，返回
7、根指针T,否那么在左子树中继续查找，假设还未找到，那么继续在右子树中进行查找，直到找到 该数据元素或树T为空为止。平衡二叉树的查找、插入和删除查找元素key是否在树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的根节点，树
8、长高，树的深度增加1。二假设待插入的数据元素 e与T的根节点的关键字相同，那么不进行插入。三假设待插入的数据元素 e小于根节点的关键字，且在 T的左子树上不存在与 e相 等的数据元素，那么将 e插入到T的左子树上。下面就插入到左子树之后，就不同的情况进行处理： 假设之前T的根节点的平衡因子为-1 ,将根节点的平衡因子变为0 , T的深度不变； 假设之前T的根节点的平衡因子为 0,就将根节点的平衡因子变为 1 , T的深度增加； 假设之前的T的根节点的平衡因子为 1 ,那么当其左子树的根节点的平衡因子为1的时候，需要进行单向右旋处理， 并且在右旋处理之后， 将根节点和其右子树根节点的平衡因子 改
9、为0,树的深度不变；当其左子树的根节点的平衡因子为-1的时候，要进行先左后右的双向旋转平衡，并在旋转之后，修改根节点和其左右子树的根节点的平衡因子，树的深度不平衡二叉树的查找、插入和删除变。(四) 假设待插入的数据元素e大于根节点的关键字，且在 T的右子树上不存在与 e相等的数据元素，那么将e插入到T的右子树上。下面就插入到右子树之后，就不同的情况进行处理： 假设之前T的根节点的平衡因子为1 ,将根节点的平衡因子变为 0 , T的深度不变； 假设之前T的根节点的平衡因子为0,就将根节点的平衡因子变为1 , T的深度增加； 假设之前的T的根节点的平衡因子为-1 ,那么当其右子树的根节点的平衡因子
10、为-1的时候，需要进行单向左旋处理，并且在左旋处理之后，将根节点和其左子树根节点的平衡因子改为0 ,树的深度不变；当其右子树的根节点的平衡因子为1的时候，要进行先右后左的双向旋转平衡，并在旋转之后，修改根节点和其左右子树的根节点的平衡因子，树的深度不变。插入结点e,假设T中不存在和e相同关键字的结点，那么插入一个数据元素为e的新结点，并返回1，否那么返回0bool InsertAVL(BSTree &T,int e,bool &taller) (if(!T)/插入新结点，树长高，置taller为true(T = (BSTree)malloc(sizeof(BSTNode);T-data = e
11、;T-lchild = T-rchild =NULL;T-bf = EH; taller = true;平衡二叉树的查找、插入和删除else(if(EQ(e,T-data) /树中已存在和有相同关键字的结点那么不再插入(taller = false;printf(已存在相同关键字的结点n);return 0;if(LT(e,T-data) / 应继续在*T的左子树中进行搜索(if(!InsertAVL(T-lchild,e,taller)return 0;/ 未插入if(taller) / 已插入到*T的左子树中且左子树长高(switch(T-bf) / 检查*T的平衡度(case LH: /
12、原本左子树比右子树高，需要作左平衡处理LeftBalance(T);taller = false; break;case EH: /原本左子树、右子等高，现因左子树增高而使树增高T-bf = LH;平衡二叉树的查找、插入和删除taller = true; break;case RH: /原本右子树比左子树高，现左、右子树等高T-bf = EH;taller = false; break;else /应继续在*T的右子树中进行搜索if(!InsertAVL(T-rchild,e,taller)return 0;/ 未插入if(taller) /已插入到*T的右子树中且右子树长高switch(T-
13、bf) / 检查*T的平衡度case LH: /原本左子树比右子树高，现左、右子树等高T-bf = EH; taller = false; break;case EH: /原本左子树、右子等高，现因右子树增高而使树增高T-bf = RH; taller = true; break;case RH: /原本右子树比左子树高，需要作右平衡处理RightBalance(T); taller = false; break;页共38页平衡二叉树的查找、插入和删除return 1;/InsertAVL3、删除元素的删除，有三种情况，分别是：(1) 被删除的结点是叶子；(2) 被删除的结点只有左子树或者只有
14、右子树；(3) 被删除的结点既有左子树，也有右子树。具体实现如下：int DeleteAVL(BSTree &p,int x,int &shorter)(int k;BSTree q;if(p=NULL)(printf(不存在要删除的关键字！!n);return 0;else if(xdata)/ 在p的左子树中进行删除(k=DeleteAVL(p-lchild,x,shorter);if(shorter=1)LeftBalance_div(p,shorter);return k;else if(xp-data)/ 在p的右子树中进行删除(k=DeleteAVL(p-rchild,x,shorter);if(shorter=1)RightBalance_div(p,shorter);return k;else(q=p;if(p-rchild=NULL) /右子树空那么只需重接它的左子树(p=p-lchild;free(q);shorter=1;第#页共38页平衡二叉树的查找
