平衡二叉树 （AVL）

基本信息

平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree），又被称为 AVL 树。即它首先是一棵二叉搜索树，其次它具有平衡的特殊性质。

AVL 树得名于它的发明者格奥尔吉·阿杰尔松-韦利斯基 Adelson-Velskii和叶夫根尼·兰迪斯 Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。

性质

AVL 树相比于普通的二叉搜索树有两个重要性质：

• 其左右子树的高度差的绝对值不超过1。
• 左右子树都是平衡二叉树

例如上图中只有第一棵树是AVL树，第二棵树的两个节点的高度差为2不满足条件一，第三颗树的黄色节点对应的子树不是平衡二叉树不满足条件二，故整棵树不是平衡二叉树。

二叉搜索树 （BST）

要想明白为什么要有平衡二叉搜索树，就要先搞懂什么是二叉搜索树。

性质

二叉搜索树也叫做有序二叉树（ordered binary tree）、排序二叉树（sorted binary tree）。

它的性质如下：

• 任意节点的左子树上的所有节点的值都小于该节点，右子树上的所有节点值都大于该节点。
• 任意节点上子树都是二叉搜索树。

如图即为一棵二叉搜索树。

查找

因为该树为一棵排序树，所以在查找时的算法如下：

• 若 root 为空，返回 null。
• 若 root 的权值等于 value，返回该节点。
• 若 root 的权值大于 value，在 root 的左子树中继续搜索。
• 若 root 的权值小于 value，在 root 的右子树中继续搜索。

故在理想情况下（二叉树相对饱满平衡），是二分查找的复杂度：O(log n)

但倘若是下面这种情况，二叉树完全不平衡时：

查找的时间复杂度就和链表一致了：O(n)

这种不平衡就是在搜索二叉树的节点逐一插入的过程中出现的。若能使插入的过程二叉树仍能保持平衡，那么对于查找效率来说仍然是≈*O(log n)*的。

于是就有了平衡二叉树。

调整平衡

四种破坏平衡的情况

• LL 型：左孩子的左子树过长导致平衡性破坏。
• LR 型：右孩子的右子树过长导致平衡性破坏。
• LR 型：左孩子的右子树过长导致平衡性破坏。
• RL 型：右孩子的左子树过长导致平衡性破坏。

对应的调整平衡的方式

1. LL 型：右旋节点 T

2. RR 型：左旋节点 T

3. LR 型：先左旋节点 L，成为 LL 型，再右旋节点 T。

4. RL 型：先右旋节点R，成为RR 型，再左旋节点T。