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给出了平衡二叉树树的构造过程,结点旁边标出的是该结点的平衡因子。
分享到:
相关推荐
avl tree 中的各种旋转
使用C++实现的AVLTree自平衡二叉树,支持动态插入与删除操作,供C++数据结构课程学习与交流使用。
本设计实现了AVLTree的所有的实现功能,也包括BinSTree与AVLTree的转换
一个avltree的简单实现,便于了解avltree的结构及应用
AVL Tree source code
这是一个用C实现的AVL tree,带MFC的测试程序。 在我的机器上(P4 T2050 Duo, 1G memory)列C盘所有文件并组织成AVL tree,一共是70000多个文件和目录,耗时大约是5-7秒
4. `avltree_test`:这个可能是编译后的可执行文件,当运行这个文件时,它会执行`avltree_test.c`中的测试代码,展示AVL树的运作情况。 关于AVL树的实现,主要涉及以下几个核心概念: - **节点定义**:每个节点...
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
`AVL_tree.ncb`、`AVL_tree.sln`、`AVL_tree.suo`和`AVL_tree`可能是Visual Studio项目文件,包含了实现AVL树数据结构的源代码。`ncb`文件是Visual Studio的非编译缓存,`sln`是解决方案文件,`suo`存储用户特定的...
在"www.pudn.com.txt"和"AVLTree"这两个文件中,可能包含了关于AVL树的更多详细信息,如实现代码、示例或进一步的解释。学习AVL树不仅能够理解其基本概念和操作,还能深入理解数据结构的设计和优化,这对于理解和...
AVLTree.java文件应该包含了AVL树的实现,包括节点类的定义、插入、删除、旋转等核心功能。通过阅读和理解这个源代码,你可以深入学习AVL树的原理和操作,这对于理解和使用自平衡二叉查找树是非常有价值的。在实际...
综上所述,"AVLtree_c_avl_平衡二叉树_avltree_"这个项目可能是用C语言实现了一个AVL树的数据结构,并提供了对树的增删改查操作,同时具备用户友好的交互界面。这个项目对于理解和实践AVL树的概念、操作和性能优化...
自己写的平衡树的构建及相关操作
4. **代码实现**:`PAT 1066 Root of AVL Tree.cpp` 文件可能包含了实现AVL树的基本数据结构、插入、删除和平衡调整的函数。在实际编程中,通常会定义一个AVL树节点结构体,包含键值、子节点指针、以及平衡因子。...
在"03平衡二叉树_AVLTree.c"这个文件中,应该包含了C语言实现AVL树的代码,包括节点结构定义、插入、删除和查找等基本操作,以及相应的旋转函数。通过阅读和理解这段代码,可以深入学习AVL树的内部工作原理和操作...
AVL树是一种自平衡二叉查找树(Binary Search Tree, BST),由Georgy Adelson-Velsky和Emanuel Landis于1962年提出,因此得名AVL树,其中A、V、L分别是他们姓氏的首字母。在AVL树中,每个节点的两个子树的高度差最多...
AVL树是一种自平衡的二叉搜索树,由G. M. Adelson-Velsky和E. M. Landis在1962年提出,因此得名AVL树。它的主要特点是任何节点的两个子树的高度差不超过1,这使得AVL树具有较高的查找效率。在AVL树中,平均查找长度...
在二叉树的基础上,二叉查找树(Binary Search Tree,BST)是一种特殊的二叉树,其每个节点的值都大于其左子树中的任何节点的值,并小于其右子树中的任何节点的值。这种性质使得二叉查找树在查找特定值时具有较高的...
AVL树是自平衡二叉查找树(Self-Balancing Binary Search Tree)的一种,由G. M. Adelson-Velsky和E. M. Landis于1962年提出,因此得名AVL树。在AVL树中,任何节点的两个子树的高度最大差别不超过1,这保证了树的...