文档章节

数据结构-自平衡二叉查找树(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
朝阳
程序员
私信 提问
MySQL索引结构采用B+树的原因

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

edwardGe
08/26
0
0
java集合框架(四):TreeMap

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

chenzanjin
2017/11/07
0
1
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树)

前言 推出一个新系列,《看图轻松理解数据结构和算法》,主要使用图片来描述常见的数据结构和算法,轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等...

超人汪小建
08/09
0
0
学习数据结构 二叉查找树(binary search tree)

为学习 LLVM 的 ImmutableSet,其底层的实现选择为 AVL 树(平衡二叉搜索树),我不很熟悉该树,虽然大致知道但毕竟不精,因此还是先学习学习二叉搜索树吧。 二叉搜索树或叫做二叉查找树,可...

刘军兴
2012/03/16
0
2

没有更多内容

加载失败,请刷新页面

加载更多

Nginx 内置请求参数

nginx内置变量 内置变量存放在 ngx_http_core_module 模块中,变量的命名方式和apache 服务器变量是一致的。总而言之,这些变量代表着客户端请求头的内容,例如$http_user_agent, $http_coo...

大木老师故事的小黄花
昨天
2
0
我为什么坚持写作

说写作可能是抬高了自己,目前来说只能是写东西、记录东西、表达观点和情感。 在俞敏洪的公众号上看到过一篇文章,里面讲了一个观点,大概是说写作不求能写出伟大的作品,只是把自己的生活、...

Bob2100
昨天
3
0
中国公有云三巨头,同时支持Rancher Kubernetes平台

华为云容器引擎(CCE)、阿里云K8S容器服务(ACK)和腾讯云K8S引擎(TKE),中国公有云三巨头正式全面支持Rancher Kubernetes平台。 Rancher正式宣布扩大对中国领先Kubernetes服务的支持,华...

RancherLabs
昨天
1
0
【NLP】【八】基于keras与imdb影评数据集做情感分类

【一】本文内容综述 1. keras使用流程分析(模型搭建、模型保存、模型加载、模型使用、训练过程可视化、模型可视化等) 2. 利用keras做文本数据预处理 【二】环境准备 1. 数据集下载:http:...

muqiusangyang
昨天
3
0
nginx 解决session一致性

session 粘滞性 每个请求按访问ip的hash结果分配,这样每个访客固定访问一个后端服务器,可以解决session的问题。 upstream backserver {ip_hash;server 192.168.0.14:88;server 192.1...

zhu_kai1
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部