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