文档章节

数据结构-自平衡二叉查找树(AVL)详解

fengsehng
 fengsehng
发布于 2016/11/09 09:12
字数 1491
阅读 0
收藏 0

介绍:

在计算机科学中,AVL树是最先发明的自平衡二叉查找树。

在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。

查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis,他们在 1962 年的论文 “An algorithm for the organization of information” 中发表了它。

特点:

AVL树本质上还是一棵二叉搜索树,它的特点是:

1.本身首先是一棵二叉搜索树。

2.带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。

也就是说,AVL树,本质上是带了平衡功能的二叉查找树(二叉排序树,二叉搜索树)。

节点数:

高度为 h 的 AVL 树,节点数 N 最多2^h − 1; 最少N(h)=N(h− 1) +N(h− 2) + 1。

最少节点数n 如以斐波那契数列可以用数学归纳法证明:
即:
N(0) = 0 (表示 AVL Tree 高度为0的节点总数)
N(1) = 1 (表示 AVL Tree 高度为1的节点总数)
N(2) = 2 (表示 AVL Tree 高度为2的节点总数)
N(h)=N(h− 1) +N(h− 2) + 1 (表示 AVL Tree 高度为h的节点总数)

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

操作:

假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a(即a是离插入点最近,且平衡因子绝对值超过1的祖先结点),

则失去平衡后进行进行的规律可归纳为下列四种情况:

单向右旋平衡处理LL:

由于在*a的左子树根结点的左子树上插入结点,*a的平衡因子由1增至2,致使以*a为根的子树失去平衡,则需进行一次右旋转操作;

单向左旋平衡处理RR:

由于在*a的右子树根结点的右子树上插入结点,*a的平衡因子由-1变为-2,致使以*a为根的子树失去平衡,则需进行一次左旋转操作;

双向旋转(先左后右)平衡处理LR:

由于在*a的左子树根结点的右子树上插入结点,*a的平衡因子由1增至2,致使以*a为根的子树失去平衡,则需进行两次旋转(先左旋后右旋)操作。

双向旋转(先右后左)平衡处理RL:

由于在*a的右子树根结点的左子树上插入结点,*a的平衡因子由-1变为-2,致使以*a为根的子树失去平衡,则需进行两次旋转(先右旋后左旋)操作。

图解二叉树的操作:

1.左旋

这里写图片描述

2.右旋:

这里写图片描述

avl的插入操作:(邪恶脸)

1.单方向:

这里写图片描述

以节点5为基准进行右旋:

这里写图片描述

总结:

对于这种一个方向的,只需要一次操作,这是孩子都在左边的情况,对于孩子都在右边的情况,(5,8,10),以5为基准,进行一次左旋

2.双方向:

这里写图片描述

不是一个方向,进行两次操作,先转化为1的情况,再次旋转 ,显示3为基准,左旋,5为基准右旋,先左后右边

这里写图片描述

总结:

对于这种不一个方向的情况,需要两次操作,先转化为1的情况,对称的情况是先右后左。

删除操作:

从AVL树中删除可以通过把要删除的节点向下旋转成一个叶子节点,接着直接剪除这个叶子节点来完成。因为在旋转成叶子节点期间最多有 log n个节点被旋转,而每次 AVL 旋转耗费恒定的时间,删除处理在整体上耗费 O(log n) 时间。

查找:

在AVL树中查找同在一般BST完全一样的进行,所以耗费 O(log n) 时间,因为AVL树总是保持平衡的。不需要特殊的准备,树的结构不会由于查询而改变。(这是与伸展树查找相对立的,它会因为查找而变更树结构。)

时间复杂度分析:

在树, 二叉树, 二叉搜索树中提到,一个有n个节点的二叉树,它的最小深度为log(n),最大深度为n。比如下面两个二叉树:

深度为n的二叉树

这里写图片描述

深度为log(n)的二叉树

这里写图片描述

分析:

