一、背景

1、问题

例如：在 n 个动态的整数中搜索某个整数是否存在？

0	1	2	3	4	5	6	7	8	9
31	66	17	15	28	20	59	88	45	56

如果维护一个有序的动态数组，使用二分搜索，最坏时间复杂度：O（logn）

但是添加，删除的平均时间复杂度是O（n）

针对这个需求，有没有更好的方案？

使用二叉搜索树，添加，删除，搜索的最坏时间复杂度均可优化至：O（logn）

2、二叉搜索树

二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称为 BST，有如下特点：

• 任意一个节点的值都大于其左子树所有节点的值
• 任意一个节点的都小于其右子树所有节点的值
• 它的左右子树也是一颗二叉搜索树
• 二叉搜索树存储的元素必须具备可比性，如果是自定义类型，需要指定比较方式，不允许为 null

根据二叉搜索树的定义，如果是按照  7，4，9，2，5，8，11 顺序添加可以构造一颗完全二叉树。

如果是从从小到大或者从大到小添加节点，二叉搜索树树将会退化成链表。此外，删除节点也有可能会导致二叉搜索树退化成链表。

如何避免二叉搜索树退化成链表呢？

首先，节点的添加，删除顺序是无法限制的，可以认为是随机的。所以，改进方案是：在节点添加，删除操作之后，想办法让二叉树恢复平衡。一颗达到适度平衡的二叉搜索树，可以称之为：平衡二叉搜索树，英文简称 BBST

二、AVL树简介

AVL树是最早发明的自平衡二叉搜索树之一，AVL 取名于两位发明者的名字（G.M.Adelson-Velsky 和 E.M.Landis）。

也有人把 AVL 树念做 “艾薇儿树”。

1、特点

• 每个节点的平衡因子只可能是 1,0，-1 （绝对值 <=1，如果超过1，称之为“失衡”）
• 每个节点的左右子树高度差不超过1
• 搜索，添加，删除的时间复杂度是O（logn）

 

如上图所示：节点 9 的左子树高度为0，右子树高度为 3，所以 9 的平衡因子为 -3，已经失衡了。

2、添加导致的失衡

如下图所示，添加节点 13 时，祖父节点（父节点的父节点）的平衡因子为2，已经失衡了，祖父节点的父节点也失衡了。

最坏情怀：可能会导致所有祖父节点都失衡

父节点，非祖先节点都不可能失衡

需要通过以下方式旋转恢复平衡

2.1、LL - 右旋转（单旋）

如下图所示，T0 = T1，T2 = T3（高度相等）：

在没有加入新增节点（红框）之前，g 节点的平衡因子为1

加入新增节点之后，g 节点的平衡因子为2，已经失衡。

这属于在左子树的左子树 上插入节点之后导致的失衡，通过右旋转 P 节点成为根节点，恢复平衡，如下所示：

节点大小关系如下：

n < p < T2 < g < T3

所以 p 节点右旋转成为根节点时，需要做以下调整：

• g 成为 p 的右子树（p.right = g）
• T2 大于 p，小于 g，T2之前是 p.right。所以 T2 成为 g 的左子树 （g.left = p.right）

此时整颗树达到了平衡，此外还需要注意一些收尾工作：例如：更新 T2，p，g 的parent 属性

2.2、RR - 左旋转（单旋）

 如下图所示：T0 = T1，T2 = T3（高度相等）

同理：这属于在右子树的右子树上插入节点之后导致的失衡，通过左旋转 P 节点成为根节点，恢复平衡

节点大小关系如下：

T0  < g < T1 <  p < n

所以 p 节点左旋转成为根节点时，需要做以下调整：

• g 成为 p 的左子树（p.left = g）
• T1 大于 g，小于 p，T1之前是 p.left。所以 T1 成为 g 的右子树 （g.right = p.left）

此时整颗树达到了平衡，此外还需要注意一些收尾工作：例如：更新 T1，p，g 的parent 属性