内容简介：前面我们有学过 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 树的第二个条件，看图：
有两种方式可以解决这种不平衡性：右旋转和左旋转。我们下节内容将探讨这两个概念。
大家加油！！！
推荐阅读：
图解数据结构和算法
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
现代前端技术解析
张成文 / 电子工业出版社 / 2017-4-1 / 79.00元
这是一本以现代前端技术思想与理论为主要内容的书。前端技术发展迅速，涉及的技术点很多，我们往往需要阅读很多书籍才能理解前端技术的知识体系。《现代前端技术解析》在前端知识体系上做了很好的总结和梳理，涵盖了现代前端技术绝大部分的知识内容，起到一个启蒙作用，能帮助读者快速把握前端技术的整个脉络，培养更完善的体系化思维，掌握更多灵活的前端代码架构方法，使读者获得成为高级前端工程师或架构师所必须具备的思维和能......一起来看看 《现代前端技术解析》 这本书的介绍吧!
