AVL树及其搜索树

首先我们先明确两个关于二叉树的基本概念：深度（depth）和高度（height）。

深度：从根节点开始（其深度为1），自顶向下逐层累加；

高度：从叶节点开始（其高度为1），自底向上逐层累加。

虽然树的高度和深度一样，但具体到某个节点，其深度和高度不一样，如：

节点10的高度为2，深度为3；节点7的高度为1，深度为3.

言归正传：

AVL树：一个空二叉树是AVL树；一个非空二叉树T的左右子树TL和TR，若T为AVL树，则TL和TR也为AVL树，且TL和TR的高度差不超过1.

AVL搜索树（AVL search tree）：只不过是一个拥有AVL特性的二叉搜索树，如

一个有n个节点的AVL树的高度是O(logn)，这有助于评估基于AVL树的算法的复杂度。

下面着重谈一谈AVL搜索树的基本操作：

1）搜索（search）：与普通二叉搜索树的操作一样，不过算法复杂度变为O(logn)；

2）插入（insert）：

平衡因子（balance factor）—— 一个节点左子树的高度减去右子树的高度就是该节点平衡因子，一棵AVL树中不存在平衡因子不是1、-1或0的节点。

寻找X：维持该树的平衡因子不变，从要插入的位置向根节点上溯，找到平衡因子首先为1或-1的祖先节点，记为X。

根据X进行判断是否需要重新平衡树：

a)若X不存在，也就是说从根节点（包括根节点）到要插入的位置的路径上的节点的平衡因子都为0，这是可以判断不需要重新平衡，只需要改变路径上节点的平衡因子即可。

b)X存在，但插入后其平衡因子变为0，也不需要进行平衡，只不过X的左右子树在插入后的高度变得相等罢了。

c)当X的平衡因子由1变为2或由-1变为-2时才需要进行平衡。

不平衡（imbalance）的类型分为LL、LR和RR、RL四种类型，并对应四种旋转以达到平衡。

I)LL旋转（rotation）

II)LR旋转

III)对于RR和RL旋转也是同样的道理，LL和RR的旋转属于单旋转（single rotations），LR和RL的旋转是双旋转（double rotations）。

3）删除（delete）：

维持原始平衡因子不变，如果从要删除的节点到根节点路径上的节点的平衡因子都为0，则不需要进行平衡旋转。当删除节点后调整平衡因子，从删除位置向根节点上溯，找到平衡因子首先变为2或-2的节点记为X，我们以它为根节点进行旋转。

I)R1旋转

为什么叫R1旋转？我们首先找到特殊节点X为节点15，由于删除的节点位于15的右子树，所以为R，1是因为删除前15节点左子树的根节点13的平衡因子为1，同理如果平衡因子为0，则为R0旋转，为-1，则为R-1旋转。这里的R1旋转跟上面插入用的LL旋转一模一样：

节点13顶替15的位置，13的右子树作为15的左子树，节点15接在13的右子树上。

II)R0旋转

R0旋转和LL旋转的不同在于B和X的平衡因子。

总结：其实一切都是围绕平衡因子来的，我们通过平衡因子判断是否平衡，并确定旋转区域的根节点（如上面的节点15和节点X），也是根据平衡因子我们制定旋转策略，其在算法实现上，只是根据平衡因子进行局部子树的重组，算法复杂度不论查找、插入还是删除，都为O(logn)。