内容简介：前面我们有学过 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 树的第二个条件，看图：
有两种方式可以解决这种不平衡性：右旋转和左旋转。我们下节内容将探讨这两个概念。
大家加油！！！
推荐阅读：
图解数据结构和算法
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
