二叉搜索树被提出后不就，就有人发现了一个关键问题：当数据无意或者有意被有序输入时，二叉树的每一个节点都将只有一个孩子，也就是会退化成链表。为此，A.V.和L.提出了二叉平衡树的概念，解决了问题。
AVL树是一种特殊的二叉排序树，它具有以下性质：
1.左子树和右子树都是平衡二叉树； 2.左子树和右子树的深度（高度）之差的绝对值不超过1。
这样可以保证在搜索其中的元素时最大时间复杂度不会超过log 2 N 。
下面给出AVL树的C语言实现。
首先是树节点的定义：
//为了保持平衡，每个节会额外增加一个数据表示当前的高度。
struct node
{
int height;
int key; //这是关键字，实际应用还需要根据存储的数据来计算关键字的值
struct node* left;
struct node* right;
}AVLNode;
接下来是访问的节点
typedef struct
{
struct node *root;
}AVLTree;
AVL树同一般的二叉树一样，有遍历（先序、中序、后序），最大值与最小值，插入和删除，销毁等操作，除插入和删除以外其余均与二叉搜索树相同，所以这里就只写AVL插入和删除操作。
在进行实现之前，需要先了解一下AVL树能够平衡总高度的原理。只有搭建了这些方法之后才能进行调用（图片转自某个二叉树生成器）
在面对不平衡的树时，可以通过旋转操作来更改根节点和叶子节点的关系，从而使访问根节点时，二叉树是平衡的。
根据不同的失衡类型，可以分为LL,LR,RL,RR四种。虽然数学书镜像对称的问题可以归类为一种，但很抱歉，这里不欢迎数学(手动狗头)。
LL型：
针对LL型失衡问题，我们先看图说话：这里可以看出，1的存在造成了节点5的深度达到了3，使二叉树发生了失衡。它的识别特征是“失衡节点的左孩子的左孩子多了一个孩子” 。 而修正策略用自然语言描述，就是“失衡节点的左孩子的右孩子链接至失衡节点，并将这个左孩子放置于原失衡节点原本的位置” 拿图里的序号来说，就是将4号链接至5号，并把3号重置为根节点。
下面给出修正策略的代码实现：
/*LL旋转， 参数： root ： 失衡AVL树根节点(不一定是树的根节点) 返回值 ： 调整后的AVL树根节点 */ AVLNode* LLRotate(AVLNode* root) { AVLNode* lchild=root->left; root->lchild=lchild->right; lchild->right=root; lchild->height = max(height(lchild->left), height(root)) + 1; root->height = max(height(root->left), height(root->right)) + 1; //height函数用来获取节点的高度，而+1是因为我们刚把一个节点旋转到原root的头上 return lchild; }
RR型：
对于RR型，大部分的内容和LL型一样，替换一些关键字即可。 /*LL旋转， 参数： root ： 失衡AVL树根节点(不一定是树的根节点) 返回值 ： 调整后的AVL树根节点 */ AVLNode* RRRotate(AVLNode* root) { AVLNode* rchild=root->right; root->right=rchild->left; rchild->left=root; rchild->height = max(height(rchild->left), height(root)) + 1; root->height = max(height(root->right), height(root->left)) + 1; return lchild; }
RL型与LR型：
这些问题需要旋转两次才能够解决，相对而言麻烦一些。如上图所示，先对最低失衡根结点的左孩子（结点2）进行RR旋转，再对最低失衡根结点（结点5）进行LL旋转。下图演示了调整过程。
而由于已经构建了LL和RR旋转所用到的函数，进行简单拼合之后就可以得到LL和LR的代码。 AVLNode* RLRotate(AVLNode* root) { root->left = RLRotate(root->left); //先对左子树RR旋转 return LLRotate(root); //再对根结点LL旋转 } AVLNode* LRRotate(AVLNode* root) { root->right = LLRotate(root->right); //先对左子树LL旋转 return RRRotate(root); //再对根结点RR旋转 }
看到这里应该也累得要死了吧…。那么下面就贴出插入节点的代码。在此处指出，与一般的二叉树插入代码惟一不同之处在于插入后会检查有没有出现不平衡的现象。
AVLNode* AVLInsert(AVLNode* root, int key)
{
if (root == NULL)
AVLNode root ={0,key,NULL,NULL};
else if (key < root->key) //作为左子树插入
{
root->left = AVLInsert(root->left, key);
if (height(root->left) - height(root->right) == 2) //插入导致二叉树失衡
{
if (key < root->left->key)
root = leftLeftRotate(root);
else root = leftRightRotate(root);
}
}
else if (key>root->key) //作为右子树插入
{
root->right = insert(root->right, key);
if (height(root->right) - height(root->left) == 2)
{
if (key > root->right->key)
root = rightRightRotate(root);
else root = rightLeftRotate(root);
}
}
root->height = max(height(root->left), height(root->right)) + 1;
return root;
}
累死我了,过两天再补删除的代码
4.2：补个锤子，节点删了再检查一遍平衡性就完了
4.11：我错了，这里头好多东西
节点删除
对于节点删除，有很多种情况需要分析。
0.根节点 1.没有左右孩子 2.有左右孩子 3.只有左孩子 4.只有右孩子
删除节点有两个儿子：
一般的删除策略是用其右子树的最小的数据代替该节点的数据，并递归地删除那个右子树的最小节点。如果删除节点2，那么先用其右子树的最小数据节点3代替该节点的数据，然后再递归地删除节点3。数据结构的各个数据节点仅数值不同，修改数据其实就是修改数据节点。
/* * 6 6 6 * / \ / \ / \ * 2 8 3 8 3 8 * / \ \ --> / \ \ --> / \ \ * 1 4 10 1 4 10 1 4 10 * / / * 3 3 */
根据二叉查找树的特性，右子树的最小数据节点大于该节点的所有左子树节点，小于该节点的右子树节点当中除了最小节点的所有节点，这样用这个右子树最小数据节点代替该节点，那么操作之后的还是二叉查找树。
删除节点只有左孩子：
分两种情况
1.左孩子是叶子节点
这种情况很好办，用左孩子的值替换当前节点，随后删除左孩子节点。
2.左孩子不是叶子节点
此时需要找到左孩子的所有子节点中，最大的值。原因同上。随后再以这个次大的节点递归进行删除。
/* * 6 4 4 4 * / / / / * 2 2 2 2 * / \ --> / \ --> / \ --> / \ * 1 4 1 4 1 3 1 3 * / / / * 3 3 3 */
删除节点只有右孩子：
同上，如果只有一个右孩子，替换并删除即可。
若不是，找到右孩子的子节点里最小的替换，然后递归删除…
/* * 6 6 6 * / / / * 2 3 3 * \ --> \ --> \ * 4 4 4 * / / * 3 3 */
从上面分析可以看出，删除操作是用树中的某个数据代替删除节点键值，实际上删除的都是叶子节点，据此我们可以把所有情况用一个程序解决。
删除代码:
AVLNode* AVLdel(AVLNode* root, int key)
{
if(root==NULL)
return NULL;
else if(root->key > key)//在左子树中
{
root->lchild = AVLdel(root->lchild, key);
if (height(root->left) - height(root->right) == 2) //插入导致二叉树失衡
{
if (key < root->left->key)
root = leftLeftRotate(root);
else root = leftRightRotate(root);
}
}
else if(root->key < key)//在右子树中
{
root->lchild = AVLdel(root->rchild, key);
if (height(root->left) - height(root->right) == 2) //插入导致二叉树失衡
{
if (key < root->left->key)
root = leftLeftRotate(root);
else root = leftRightRotate(root);
}
}
else if(root->key == key)
{
if(root->lchild && root->rchild)//左右孩子都存在
{
if (HEIGHT(root->lchild) > HEIGHT(root->rchild))
{
// 如果root的左子树比右子树高；
// 则(01)找出root的左子树中的最大节点
// AVLMax函数就是干这个的，别问怎么干
// (02)将该最大节点的值赋值给root。
// (03)删除该最大节点。
// 这类似于用"root的左子树中最大节点"做"root"的替身；
// 采用这种方式的好处是：删除"root的左子树中最大节点"之后，AVL树仍然是平衡的。
AVLNode *max = AVLMax(root->lchild);
root->key = max->key;
root->lchild = AVLdel(root->lchild, max);
}
else
{
// 如果root的左子树不比右子树高(即它们相等，或右子树比左子树高1)
// 则(01)找出root的右子树中的最小节点
// (02)将该最小节点的值赋值给root。
// (03)删除该最小节点。
// 这类似于用"root的右子树中最小节点"做"root"的替身；
// 采用这种方式的好处是：删除"root的右子树中最小节点"之后，AVL树仍然是平衡的。
AVLNode *min = AVLMin(root->rchild);
root->key = min->key;
root->rchild = AVLdel(root->rchild, min);
}
}
else //都不是，那没有这个节点，把用户骂一顿
{
AVLNode *tmp = root;
root = root->lchild ? root->lchild : root->rchild;
free(tmp);
}
return root;
}
参考文献：https://www.cnblogs.com/skywang12345/p/3576969.html
隐形眼镜是伟大的发明