Hoyue の 自留地 
前言
这一章将在BST（二叉查找树）的基础上，介绍AVL树。
AVL树
我们知道，二叉查找树满足：
- 若其左子树非空，则左子树上所有节点各自的值都小于根节点的值
- 若其右子树非空，则右子树上所有节点各自的值都大于根节点的值
- 其左右子树都是一棵二叉查找树。
但是我们在实现中很容易遇到其他的特殊情况，例如：
- 左右子树的高度差距太大；
- 高度决定因素比较单一…
这些不平衡的高度会影响到我们的时间复杂度和深度，于是我们就推出了AVL树解决这个问题。
定义： AVL(Adelson-Velskii和Landis)树是 带有平衡条件 的二叉查找树。这个平衡条件必须要容易保持，而且它须保证树的深度是 。
既然AVL是一个带有条件的二叉查找树，那它的最理想情况就是完全平衡的，左右子树具有相同的高度，每个非树叶节点均有两个子节点。称为理想平衡树(perfectly balanced tree)。
但是这个条件太严格，难以使用，需要放宽条件。所以我们定义：
一棵AVL 树是 “其每个节点的左子树和右子树的 高度最多差1 ” 的二叉查找树。
AVL树保证了，每一个节点的子树的高度差最多为1，这里以左子树比右子树高度大一来举例。
我们用Nh表示AVL树的节点数量，h为树叶的数量。我们来看AVL树节点的规律：
h从0~3的情况：
h=4时：
从N3、N4我们就发现了，Nh的值只与 N(h-1)+N(h-2)+1 有关，归纳一下就是这样：
- N(0) = 1, N(1) = 2;
- N(h) = N(h-1)+N(h-2)+1. (h>1)
它的递推公式与斐波那契数列很像，即 N(n) = F(n) + 1 ;
了解了AVL树的基本内容后，我们来看看AVL树的相关操作和BST的不同。创建等操作和其他树基本一致，但是我们发现插入操作会有特殊之处——可能破坏AVL 树的特性。
在介绍插入和删除前，我们同样也来简单地写AVL树的基本实现——定义、初始化、其他功能函数等。
定义以及初始化
像BST一样的，我们定义一个AVL树：
typedef int Type;typedef struct AVLTree{ Type d; int h; struct AVLTree *left; struct AVLTree *right;}tree;
tree *create(Type d, tree *l, tree *r){ tree *node=(tree *)malloc(sizeof(tree)); if(node == NULL) return NULL; node->d=d; node->left=l; node->right=r; node->h=0; //初始化创建时为0，之后动态调整 return node;}AVL树的节点包括的几个组成对象: (01) d：数据信息。 (02) left：左孩子。 (03) right：右孩子。 (04) h：高度。
其他函数
我们还需要计算树的高度的函数。如果我们这个树是空的，高度应该为-1，因为高度从0开始计算。同时加入一个比较大小的max函数，比较两节点的数据大小
int height(tree *node){ return (node!=NULL)?node->h:-1;}
tree *max(tree *a, tree *b){ return (a->d > b->d)?a:b;}接下来就是我们的插入和删除啦。
旋转
我们在插入时，大多会破坏AVL树的性质，我们需要更新通向根节点路径上那些节点的所有平衡信息，并恢复AVL树的性质。
我们把对树进行简单的修正的过程，称为 旋转(rotation) 。
旋转的目的是 减少高度 ，通过降低整棵树的高度来平衡。一般 插入发生在”外边”的情况 可以通过一次旋转解决，称为 单旋转 ， 插入发生在”内部” 的情况 一般可以通过两次解决，称为 双旋转 。
单旋转
插入发生在外边的情况，一般可以使用单旋转解决。例如：
LL
在左子树的左子树处插入 ，LeftLeft，也称为”左左”。此时”根的左子树的高度”比”根的右子树的高度”大1。如图这两种情况，都是在左子树的左子树处插入：（图为根节点8处左右子树不平衡）
图中，根节点(8)的左子树(4)的左子树(2)还有非空子节点， 根的左子树的高度为2 ， 而 根节点(8)的右子树(12)没有子节点， 根的右子树的高度为0。 此时高度差>1，平衡条件被破坏。
我们从简单的例子开始，例如：
我们插入一个节点在左树叶5上。
平衡被破坏，此时让它重新平衡需要进行右旋转，被破坏了平衡 首先要找到是哪个子树被破坏了平衡 ，然后调整这个子树。然后继续往上一个一个的调整。
所以我们先 找离新插入的节点最近的不平衡的树进行调整 ，上图中就是根节点为7的树. 7的左子树高度为1，右子树不存在，高度为-1，此时高度差为2，处于不平衡状态。
此时我们要满足AVL树的要求——左右子树高度差<=1，并且根节点的左侧大于右侧（BST要求），那我们就对它进行一次顺时针向右的旋转，即 固定中间的被插入的节点5，以它为轴，向右旋转。此时7就掉到了5的右边，成为5的右子树了 。然后5替代了原来7的位置（5代替7上位），如图：
经过这样的调整过后，我们就已经成功把不平衡的LL情况，恢复为平衡了。
那如果节点5本来就有了右子树呢？这个就会涉及到双旋转，在之后会涉及。
关于LL的图解：
我们看图说话，直接写出LL的函数：
static tree *LLspin(tree *root){ tree *k1=root->left; tree *k2=root; k2->left=k1->right; k1->right=k2; k2->h=maxheight(height(k2->left),height(k2->right))+1; k1->h=maxheight(height(k1->left),height(k2))+1; return k1;}RR
同理，和LL一样的，我们在 在右子树的右子树处插入 ，RightRight，称为”右右”。此时”根的右子树的高度”比”根的左子树的高度”大2，导致AVL树失去了平衡。
图中，根节点(8)的右子树(12)的右子树(14)还有非空子节点， 根的左子树的高度为2 ， 而 根节点(8)的左子树(4)没有子节点， 根的右子树的高度为0。 此时高度差>1，平衡条件被破坏。
和LL一样， 在右子树的右子树上插入节点破坏的平衡需要 左 旋转来矫正 。那么同样的，我们进行如下操作：
- 找到最近非平衡树；
- 固定有一个子节点的节点，以它为轴旋转；
- 逐级调整直到成为AVL树。
如图示例：
关于RR的图解：
同理，RR的函数为：
static tree *RRspin(tree *root){ tree *k1=root; tree *k2=root->right; k1->right=k2->left; k2->left=k1; k1->h=maxheight(height(k1->left),height(k1->right))+1; k2->h=maxheight(height(k2->left),height(k2->right))+1; return k2;}双旋转
我们之前讨论的情况是在左子树的左子树上插入节点（LL），或是在右子树的右子树上插入节点（RR），那如果是在左子树的右节点插入，或右子树的左节点插入呢？我们来讨论下一这两种情况。
LR
LeftRight，也称为”左右”。插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，导致”根的左子树的高度”比”根的右子树的高度”大2，导致AVL树失去了平衡。
LR形如：
如果在LL的例子中不是向左插入3，而是向右插入6，平衡条件依然被破坏，如图：
我们的解决方法和之前相同，先找到最近的不平衡子树。这里依然是以7为根的树，于是我们尝试对它进行旋转。可能会得到下面这种情况：
但这是一种错误的旋转，因为我们发现左节点6居然比根节点5大，不满足BST的性质。 要是插入的这个节点在左子树上就刚好可以这样旋转了。
所以我们可以先把插在右节点上的节点旋转到左边，即：
这里的旋转是针对根为5的子树的旋转 ，我们固定节点6，再向左旋转，就得到了如图的子树。
此时旋转了一次以后我们就得到了类似于LL的形式，我们就对其进行右旋转。
最后我们就得到了AVL树。全过程进行了一次左旋，再进行了一次右旋，如图：
知道LR双旋转后这时我们就可以解决之前在LL时提出的问题——如果插入的节点有兄弟节点，该如何旋转？
例如，我们插入的节点是3，原本就存在节点6：
我们同样的对它试着进行旋转。此时旋转过程中有阻碍， 我们一般把原来的节点拿走，旋转新的节点，并把原来的节点接入旋转后的节点上。 固定节点5向右旋转，此时旋转时为了让7落下来且不破坏BST性质，我们应该先判断一次右节点（6）与前节点的大小（7）。
若右节点小于前节点，则右节点成为旋转下来后的前节点的左节点；若右节点大于前节点，则右节点成为旋转下来后的前节点的右节点。
此时6<7，于是把节点7旋转下来，并把节点6作为节点7的左节点。
但是我们此时整体的树依然不是AVL树，我们发现这时候树满足，插入节点位于左子树的右子树上，满足LR的形式，此时对它进行LR的先左旋再右旋即可恢复。
关于LR先左旋再右旋的图解：
static tree *LRspin(tree *root){ root->left=RRspin(root->left); return LLspin(root);}RL
RightLeft，称为”右左”。插入或删除一个节点后，根节点的右子树的左子树还有非空子节点，导致”根的右子树的高度”比”根的左子树的高度”大1，导致AVL树失去了平衡。
RL形如：
当破坏平衡的节点是这个树的右子树的左子树时，要进行先右旋转再左旋转来矫正。
与LR类似的过程就不再描述，例子与图例：
关于RL先右旋再左旋的图解：
static tree *RLspin(tree *root){ root->right=LL(root->right); return RRspin(root);}旋转总结
总结一下旋转：
- 旋转的目的就是 减少高度 ，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转；
- 旋转保证的 仍然是中序遍历 的序列（BST性质）；
- 每次旋转基本都是 同一个节点 ，那个节点一般是子树中深度为1的，大多数情况是这样的。
插入
我们已经了解了旋转的方法，接下来就是在插入节点时进行旋转操作的实现：
tree *insert(tree *node, Type d){ if(node == NULL) { node=create(d, NULL, NULL); if(!node) { printf("Error, no space.\n"); return NULL; } } if(d == node->d) { printf("Error, cannot add same node\n"); return NULL; } else if(d < node->d) //往左边插入 { node->left=insert(node->left,d); if(height(node->left) - height(node->right) > 1) // 插入节点后，若AVL树失去平衡，则进行相应的调节。 { if(d<node->left->d) LLspin(node); else LRspin(node); } } else if(d > node->d) //往右边插入 { node->right=insert(node->right,d); if(height(node->right) - height(node->left) > 1) // 插入节点后，若AVL树失去平衡，则进行相应的调节。 { if(d > node->right->d) RRspin(node); else RLspin(node); } } node->h=max(height(node->left),height(node->right))+1; //取左右子树的最大高度，并且+1表示当前根节点的高度 return node;}删除
删除节点也可能破坏AVL树的结构，一般来说会有下面几种情况：
- 根为空或者没有要删除的节点，直接返回NULL。
- 待删除的节点在左子树中，删除节点后，若AVL树失去平衡，需要旋转。（因为删除节点满足BST删除的性质，需要进行一些调整，可能导致失去平衡）
- 待删除的节点在右子树中，删除节点后，若AVL树失去平衡，需要旋转。
- 待删除的节点为当前根节点
- 根节点左右子树均非空
- 根节点左右子树有空
我们在删除当前节点的时候，因为不是插入，我们可以直接让 该节点的值替换为其左/孩子节点的值，然后删除左/右孩子节点。
我们分情况来看，先从底下的树叶或左右树叶情况来看：
此时不需要通过旋转来平衡AVL树。也会出现需要旋转调整的情况：
当需要删除的结点是 非叶子节点， 该节点的值替换为该节点的前驱节点（或者后继节点），然后删除前驱节点（或者后继节点）。
于是我们的代码部分：
tree *delete(tree *root, tree *node) //返回根节点，删除node{ if(!root || !node) //case1 return NULL; if(node->d < root->d) //case2：待删除的节点在左子树 { root->left=delete(root->left,node); //删除节点后，若AVL树失去平衡，则进行相应的调节。 if(height(root->right) - height(root->left) == 2) { tree *p=root->right; if(height(p->right) > height(p->left)) //检查它的右边，因为删除后可能右边高 root=RRspin(root); //相当于在右侧的左边插入了一个 else root=RLspin(root); } } if(node->d > root->d) //case3：待删除的节点在右子树 { root->right=delete(root->right,node); //删除节点后，若AVL树失去平衡，则进行相应的调节。 if(height(root->right) - height(root->left) == 2) { tree *p=root->left; if(height(p->left) > height(p->right)) //检查它的左边 root=LLspin(root); //相当于在左侧的左边插入了一个 else root=LRspin(root); } } else //case4: 待删除的节点为当前根节点 { if(root->left && root->right) //左右孩子都非空 { if(height(root->left) > height(root->right)) //如果左子树比右子树高； { //(1)找到左子树中最大的——左子树根的最右节点 tree *maxima=root->left; while(maxima->right) { maxima=maxima->right; } //(2)将它的值赋给当前的根 root->d=maxima->d; //(3)把最大值的那个位置删了 root->left=delete(root->left,maxima); //删除并连接 } if(height(root->left) <= height(root->right)) //如果左子树比右子树低或相等； { //(1)找到右子树中最小的——右子树根的最左节点 tree *minima=root->right; while(minima->left) { minima=minima->left; } //(2)将它的值赋给当前的根 root->d=minima->d; //(3)把最小值的那个位置删了 root->right=delete(root->right,minima); } } else //此时为树叶或只有左树叶或右树叶 { tree *t=root; if(root->left) { root=root->left; } else if (root->right) { root=root->right; } //删除之前节点 free(t); } } return root;}后记
AVL树的旋转是平衡是它的特点，并且还满足BST的性质。建议是把旋转的图像理解记忆，根据图像即可写出代码。
