AVL平衡树的旋转
平衡二叉树在进行插入操作的时候可能出现不平衡的情况,AVL树即是一种自平衡的二叉树,它通过旋转不平衡的节点来使二叉树重新保持平衡,并且查找、插入和删除操作在平均和最坏情况下时间复杂度都是O(log n)
AVL树的旋转一共有四种情形,注意所有旋转情况都是围绕着使得二叉树不平衡的第一个节点展开的。
1. LL型
平衡二叉树某一节点的左孩子的左子树上插入一个新的节点,使得该节点不再平衡。这时只需要把树向右旋转一次即可,如图所示,原A的左孩子B变为父结点,A
变为其右孩子,而原B的右子树变为A的左子树,注意旋转之后Brh是A的左子树(图上忘在A于Brh之间标实线)
2. RR型
平衡二叉树某一节点的右孩子的右子树上插入一个新的节点,使得该节点不再平衡。这时只需要把树向左旋转一次即可,如图所示,原A右孩子B变为父结点,A变为其左孩子,而原B的左子树Blh将变为A的右子树。
3. LR型
平衡二叉树某一节点的左孩子的右子树上插入一个新的节点,使得该节点不再平衡。这时需要旋转两次,仅一次的旋转是不能够使二叉树再次平衡。如图所示,在B节点按照RR型向左旋转一次之后,二叉树在A节点仍然不能保持平衡,这时还需要再向右旋转一次。
4. RL型
平衡二叉树某一节点的右孩子的左子树上插入一个新的节点,使得该节点不再平衡。同样,这时需要旋转两次,旋转方向刚好同LR型相反。
下面是一些例子:
具体步骤如下:
⑴ 每当插入一个新结点,从该结点开始向上计算各结点的平衡因子,即计算该结点的祖先结点的平衡因子,若该结点的祖先结点的平衡因子的绝对值均不超过1,则平衡二叉树没有失去平衡,继续插入结点;
⑵ 若插入结点的某祖先结点的平衡因子的绝对值大于1,则找出其中最小不平衡子树的根结点;
⑶ 判断新插入的结点与最小不平衡子树的根结点的关系,确定是哪种类型的调整;
⑷
如果是LL型或RR型,只需应用扁担原理旋转一次,在旋转过程中,如果出现冲突,应用旋转优先原则调整冲突;如果是LR型或LR型,则需应用扁担原理旋转
两次,第一次最小不平衡子树的根结点先不动,调整插入结点所在子树,第二次再调整最小不平衡子树,在旋转过程中,如果出现冲突,应用旋转优先原则调整冲
突;
⑸ 计算调整后的平衡二叉树中各结点的平衡因子,检验是否因为旋转而破坏其他结点的平衡因子,以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。
设有关键码序列{20, 35, 40, 15, 30, 25, 38},图7-3给出了平衡二叉树树的构造过程,结点旁边标出的是该结点的平衡因子。
分享到:
相关推荐
使用C++实现的AVLTree自平衡二叉树,支持动态插入与删除操作,供C++数据结构课程学习与交流使用。
本设计实现了AVLTree的所有的实现功能,也包括BinSTree与AVLTree的转换
一个avltree的简单实现,便于了解avltree的结构及应用
avl tree 中的各种旋转
AVL Tree 的代码实例,包括插入和删除节点操作。
AVL Tree source code
这是一个用C实现的AVL tree,带MFC的测试程序。 在我的机器上(P4 T2050 Duo, 1G memory)列C盘所有文件并组织成AVL tree,一共是70000多个文件和目录,耗时大约是5-7秒
An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is...
AVL tree using node from data structure and algorithm java class, create a minimum AVL tree with minimum number of nodes at given high
04-树4. Root of AVL Tree (25)。 AVL树的旋转,Devc的工程文件。
avl tree implementation
AVL tree implementation in java
AVL tree with insertion,deletion and balancing height
avltree的c代码实现,没有错,放心下载
自己写的平衡树的构建及相关操作
AVL Tree implementation
AVLTREE,数据结构中AVL树的C语言实现
自己写的AVLtree,大家看着用吧,是浙大网课上的同步作业
Program sorting array of numbers using avl tree
Java代码实现,从文件中读取数据,根据AVL树的构建规则,构建一棵AVL树(平衡二叉树),并输出平均查找长度ASL。