AVL树的删除算法的两种实现方法
本文是本人原创,当时作为长安大学高一凡老师带的学生,我的毕业设计就是做一个AVL 算法的演示软件。其中,AVL树的删除算法在度娘和 谷歌了很久都没有找到逻辑通畅或者说是我能够看懂的。后来,闭门造成,费了十几张A4纸才把算法设计出来
本文是当时我想投稿的一个草稿,只是当时太嫩,不敢投论文。。而且马上就毕业了,所以就一直没了下文。现,贡献该草稿,希望对要了解AVL树算法的同学有帮助。
<原创证明>邮件来往。
摘要:AVL树是一种重要的数据结构,凡是能够用二叉查找树的地方都能用AVL树代替,而且其效率最坏也是.一般的数据结构书上通常都只介绍AVL树的插入算法。本文将讨论AVL树删除算法的递归和非递归实现及其可视化实现。
关键字:AVL树;删除;递归;非递归;可视化
1.删除结点的分类
对于要删除的结点设为E可以分为三种类型,如图1 所示
(1)叶子结点
(2)没有左子树且有右子树的结点
(3)有左子树的结点
对于叶子结点E可以直接删除,而对于只有右子树ER的结点可以将ER的值赋给E然后将ER释放并将E右孩子指空。
对于第(3)种则要在EL中找到E的中序遍历的前驱结点。E的前驱结点为EL中值最大的结点。将前驱结点的值赋给E且删除前驱结点。
2 删除结点后的失衡类性及其调整
删除结点后可能导致其祖先结点的不平衡。由于左右对称,我们仅分析删除发生在右子树的情况。我们将各种情况删除前,删除后以及调整后整个过程的变化用图示的方法表示。
图2.1描述的是在T的右子树TR中删除结点后导致T失衡,须进行R_Rotate(T)处理,处理之后各结点的平衡因子如图所示,且树不变矮。
图2.2描述的是在T的右子树TR中删除结点后导致T失衡,须进行R_Rotate(T)处理,处理之后各结点的平衡因子如图所示,且树的高度减1 。
图2.3描述的是在T的右子树TR中删除结点后导致T失衡,须进行LR_Rotate(T)处理,处理之后各结点的平衡因子如图所示,且树的高度减1 。
图2.4描述的是在T的右子树TR中删除结点后导致T失衡,须进行LR_Rotate(T)处理,处理之后各结点的平衡因子如图所示,且树的高度减1 。
图2.5描述的是在T的右子树TR中删除结点后导致T失衡,须进行LR_Rotate(T)处理,处理之后各结点的平衡因子如图所示,且树的高度减1 。
另外还有两种不发生失衡的情况如图2.6和图2.7所示
图2.6描述的是在T的右子树TR中删除结点后的T的平衡因子变为1,树的高度不变
图2.7描述的是在T的右子树TR中删除结点后的T的平衡因子变为0,树的高度减1.
3 实现算法
3.1 数据结构
template<typename T>struct BSTNode//平衡二叉树的结点类型结构体
{
T data;//结点数据类型
int bf;//结点的平衡因子,比二叉链表结点多此项
BSTNode<T>*lchild,*rchild;//左右孩子指针
};
3.2 算法
3.2.1 递归法
递归实现AVL树的结点删除的思想如下。
在AVL树T上删除值为E的结点步骤如下:
(1)若树T为空,返回0退出否则到(2);
(2)比较T的数据和E,若相等跳到(3),若E小于T->data跳到(4),若E大于T->data则跳到(5)
(3)分析T结点的类型
(3.1)若T是叶子结点则直接删除,树变矮即lower=1;
(3.2)若T只有右子树TR则将右子树结点的值赋给T,删除TR结点将T->rchild=NULL,lower=1;
(3.3)若T有左子树,则找到其中序遍历的前驱结点P,将P结点值用临时变量temp保存,并且用指针Tptr保存T;递归删除结点P;将Tptr所指结点即原T结点的值更新为temp;
(4)在左子树T->lchild中递归删除值为E的结点,若删除成功检查左子树是否变矮即lower的值是否为1;若lower=0返回0退出;若lower=1则进行失衡调整各种情况上文有分析
(5)在右子树T->rchild中递归删除值为E的结点,若删除成功检查左子树是否变矮即lower的值是否为1;若lower=0返回0退出;若lower=1则进行失衡调整,各种情况上文有分析
3.2.2非递归法
非递归的算法思想如下。
在AVL树T上删除值为E的结点的步骤如下:
初始化一个栈s ;
(1) 若树T为空则返回0退出否则跳到(2);
(2)p为工作指针p=T;比较p的数据和E,若相等则跳到(3),若E小于p->data则跳到(4),若E大于p->data则跳到(5)
(3) 分析p结点的类型
(3.1)若p是叶子结点则直接删除,树变矮,
(3.1.1)若p是其父结点的左子树则lower=1;
(3.1.2)若p是其父结点的右子树则lower=2;
(3.2) 若p只有右子树pR则将右子树结点的值赋给p然后删除删除pR,树变矮,lower的值 和(3.1)一样分析,之后不再特别说明则都和(3.1)处理一样。
(3.3)若p有左子树pL则将p和pL入栈,且用指针tempptr指向p即tempptr=p然后执行
q=TL ;While(q->rchild){q=q->rchild;s.push(q);}之后可以找到p的前驱结点q,将q的值赋给原p结点即tempptr->data=q->data,若q是叶子结点则直接删除否则将q的左子树代替q。树变矮且弹栈s.pop() ;然后执行如下循环体
(3.3.1)若栈不空且lower不为0则执行
a.弹栈q=s.top();s.pop();及其q的父结点fa=s.top();
若fa=NULL则表明q是根结点则若要执行下面 b
或c时不用在给lower赋值了。
b.若lower=1则表明左子树变矮,执行相应的失衡调整,并且调整过程中若导致q树变矮也得根据q为fa的左子树还是右子树将lower=1或为lower=2;
c.若lower=2 则表明右子树变矮,执行相应的失衡调整,并且调整过程中若导致q树变矮也得根据q为fa的左子树还是右子树将 lower=1或为lower=2;
退出循环后返回0退出;
(4)将p入栈且p=p->lchild;然后跳到(2);
(5)将p入栈且p=p->rchild;然后跳到(2);
4实例分析
有如图3.1所示的AVL树
图3.1
选择删除61结点后如
5结束语
无论是递归还是非递归实现AVL树的删除都比较复杂,将其总结为算法并配以图形化的实现使得AVL树的在课堂上讲解更为方便,继而有力的推广AVL树的应用。
6参考文献
严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2007.
分享到:
相关推荐
次程序是关于avl树的删除、插入、左单旋、右单旋、左右双旋、右左双旋的算法实现。程序有主菜单可按提示进行操作。
AVL平衡二叉树的C++实现(模板),实现了插入、查找、删除,前序、后序、中序遍历等
C++实现类模板 包括二叉树、搜索二叉树、AVL树及它们的各种算法实现(包括建立、输出、前序遍历、中序遍历、后序遍历、插入、删除、搜索、重构、求树高、统计叶子总数等等)
(1)编写 AVL树判别程序,并判别一个二元查找树是否为 AVL树。二元查找树用其先序遍历结果表示,如:...(2)实现 AVL树的 ADT,包括其上的基本操作:结点的加入和删除;另外包括将一般二元查找树转变为 AVL树的操作。
AVL树算法,编程结构清晰,易于学习临摹。 欢迎下载。
之前只写了一些AVL树核心算法,这里给出一个AVL树的完整实现。 AVL树是平衡查找二叉树,不仅能避免二叉搜索树出现斜树的状况,更是能保持比较标准的O(log2N),但AVL树可能需要很多次的各种调整: 左儿子单旋转 左...
完整实现二叉搜索树,红黑树,AVL平衡树,B树的搜索插入删除基本功能和其它功能。红黑树和B树参考自算法导论。
第3版的主要更新如下:第4章包含AVL树删除算法的实现。第5章进行了全面修订和扩充,现在包含两种较新的算法——布谷鸟散列和跳房子散列。第7章包含基数排序的相关内容,并给出了下界证明。第12章增加了后缀树和后缀...
实现二叉平衡树的相关运算算法。并在此基础上完成如下功能:1、由{4,9,0,1,8,6,3,5,2,7}创建一颗AVL树b并以括号表示输出。2、在b中分别删除关键字为8和2 的结点,并以括号表示法输出删除后的AVL树
二叉树 5.1 二叉树概念、性质 5.2 完全二叉树概念、性质 5.3 满二叉树定义、性质 5.4 二叉树的遍历算法实现(递归与非递归)、线索二叉树的操作 5.5二叉搜索树概念及查找、插入、删除算法 5.6 AVL树概念;AVL树平衡...
基于树的字典ADT 字典或地图是一种抽象数据...使用二进制搜索树(BST)实现此字典ADT 。 通过使用二进制搜索算法,该数据结构允许非常高效的查找。 该实现从创建和使用节点和链接(指针)的结构开始。 由于使用C语言,
第3版的主要更新如下:第4章包含AVL树删除算法的实现。第5章进行了全面修订和扩充,现在包含两种较新的算法——布谷鸟散列和跳房子散列。第7章包含基数排序的相关内容,并给出了下界证明。第12章增加了后缀树和后缀...
C / C ++中的数据结构和算法 该代码由Amit Bansal在学习数据结构和算法时编写。 参考GFG,NPTEL,CLRS。 该存储库包含: 单链表。 添加两个数字表示的链表。 气泡在链接列表中排序合并在链接列表...AVL树 插入b。删除
15.1.3 AVL树的描述 15.1.4 AVL搜索树的搜索 15.1.5 AVL搜索树的插入 15.1.6 AVL搜索树的删除 15.2 红-黑树 15.2.1 基本概念 15.2.2 红-黑树的描述 15.2.3 红-黑树的搜索 15.2.4 红-黑树的插入 15.2.5 红-黑树的删除...
二叉排序树(Binary Search Tree,BST)是一种特殊的二叉树,它具有以下特点: ...然而,如果树的结构不平衡,最坏情况下时间复杂度可能退化为O(n),因此通常需要进行平衡操作(如红黑树、AVL树等)来保持树的平衡性。
数据结构与算法分析C++语言描述 中文第四版 高清含书签 2016本版特色如下: *书中的阐述和算法均用C++新标准C++11的代码...增加了对AVL树删除算法的实现。使用新的union/find分析同时改进此前各版的较弱的O(Mlog*N)界。
AVL 树操作: 插入(添加了平衡因子计算) 删除(添加了平衡因子计算) deleteTree(新的,此时没有其他树添加) checkBalance(检查平衡因子以查看是否需要轮换) calcBF(如果需要,重新计算给定根和所有祖先...
6.1.5 AVL树 6.2 红黑树 6.3 伸展树 6.4 B树 6.4.1 保持B树平衡 6.4.2 实现B树算法 6.4.3 B树实现的代码 6.5 可以看见森林吗 6.6 资源和参考资料 第7章 日期和时间 7.1 日期例程的库...
1、专业的实验报告 2、主要配套上面所传的4个代码 3、实验1:比较普通快速排序和随机快速排序; 实验2:动态规划实现0-1背包和贪心算法实现部分背包;... 实验4:实现红黑树和AVL树的初始化、插入、删除操作。