什么是 AVL 树?

栏目: 编程工具 · 发布时间: 5年前

内容简介:前面我们有学过 BST(二分搜索树),它唯一的不足是,当数据像 1-2-3-4-5 这样的时候,查询性能与单链表一致,无法发挥出 BST 的优势。在下面的 BST 中查找 4 这个节点,只能逐个查找。为了解决 BST 性能问题。1962 年 G. M.

前面我们有学过 BST(二分搜索树),它唯一的不足是,当数据像 1-2-3-4-5 这样的时候,查询性能与单链表一致,无法发挥出 BST 的优势。在下面的 BST 中查找 4 这个节点,只能逐个查找。

什么是 AVL 树?

为了解决 BST 性能问题。1962 年 G. M. A delson- V elsky 和 E. M. L andis 在他们的论文《An algorithm for the organization of information》中提到了一种方法可以解决这个问题。它就是 AVL 这种数据结构,AVL 由两位发明者的姓名首字母命名。

AVL 树需要满足两个条件:

  1. 是一颗 BST;

  2. 所有节点的左子树高度与右子树高度差的绝对值不能大于 1;

为了满足第2个条件,需要 AVL 树的节点记录其高度和平衡因子(左子树高度与右子树高度差)。通俗地讲,AVL是一颗可以自平衡的 BST,也就是说当有新的节点插入后,一但破坏了第二个条件,就需要调整平衡性让其满足第二个条件。采用的方式有两种:左旋转和右旋转。

我们先看一颗 AVL 树:

什么是 AVL 树?

上面这课二叉树满足 AVL 树的条件,如果插入元素 1,它将失去平衡性,3,4,5 这几个节点的平衡因子为 2,不满足 AVL 树的第二个条件,看图:

什么是 AVL 树?

有两种方式可以解决这种不平衡性:右旋转和左旋转。我们下节内容将探讨这两个概念。

大家加油!!!

推荐阅读:

二分搜索树 BST(Binary Search Tree)

使用 Swift 实现一颗二分搜索树

图解数据结构和算法

什么是 AVL 树?


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

创业时代

创业时代

付遥 / 中信出版社 / 2015-7 / 39.8元

香港人郭鑫年酷爱赛车,在驾车穿越隧道的时候,因为收发短信发生意外,他从被撞得破烂的车里爬出来时,兴奋地高喊:我有一个伟大的想法,手机上的对讲机,将要改变世界!他随即辞职来到北京,开始艰难的创业历程。 移动技术迅猛发展,正在颠覆互联网行业,郭鑫年误打误撞,对讲机用户数量急增,竟成为移动互联网的明星,他也因此置身于风口浪尖。三大互联网巨头为了抢夺手机入口大打出手,无不希望争夺这张通往未来移动市场......一起来看看 《创业时代》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器