内容简介：前面我们有学过 BST（二分搜索树），它唯一的不足是，当数据像 1-2-3-4-5 这样的时候，查询性能与单链表一致，无法发挥出 BST 的优势。在下面的 BST 中查找 4 这个节点，只能逐个查找。为了解决 BST 性能问题。1962 年 G. M.
前面我们有学过 BST（二分搜索树），它唯一的不足是，当数据像 1-2-3-4-5 这样的时候，查询性能与单链表一致，无法发挥出 BST 的优势。在下面的 BST 中查找 4 这个节点，只能逐个查找。
为了解决 BST 性能问题。1962 年 G. M. A delson- V elsky 和 E. M. L andis 在他们的论文《An algorithm for the organization of information》中提到了一种方法可以解决这个问题。它就是 AVL 这种数据结构，AVL 由两位发明者的姓名首字母命名。
AVL 树需要满足两个条件：
-
是一颗 BST；
-
所有节点的左子树高度与右子树高度差的绝对值不能大于 1；
为了满足第2个条件，需要 AVL 树的节点记录其高度和平衡因子（左子树高度与右子树高度差）。通俗地讲，AVL是一颗可以自平衡的 BST，也就是说当有新的节点插入后，一但破坏了第二个条件，就需要调整平衡性让其满足第二个条件。采用的方式有两种：左旋转和右旋转。
我们先看一颗 AVL 树：
上面这课二叉树满足 AVL 树的条件，如果插入元素 1，它将失去平衡性，3,4,5 这几个节点的平衡因子为 2，不满足 AVL 树的第二个条件，看图：
有两种方式可以解决这种不平衡性：右旋转和左旋转。我们下节内容将探讨这两个概念。
大家加油！！！
推荐阅读：
图解数据结构和算法
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
算法设计、分析与实现
徐子珊 / 2012-10 / 65.00元
《算法设计、分析与实现：c、c++和java》由徐子珊编著，第1章～第6章按算法设计技巧分成渐增型算法、分治算法、动态规划算法、贪婪算法、回溯算法和图的搜索算法。每章针对一些经典问题给出解决问题的算法，并分析算法的时间复杂度。这样对于初学者来说，按照算法的设计方法划分，算法思想的阐述比较集中，有利于快速入门理解算法的精髓所在。一旦具备了算法设计的基本方法，按应用领域划分专题深入学习，读者可以结合已......一起来看看 《算法设计、分析与实现》 这本书的介绍吧!
