平衡二叉树之AVL树

平衡二叉树之AVL树

AVL树是最先发明的自平衡二叉查找树。AVL树以其发明者前苏联学者 G.M. Adelson-Velsky 和 E.M. Landis 名字而命名,他们在1962年的论文《An algorithm for the organization of information》中发表了它。

AVL树中,一个非常重要的概念为平衡因子(Balance factor),对于任意节点 x ,其平衡因子定义为该节点右子树和左子树高度差,即 bf(x)=h(x-right)-h(x-left)。

带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的,并需要重新平衡这个树。平衡因子可以直接存储在每个节点中,或从可能存储在节点中的子树高度计算出来。

1. AVL树数据结构

为了方便计算每个节点的平衡因子,对二叉树的数据结构进行修改,增加一个数据单元用于记录以该节点为root的子树高度,重新定义数据结构如下(代码采用C实现):

2. AVL树旋转操作

AVL在插入和删除节点造成不平衡的时候需要对发生不平衡的节点及时调整,调整方法为旋转操作。根据造成不平衡的节点出构型可分为:LL 、RR 、LR 、RL型,对应的操作则为单旋和双旋,下面分析一下各种构型具体操作方法。

下图所示为LL构型,在B节点的左子树上插入节点导致A节点失衡,调整过程为:以B节点为轴心,A节点顺时针旋转至B的右子树,A的右子树又B的右子树代替。通过右旋操作,返回以B为Root的平衡子树。 RR够型和LL够型成对称关系,操作方向相反,此处就省略了。

下图所示为LR构型,在B节点的右子树上插入新节点导致A节点失衡,调整过程分两个步骤:首先以C为轴心,B绕C逆时针旋转,生成的子树作为A的左子树;这样就变化成了LL型,然后用上图所示的方法调整即可。通过先左旋后右旋,返回以C为Root的平衡子树。RL型和LR型呈对称状,此处也省略。

下表列出节点够型和选择操作关系。

构型

操作

对应的函数

LL型

单旋:右旋

RR型

单旋:左旋

LR型

双旋:先左旋后右旋

RL型

双旋:先右旋后左旋

3. 插入节点

向AVL树中插入节点后,要判断是否引起失衡,如果失衡则需要进一步确定构型,选择合适的基本旋转操作来调整。


4. 删除节点

从AVL树中删除节点分为两个步骤:首先删除节点;然后调整平衡。删除操作对应为插入操作的逆向操作,调整平衡的时候也需要确定被删除节点的分支构型来选择合适的旋转方法。

5. 测试

分别对 查找二叉树 和 AVL树进行下列操作:依次插入 0-15 ;依次删除 0, 3,6,10,15。测试结果如下:

对比来看, 查找二叉树退化为线性,而AVL树则形态匀称。

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2017-08-22

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法工程师

红黑树算法

前情提要 红黑树是AVL树里最流行的变种,有些资料甚至说自从红黑树出来以后,AVL树就被放到博物馆里了。红黑树是否真的有那么优秀,我们一看究竟。红黑树遵循以下...

39012
来自专栏数据结构与算法

BZOJ3732: Network(Kruskal重构树)

$n \leqslant 15000, m \leqslant 30000, k \leqslant 20000$

934
来自专栏Duncan's Blog

红黑树学习

1.红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色.并且有如下性质:

881
来自专栏文武兼修ing——机器学习与IC设计

AVL二叉树AVL二叉查找树

AVL二叉查找树 AVL二叉查找树是一种特殊的二叉查找树,其规定 每个节点的左子树和右子树的高度差最多是1 AVL调整算法 AVL树插入一个新的节点到某个...

2384
来自专栏大数据和云计算技术

算法基础8:平衡树之红黑树

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第8篇《平衡查找树概述》,非常赞!希望对大家有帮助,大家会喜欢! 前面系列文章: 归并排序 #算法...

3265
来自专栏数据结构与算法

二分图相关定理

定义:若选择一个点说明选择与它相连的所有边,最小顶点覆盖就是选择最少的点来覆盖所有的边。

1053
来自专栏数值分析与有限元编程

可视化 | Tecplot作三角形单元后处理工具

对于有限元分析的后处理,除了单的信息,还包括单元信息,比如一个单元由哪些结点组成。Tecplot可以处理的单元类型有三角形单元,四边形单元,四面体单元和六面体单...

3674
来自专栏xingoo, 一个梦想做发明家的程序员

AVL树

详细描述,好像跟我自己写的差不多......不过终究是大神级别,讲的就是透彻 1. 概述 AVL树是最早提出的自平衡二叉树,在AVL树中任何节点的两个子树的高度...

2468
来自专栏mukekeheart的iOS之旅

哈夫曼树和哈夫曼编码

  在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛,如JP...

3479
来自专栏灯塔大数据

每周学点大数据 | No.27高维外存查找结构——KD 树

No.27期 高维外存查找结构——KD 树 Mr. 王:以往我们在数据结构中进行的查找,都是查找某一个键值或者某一个区间内的值,这样的查找称之为一维查...

3698

扫码关注云+社区