平衡二叉树的插入

平衡二叉树的插入平衡二叉树的概念:在学习二叉排序树的查找时,通过分析查找算法的效率可知,不同结构的二叉排序树查找效率有很大的不同,单支树的查找效率相当于顺序查找,而越趋于平衡的二叉排序树查找效率越高。因此,在二叉排序树的基础上引进了平衡二叉树。所谓平衡二叉树是指它除了具备二叉排序树的基本特性之外,还具有一个非常重要的特点:它的左子树与右子树的深度之差(平衡因子)的绝对值不超过1,且都是平衡二叉树。二叉…

平衡二叉树的概念:


在学习二叉排序树的查找时,通过分析查找算法的效率可知,不同结构的二叉排序树查找效率有很大的不同,单支树的查找效率相当于顺序查找,而越趋于平衡的二叉排序树查找效率越高。因此,在二叉排序树的基础上引进了平衡二叉树。

所谓平衡二叉树是指它除了具备二叉排序树的基本特性之外,还具有一个非常重要的特点:它的左子树与右子树的深度之差(平衡因子)的绝对值不超过1,且都是平衡二叉树。二叉树结点的左子树深度减去右子树深度的值称为平衡因子。那么平衡二叉树上的所有结点的平衡因子只可能是-1,0,1。只要二叉树上一个结点的平衡因子的绝对值大于1,那么该二叉树就不是平衡二叉树。

例如:这里写图片描述
平衡二叉树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法)。

平衡二叉树也可以进行查找,插入等操作,在进行查找操作时与二叉排序树相同且效率比二叉排序树高,如果平衡二叉树平衡度高,则相当于是顺序表中的折半查找。

但在执行插入操作时,要随时注意保持树的平衡性,在插入结点时,如果距离插入位置最近且平衡因子绝对值大于1,以此为根结点的子树称为最小不平衡子树。

平衡二叉树的插入:


在平衡二叉树中插入结点要随时保证插入后整棵二叉树还是平衡的,但是在插入结点的时候,会破坏二叉树的平衡性,会产生最小不平衡子树。因此,为了保证插入结点后二叉树仍是平衡的,就需要找出插入新结点后失去平衡的最小子树根结点。然后再调整这棵子树中有关结点之间的链接关系,使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后,其他所有不平衡子树无须调整,整个二叉排序树就又称为一棵平衡二叉树。调整结点之间的链接关系的基本方法就是旋转,也有书中称之为结点交换。

旋转的方法有右旋转,左旋转,左右旋转,右左旋转,接下来用一组数据构建一棵平衡二叉树,在构建过程中讲解如何用旋转来调整二叉树的平衡。

假设有一组数据int arr[10]={90,66,65,98,100,88,105,102,110,103};现要用这组数据来构建一棵平衡二叉树,以90为根结点,下一个数据66小于90,则为它的左孩子,此时两个结点构成的二叉树是一棵平衡二叉树;然后插入结点65,65小于66,则为66的左孩子。

结点左边是每个结点的平衡因子,当插入结点65后,结点90的平衡因子变为2,此树不再是平衡二叉树,那么为了保持树的平衡性,就要对树进行调整,即进行旋转。在进行旋转时也有一定的规则:在产生的最小不平衡子树的根结点及其左子树平衡因子都为正,即在最小不平衡子树根结点的左孩子的左孩子处插入结点,则以根结点的左孩子为支点进行右旋转。66为根结点90的左孩子,而结点65就是插入到了结点66的左孩子处,根结点90与左孩子结点66的平衡因子都同为正,因此要调整二叉树的平衡就以66为支点进行右旋转。

如图所示:前三个结点前三个结点

平衡二叉树的插入右旋转

旋转之后二叉树就变为以66为根结点,以65和90分别为左右孩子的平衡二叉树。

接着再插入结点98,则98会成为结点90的右孩子。

插入结点98之后并没有打破二叉树的平衡性,因此不需要调整。接下来再插入结点100,则100成为98的右孩子。

