VL树（平衡二叉查找树）
1. 前提条件

先回忆 BST：

左子树 < 根

右子树 > 根

例如：

        8
       / \
      4   10
     / \    \
    2   6    12

查找：

O(log n)

很快。

但是 BST 有个问题。

如果插入：

1
2
3
4
5

会变成：

1
 \
  2
   \
    3
     \
      4
       \
        5

已经不是树了。

变成：

链表

查找：

O(n)

退化了。

所以提出：

AVL Tree
2. 核心概念

AVL：

平衡二叉查找树

Balanced Binary Search Tree

AVL首先是BST。

所以仍然满足：

左小右大

同时增加要求：

任何结点

左右子树高度差

不能超过1

例如：

合法：

      4
     / \
    2   6

左高度：

1

右高度：

1

高度差：

0

合法。

再例如：

      4
     /
    2
   /
  1

左高度：

2

右高度：

0

高度差：

2

不合法。

3. 平衡因子 BF

AVL最重要概念。

定义：

BF

=

左子树高度

-

右子树高度

例如：

      4
     / \
    2   6

左右高度：

1

1

所以：

BF = 1-1 = 0

再例如：

      4
     /
    2

高度：

左=1

右=0

所以：

BF = 1

AVL允许：

BF=-1

BF=0

BF=1

不允许：

BF=2

BF=-2
4. AVL为什么快

AVL始终保持：

接近平衡

所以高度不会太大。

BST最坏：

高度=n

AVL：

高度≈log₂n

因此：

查找 O(log n)

插入 O(log n)

删除 O(log n)
5. AVL什么时候失衡

插入新节点以后。

例如：

插入：

30
20
10

得到：

    30
   /
 20
 /
10

看30：

左高度=2

右高度=0

所以：

BF=2

失衡。

此时需要：

旋转
6. AVL四种失衡

考试必考。

只有四种。

LL
      30
     /
   20
   /
 10

特点：

左孩子的左边插入

口诀：

LL

右旋
RR
10
 \
 20
  \
  30

特点：

右孩子的右边插入

口诀：

RR

左旋
LR
      30
     /
   10
     \
      20

特点：

左孩子的右边插入

口诀：

LR

先左旋

再右旋
RL
10
  \
   30
   /
 20

特点：

右孩子的左边插入

口诀：

RL

先右旋

再左旋
7. AVL判断口诀

考试最快方法。

发现：

BF=2

说明左边太高

再看：

新增结点

在左孩子左边？

还是左孩子右边？

如果：

左孩子左边

就是：

LL

如果：

左孩子右边

就是：

LR

同理：

BF=-2

说明：

右边太高

看新增结点：

右孩子右边

RR

或者：

右孩子左边

RL
8. AVL结构体

一般和BST一样。

struct TreeNode
{
    int val;

    struct TreeNode* left;

    struct TreeNode* right;

    int height;
};

新增：

height

记录高度。

9. AVL为什么需要height

因为要算：

BF

而：

BF

=

左高度

-

右高度

所以每个节点都保存：

height

方便计算。

10. 易错点
易错点1

AVL首先是BST

仍然满足：

左小右大

不要忘。

易错点2

AVL不是完全平衡树

允许：

BF=1

BF=0

BF=-1

不是：

必须相等
易错点3

失衡只会有四种：

LL

RR

LR

RL

考试看到图先判断类型。

易错点4

双旋转别背反

口诀：

LR

先左后右

RL

先右后左
AVL总结（考试版）
AVL树

定义：

平衡二叉查找树

--------------------------------

首先是BST：

左子树 < 根

右子树 > 根

--------------------------------

平衡因子：

BF

=

左高度

-

右高度

--------------------------------

合法：

BF=-1

BF=0

BF=1

--------------------------------

失衡：

BF=2

BF=-2

--------------------------------

四种失衡：

LL

RR

LR

RL

--------------------------------

对应旋转：

LL

右旋

----------------

RR

左旋

----------------

LR

左旋+右旋

----------------

RL

右旋+左旋

--------------------------------

复杂度：

查找 O(log n)

插入 O(log n)

删除 O(log n)