4.5.2 平衡二叉树

1、平衡二叉树的定义

为了避免树的高度增长过快,降低二叉排序树的性能,我们规定在插入和删除二叉树结点时,要保证任意结点的左、右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树,简称平衡树(AVL树)。定义结点左子树和右子树的高度差为该结点的平衡因子,则平衡二叉树结点的平衡因子的值只可能是-1、0或1。

因此平衡二叉树可定义为它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的高度差的绝对值不超过1.

2、平衡二叉树的插入

二叉排序树保证平衡的基本思想:每当在二叉树中插入(或删除)一个结点时,首先要检查其插入路径上的结点是否因为此次操作而导致了不平衡。如果导致了不平衡,则先找到插入路径上离结点最近的平衡因子绝对值大于1的结点A,再对以A为根的子树,在保持二叉排序树特性的前提下,调整各结点的位置关系,使之重新达到平衡。

注意:每次调整的对象都是最小不平衡子树,即在插入路径上离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树

平衡二叉树的插入过程前半部分与二叉排序树相同,但是在新结点插入后,如果造成了查找路径上不再平衡,需要做出相应的调整。一般可将失去平衡后进行调整的规律归纳为以下4种情况: 1)LL平衡旋转(右单旋转)

由于在结点A的左孩子(L)的左子树(L)上插入了新结点,A的平衡因子由1增至2,导致以A为根的子树失去平衡,需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A称为根结点,将A结点向右下旋转称为B的右子树的根结点,则B的原右子树则作为A结点的左子树。

2)RR平衡旋转(左单旋转)

由于在结点A的右孩子(R)的右孩子(R)上插入新结点,A的平衡因子由-1减至-2,导致以A为根的子树失去平衡,需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点,将A结点向左下旋转成为B的左子树的根结点,而B的原左子树则称为A结点的右子树。

3)LR平衡旋转(先左后右双旋转)

由于在A的左孩子(L)的右子树(R)上插入新结点,A的平衡因子由1增至2,导致以A为根的子树失去平衡,需要进行两次旋转操作,先左旋转后右旋转。现将A结点的左孩子B的右子树的根结点C向上旋转提升到B结点的位置,然后再把该C结点向右上旋转提升到A结点的位置。

4)RL平衡旋转(先右后左双旋转)

由于在A的右孩子(R)的左子树(L)上插入新结点,A的平衡因子由-1减至-2,导致以A为根的子树失去平衡,需要进行两次旋转操作,先右旋转后左旋转。现将A结点的右孩子B的左子树的C向右上旋转提升到B的位置,然后再把该C结点向左上旋转提升到A结点的位置。

3、平衡二叉树的查找

在平衡二叉树上进行查找的过程和二叉排序树相同,因此,在查找的过程中和给定值进行比较的关键字的个数不超过树的深度。

假设以Nh表示深度为h的平衡树中含有最少的结点树。显然N0=0,N1=1,N2=2,并且有Nh=N(h-1)+N(h-2)+1.

可以证明,含有n个结点的平衡二叉树的最大深度为O(log2 n).因此平衡二叉树的平均查找长度为O(log2 n)。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

每周学点大数据 | No.24二叉搜索树回顾(一)

No.24期 二叉搜索树回顾(一) Mr. 王:接下来我们谈一谈外存查找结构。内存中的查找结构最典型的就是二查搜索树了。这里我们先来简单地认识一下关于二叉树...

36850
来自专栏kevindroid

leetcode110 Balanced Binary Tree

16150
来自专栏赵俊的Java专栏

平衡二叉树

23850
来自专栏小文博客

小文’s blog — 平衡二叉树构造方法

11530
来自专栏从流域到海域

校招必考:根据二叉树遍历序列确定二叉树

根据二叉树的前序遍历和中序遍历求其后序遍历或者根据二叉树的后序遍历和中序遍历求其前序遍历是腾讯等校招的必考题,下面我们就来分析一下解题思路。 这道题本质上...

24650
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题39二叉树的深度

题目:输入一颗二叉树的根结点,求该树的深度。从根结点到叶结点一次经过的结点形成树的一条路径,最长路径的长度为树的深度。 分析:本题是一道典型的“分治法”。要...

33350
来自专栏机器学习从入门到成神

数据结构之树、森林和二叉树的转换

树转换为二叉树 (1)加线。在所有兄弟结点之间加一条连线。 (2)去线。树中的每个结点,只保留它与第一个孩子结点的连线,删除它与其它孩子结点之间的连线。...

21120
来自专栏开发与安全

数据结构:树的定义和基本概念

一、树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中:(1)有且仅有一个特定的称为根(root)的结点。 (2)当n>1时,其...

21180
来自专栏编程理解

数据结构(四):平衡二叉树(AVL树)

。影响时间复杂度的因素即为二叉树的高,为了尽量避免树中每层上只有一个节点的情况,这里引入平衡二叉树。

67830
来自专栏WD学习记录

哈夫曼树(Huffman Tree)

给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带...

25040

扫码关注云+社区

领取腾讯云代金券