这里写图片描述
插入结点98和插入结点100

插入结点100后打破了二叉树的平衡性,产生的最小不平衡子树以90为根结点。此时要调整树的平衡性,但是此次插入结点在90右孩子的右孩子98处插入,结点90及其右孩子平衡因子都为负,因此需要左旋转。左旋转规则为:在产生的最小不平衡子树根结点右孩子的右孩子处插入结点,即最小不平衡子树的根结点及其右孩子的平衡因子都为负,则以根结点的右孩子为支点进行左旋转,将结点90变为其左孩子。
这里写图片描述

左旋转之后,结点98变为了66的右孩子,结点90变为了结点98的左孩子,整棵树又恢复了平衡。需要注意的是,如果插入结点不是98的右孩子而是其左孩子,例如插入的结点值为97。这样如果直接进行简单的左旋转,则97会变成98的右孩子,就不符合二叉排序树的性质,因此不能简单地直接左旋转。
这里写图片描述

仔细观察会发现结点90与结点结点98的平衡因子符号不同,因此不能简单旋转。在旋转之前可以先将两者符号统一,先对结点98与97进行右旋转,使98成为97的右孩子。这里写图片描述

这样就与二叉平衡性一样,此时可以直接进行左旋转。
左旋转
此处为将100用97替换所出现的情况,如果在插入过程中出现平衡因子符号不同的情况,读者也要知道如何处理。

接下来插入结点88之后,则88会成为90的左孩子。
这里写图片描述
插入结点88之后,也打破了树的平衡性。产生的最小不平衡子树以66为根结点。66的平衡因子为负,其右孩子98的平衡因子为正,两者的符号不同,因此旋转方式也会改变。先要取消平衡因子符号的差异,当产生的最小不平衡子树中,从根结点的插入路径为右->左->左时,先要以此根结点的右孩子的左孩子为支点进行旋转,然后再进行左旋转。在下图中,产生的最小不平衡子树以66为根结点,则从66到插入的结点88的路径就是右->左->左,那么就先绕结点90(它为根结点66右孩子的左孩子)进行右旋转。
这里写图片描述
经过右旋转之后,结点66与结点90的平衡因子符号相同,最小不平衡子树的根结点与其右子树的平衡因子因子都为负,按照规则绕结点90进行左旋转,结点66变为90的左孩子,结点88变为66的右孩子。
这里写图片描述
插入结点88,根据插入的位置及平衡因子先进行右旋转再进行左旋转,调整树的平衡。

接下来插入结点105,105为100的右孩子,生成的最小不平衡子树以98为根结点,根结点与其右孩子平衡因子同为负,则绕结点100进行左旋转来调整二叉平衡树。
这里写图片描述
接下来插入结点102,102为105的左孩子。
这里写图片描述
插入结点102后并没有破坏二叉树的平衡性。 继续插入结点110,110为105的右孩子。
这里写图片描述
插入结点110也没有破坏树的平衡性,因此不必要调整。接下来插入结点103,则103为102的右孩子。
这里写图片描述
插入结点103后,产生的最小不平衡子树以100为根结点,结点100的平衡因子为-2,结点105的平衡因子为1,平衡因子符号不统一。那么首先要消除平衡因子间符号的差异,绕结点102右旋转。
这里写图片描述
此时再绕结点102左旋转来调整树的平衡性。
这里写图片描述
经过左旋转后,得到右边的二叉树,它已经是平衡的,至此用这一组数据构建一棵平衡二叉树完成。

在构建的过程中插入结点时要随时保持树的平衡性,通过上面的学习可知,构建平衡二叉树大致就分为三种情况:插入结点后,如果最小不平衡子树根结点与其孩子平衡因子通为正,则直接右旋转;如果最小不平衡子树根结点与其孩子平衡因子通为正,则直接左旋转;如果最小不平衡子树根结点与其孩子平衡因子符号不同,则先对孩子结点进行旋转,使平衡因子符号无差异,再进行反向旋转。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/35930.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注