文档章节

数据结构-自平衡二叉查找树(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
2018/08/26
0
0
二叉查找树,红黑树,AVL树,B~/B+树(B-tree),伸展树——优缺点及比较

本文转载自:http://blog.csdn.net/bytxl/article/details/40920165 二叉查找树(Binary Search Tree) BST 的操作代价分析: (1) 查找代价: 任何一个数据的查找过程都需要从根结点出发,沿某...

亮亮-AC米兰
2017/01/17
0
0
数据结构之Tree

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

晨曦之光
2012/03/09
182
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

没有更多内容

加载失败,请刷新页面

加载更多

阿里大规模数据中心性能分析

郭健美,阿里巴巴高级技术专家,目前主要从事数据中心的性能分析和软硬件结合的性能优化。CCF 系统软件专委和软件工程专委的委员。曾主持国家自然科学基金面上项目、入选上海市浦江人才计划A...

阿里云官方博客
36分钟前
1
0
Coding and Paper Letter(四十四)

资源整理。 1 Coding: 1.Rstudio2019年会“机器学习应用”的幻灯片,代码和数据 rstudio conf 2019 2.R语言包sparkxgb,Spark上XGBoost的R接口。 sparkxgb 3.自动SQL注入和数据库接管工具。 ...

胖胖雕
38分钟前
1
0
Ubuntu最新的主要操作系统放弃32位支持?

现在是2018年,2019年即将到来——64位处理器已经成为主流很长一段时间了。如果你仍然使用32位的电脑,那么是时候把它扔进垃圾箱了。 我为所有基于Linux的操作系统维护者感到自豪,他们有勇气...

Linux就该这么学
39分钟前
1
0
Fundebug发布Vue插件,简化BUG监控接入代码

摘要: 代码越短越好! 我们发布了fundebug-vue插件,可以简化Vue框架接入Fundebug的代码。 Vue如何接入Fundebug 1. 安装fundebug-javascript与fundebug-vue npm install fundebug-javascrip...

Fundebug
46分钟前
1
0
MySQL学习笔记之二

数据库的操作总结就是:增删改查(CURD),今天记录一下基础的检索查询工作。 检索MySQL 1.查询表中所有的记录 mysql> select * from apps;+----+------------+-----------------------+------...

凌宇之蓝
57分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部