Question

什么是AVL树呢？数据结构里面的内容

Answer 1

首先得说一下，二叉搜索树

二叉搜索树除了满足二叉树的性质，还满足自身的一个特性

所有左子树的节点都比根节点的值小，所有右子树节点的值都比根结点值大

而这个定义是递归定义的，左子树的左子树所有点比左子树根小，左子树的右子树比左子树的根大，对于每一棵子树都是这样

这样在查询一个数的时候，可以每次根据根的信息决定左走还是右走

如果树是随机树，那么树高在log级别，可以基本保证每次查询都是logn的复杂度

但是很多情况下，树会变成链状或近似链状

这样每次查询可能会平均走到树一半的位置，效率就不尽人意了

为了防止这种情况的发生，就出现了AVL树，他通过控制每个节点的两个子树的高度，使他们的差很小，来保证树高在log级别，这样效率和稳定性得以提升，这就是AVL树，具体如何实现，你书上还会讲的

Answer 2

在计算机科学中，AVL树是最先发明的自平衡二叉查找树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 "An algorithm for the organization of information" 中发表了它。
高度为 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 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。