二叉搜索树的深度越小,那么搜索所需要的运算时间越小。一个深度为log(n)的二叉搜索树,搜索算法的时间复杂度也是log(n)。然而,我们在二叉搜索树中已经实现的插入和删除操作并不能让保持log(n)的深度。如果我们按照8,7,6,5,4,3,2,1的顺序插入节点,那么就是一个深度为n的二叉树。那么,搜索算法的时间复杂度为n。

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧,都是干货!

微信订阅号二维码如下:

这里写图片描述

参考

http://baike.baidu.com/view/671745.htm
http://www.cnblogs.com/vamei/archive/2013/03/21/2964092.html

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
java集合框架(四):TreeMap

TreeMap的数据结构与HashMap、LinkedHashMap不同,其整个结构就是一颗红黑树,所以我们要研究TreeMap就得先从红黑树开始。对于红黑树的算法,我在本文章不详细展开,有兴趣的同学可以点击这里...

chenzanjin
2017/11/07
0
1
MySQL索引结构采用B+树的原因

今天看了好多关于MySQL索引的文章,对MySQL的索引结构采用B+树的原因进行梳理。 首先来回顾一下数据结构课程中学过的一些树的结构。 一、二叉查找树 1.1 性质 任意节点左子树不为空,则左子树...

edwardGe
08/26
0
0
数据结构之Tree

数据结构和数据的关系,就如同水和盛水的器皿一样, 比如: 消防员会选择用消防水栓装水,原因是他需要处理高压大量的水,解救火灾;茶馆的伙计会用茶壶, 茶壶受热均匀,煮出的茶才韵味无穷...

晨曦之光
2012/03/09
154
0
JDK TreeMap Red-Black Tree

介绍另一种平衡二叉树:红黑树(Red Black Tree),红黑树由Rudolf Bayer于1972年发明,当时被称为平衡二叉B树(symmetric binary B-trees),1978年被Leonidas J. Guibas 和 Robert Sedgewi...

zuoer
2011/12/18
0
0
堆,AVL树,红黑树以及优先级队列

声明:本文完全没有定量分析,需要定量分析的,请随便查阅一本数据结构的书籍或网页。 二叉堆:拥有删除最大(小)权值节点以及插入任意节点操作,是一颗完全二叉树,其完全性由插入和删除动...

晨曦之光
2012/04/10
505
0

没有更多内容

加载失败,请刷新页面

加载更多

docker update:更新一个或多个容器的配置

更新容器的配置 docker update:更新一个或多个容器的配置。 具体内容请访问:https://docs.docker.com/engine/reference/commandline/update/#options 语法:docker update [OPTIONS] CONTA...

lwenhao
今天
1
0
unload事件

unload事件不触发的原因分析 1.代码位置不对,应该优先加载,不能放到回调函数中 2.浏览器不支持 3.最可能的原因,unload事件中触发的函数是一个异步执行的函数,浏览器是不允许在窗口关闭之后在...

狮子狗
今天
1
0
DbForge Schema Compare for MySQL入门教程:如何连接到数据库

【dbForge Schema Compare for MySQL下载】 要创建连接: 1. 在“Connection” 工具栏上单击“New Connection”按钮 。 2. 在“Host” 框中输入主机名。 3. 在“Port” 框中输入端口信息。默...

Miss_Hello_World
今天
1
0
spring中事务的应用

spring中事务管理的两种方式 编程式事务使用TransactionTemplate或者直接使用底层的PlatformTransactionManager。对于编程式事务管理,spring推荐使用TransactionTemplate。 声明式事务是建立...

狂奔的熊二
今天
0
0
公众号关联微信小程序

公众号关联小程序发送关联通知,对于推广小程序有着很大的帮助。所以问题来了,怎么做到在公众号关联小程序发送关联通知呢? 一:开发中遇到的问题 之前在开发过程中发现,公众号已经关联小程...

Code辉
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部