昨天腾讯面试把平衡二叉树当做排序二叉树,绝对遭鄙视了,汗...
平衡二叉树简称平衡树,是由Adelson-Velskii和Landis于1962年首先提出的,所以又称为AVL树。他的定义很简单,就是若一棵二叉树的每个左右节点的高度差最多相差1,此二叉树即是平衡二叉树。把二叉树的每个节点的左子树减去右子树定义为该节点的平衡因子。二叉平衡树的平衡因子只能是1、0或者-1。
平衡二叉树是对二叉搜索树(又称为二叉排序树)的一种改进。二叉搜索树有一个缺点就是,树的结构是无法预料的,随意性很大,它只与节点的值和插入的顺序有关系,往往得到的是一个不平衡的二叉树。在最坏的情况下,可能得到的是一个单支二叉树,其高度和节点数相同,相当于一个单链表,对其正常的时间复杂度有O(lb n)变成了O(n),从而丧失了二叉排序树的一些应该有的优点。
当插入一个新的节点的时候,在普通的二叉树中不用考虑树的平衡因子,只要将大于根节点的值插入到右子树,小于节点的值插入到左子树,递归即可。而在平衡二叉树则不一样,在插入节点的时候,如果插入节点之后有一个节点的平衡因子要大于2或者小于-2的时候,他需要对其进行调整,现在只考虑插入到节点的左子树部分(右子树与此相同)。主要分为以下三种情况:
(1)若插入前一部分节点的左子树高度和右子树高度相等,即平衡因子为0,插入后平衡因子变为1,仍符合平衡的条件不用调整。
(2)若插入前左子树高度小于右子树高度,即平衡因子为-1,则插入后将使平衡因子变为0,平衡性反倒得到调整,所以不必调整。
(3)若插入前左子树的高度大于右子树高度,即平衡因子为1,则插入左子树之后会使得平衡因子变为2,这样的情况下就破坏了平衡二叉树的结构,所以必须对其进行调整,使其加以改善。
调整二叉树首先要明白一个定义,即最小不平衡子树。最小不平衡子树是指以离插入节点最近、且平衡因子绝对值大于1的节点做根的子树。
下面讲解平衡二叉树最基本的4种调整操作,调整的原则是调整后他的搜索二叉树的性质不变,即树的中序遍历是不会改变的:
1. LL型调整。在B点的左子树上插入一个节点。插入后B点的左子树的平衡因子变为1,A节点的平衡因子变为了2。这样可以看出来A节点为根节点的子树是最小不平衡子树。调整时,将A的左孩子B向右旋转代替A称为原来不平衡子树的根节点,将A的节点右下旋转称为B的右子树的根节点,而B的原右子树变为A的左子树。详细过程如下图:
2. RR型调整操作
在A节点的右孩子的右子树上插入节点,使得A节点的平衡因子由-1变为-2而引起的不平衡所进行的调整操作。调整操作大致一样,看图就可以明白了。
3. LR型的调整操作。在A节点的左孩子的右子树上插入节点,使得A节点的平衡因子由1变为了2而引起的不平衡所进行的调整的操作。调整过程如图:
4. RL型的调整操作。不多说了,直接上图:
在二叉搜索树的插入和删除运算中,采用平衡树的优点是:使树的结构较好,从而提高查找运算的速度。缺点是:是插入和删除运算变得复杂化,从而降低了他们的运算速度。对二叉搜索树删除节点而引起的不平衡性进行的操作比插入节点的情况要复杂,在此就不再论述了。
分享到:
相关推荐
平衡二叉树Java实现,平衡二叉树Java实现,平衡二叉树Java实现,平衡二叉树Java实现,
用JAVASCRIPT+VML实现平衡二叉树里增加节点删除节点的功能,目的是把二叉树的平衡算法记录在这里(备忘)。 目前只做了增加删除节点时二叉树自动平衡,保证这棵树什么时候都是平衡状态;如何将一棵不平衡的二叉树...
二叉树的应用二叉树的应用二叉树的应用二叉树的应用二叉树的应用二叉树的应用二叉树的应用
平衡二叉树c++模版,此模版採用二叉链表实现,是本人一个通宵搞出来的。可以提供时间复杂度在nlgn的排序,也可以提供lgn的查询。是一个很不错的数据结构,可是以和其它的现在比较新的一些数据结构比美。虽然有人对其...
C语言编写的 数据结构 平衡二叉树 演示、含课程设计报告 多种输出平衡二叉树格式
利用平衡二叉树实现一个动态查找表。 (1)实现动态查找表的三种基本功能:查找、插入和删除。 (2)初始时,平衡二叉树为空树,操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。在查找...
(1) 构建一个平衡二叉树并实现创建、插入、查找、删除、销毁等操作。每种操作均提示输入关键字。每次插入或删除一个结点后,更新平衡二叉树的显示。 (2) 平衡二叉树的显示采用凹入表现形式。 (3)输入的...
二叉树和平衡二叉树(B树)的C#实现源码 二叉树和平衡二叉树(B树)的C#实现源码 二叉树和平衡二叉树(B树)的C#实现源码
平衡二叉树课程设计 平衡二叉树课程设计 平衡二叉树课程设计
数据结构课程设计--二叉树遍历及其应用、对树的先序遍历、后序遍历、中序遍历、层序遍历、二叉树的深度及其叶子树、并打印树形。
平衡二叉树操作的演示的课程设计,包附加的功能。
平衡二叉树,平衡二叉树各种操作
1. 利用平衡二叉树实现一个动态查找表,实现动态查找表的三种基本功能:查找 插入和删除。 2 .初始,平衡二叉树为空树,操作界面给出查找,插入和删除三种操作供 选择,每种操作均要提示输入关键字,每次插入或删除...
AVL管理数据 struct branch{ unsigned int data; /* actual data */ struct branch * l_chld, * r_chld; /* left & right child */ short bc; /* balance coefficient */ }; ...#define avl_entry (T, P, M) (T *)(...
广工数据结构课程设计——平衡二叉树操作的演示 内含源代码、可执行程序以及相应的说明文档 实验的功能包括: [实现提示] (1) 初始,平衡二叉树为空树,操作界面给出查找、插入和删除三种操作供选择。每种操作均要...
平衡二叉树时间复杂度计算1
2015广工数据结构实验--平衡二叉树(包含源码和实验报告
平衡二叉树实现代码
C语言使用递归创建一颗平衡二叉树的源代码文件