一：AVL树介绍：
它是最先发明的自平衡二叉查找树，也被称为高度平衡树。相比于"二叉查找树"，它的特点是：AVL树中任何节点的两个子树的高度最大差别为1。 
注意： 上面的两张图片，左边的是AVL树，它的任何节点的两个子树的高度差别都<=1；而右边的不是AVL树，因为7的两颗子树的高度相差为2(以2为根节点的树的高度是3，而以8为根节点的树的高度是1)
二：AVL树结构：
typedef int Type; typedef struct AVLTreeNode{ Type key; // data值 int height; //AVL树高度 struct AVLTreeNode *left; // 左子树 struct AVLTreeNode *right; // 右子树 };
三：AVL树初始化以及创建：
Node* avltree_create_node(Type key, Node *left, Node* right) { Node* p; if ((p = (Node *)malloc(sizeof(Node))) == NULL) return NULL; p->key = key; p->height = 0; p->left = left; p->right = right; return p; }
四：重点：AVL树旋转
AVL树旋转分为四种情况： LL(左左)，LR(左右)，RR(右右)和RL(右左) 
4.1LL旋转以及RR旋转
//1.LL旋转 Node* left_left_rotation(AVLTree k2) { AVLTree k1; k1 = k2->left; k2->left = k1->right; k1->right = k2; k2->height = MAX( HEIGHT(k2->left), HEIGHT(k2->right)) + 1; k1->height = MAX( HEIGHT(k1->left), k2->height) + 1; return k1; } //2.RR旋转 Node* right_right_rotation(AVLTree k1) { AVLTree k2; k2 = k1->right; k1->right = k2->left; k2->left = k1; k1->height = MAX( HEIGHT(k1->left), HEIGHT(k1->right)) + 1; k2->height = MAX( HEIGHT(k2->right), k1->height) + 1; return k2; }
这两种旋转的方法类似：下面图示：
4.2LR旋转以及RL旋转;
//LR和RL旋转其实也就是对左/右子树先LL/RR旋转。然后对需要旋转的节点进行RR/LL旋转 //1.LR旋转 Node* left_right_rotation(AVLTree k3) { k3->left = right_right_rotation(k3->left); return left_left_rotation(k3); } //2.RL旋转 Node* right_left_rotation(AVLTree k1) { k1->right = left_left_rotation(k1->right); return right_right_rotation(k1); }
五：AVL插入节点：
Node* avltree_insert(AVLTree tree, Type key) { if (tree == NULL) { // 新建节点 tree = avltree_create_node(key, NULL, NULL); if (tree==NULL) { printf("ERROR: create avltree node failed! "); return NULL; } } else if (key < tree->key) // 应该将key插入到"tree的左子树"的情况 { tree->left = avltree_insert(tree->left, key); // 插入节点后，若AVL树失去平衡，则进行相应的调节。 if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2) { if (key < tree->left->key) tree = left_left_rotation(tree);//LL转 else tree = left_right_rotation(tree);//LR转 } } else if (key > tree->key) // 应该将key插入到"tree的右子树"的情况 { tree->right = avltree_insert(tree->right, key); // 插入节点后，若AVL树失去平衡，则进行相应的调节。 if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2) { if (key > tree->right->key) tree = right_right_rotation(tree);//RR转 else tree = right_left_rotation(tree);//RL转 } } else //key == tree->key) { printf("添加失败：不允许添加相同的节点！ "); } tree->height = MAX( HEIGHT(tree->left), HEIGHT(tree->right)) + 1; return tree; }
六：AVL删除节点：
Node* delete_node(AVLTree tree, Node *z) { // 根为空 或者 没有要删除的节点，直接返回NULL。 if (tree==NULL || z==NULL) return NULL; if (z->key < tree->key) // 待删除的节点在"tree的左子树"中 { tree->left = delete_node(tree->left, z); // 删除节点后，若AVL树失去平衡，则进行相应的调节。 if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2) { Node *r = tree->right; if (HEIGHT(r->left) > HEIGHT(r->right)) tree = right_left_rotation(tree); else tree = right_right_rotation(tree); } } else if (z->key > tree->key)// 待删除的节点在"tree的右子树"中 { tree->right = delete_node(tree->right, z); // 删除节点后，若AVL树失去平衡，则进行相应的调节。 if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2) { Node *l = tree->left; if (HEIGHT(l->right) > HEIGHT(l->left)) tree = left_right_rotation(tree); else tree = left_left_rotation(tree); } } else // tree是对应要删除的节点。 { // tree的左右孩子都非空 if ((tree->left) && (tree->right)) { if (HEIGHT(tree->left) > HEIGHT(tree->right)) { // 如果tree的左子树比右子树高； // 则(01)找出tree的左子树中的最大节点 // (02)将该最大节点的值赋值给tree。 // (03)删除该最大节点。 // 这类似于用"tree的左子树中最大节点"做"tree"的替身； // 采用这种方式的好处是：删除"tree的左子树中最大节点"之后，AVL树仍然是平衡的。 Node *max = avltree_maximum(tree->left); tree->key = max->key; tree->left = delete_node(tree->left, max); } else { // 如果tree的左子树不比右子树高(即它们相等，或右子树比左子树高1) // 则(01)找出tree的右子树中的最小节点 // (02)将该最小节点的值赋值给tree。 // (03)删除该最小节点。 // 这类似于用"tree的右子树中最小节点"做"tree"的替身； // 采用这种方式的好处是：删除"tree的右子树中最小节点"之后，AVL树仍然是平衡的。 Node *min = avltree_maximum(tree->right); tree->key = min->key; tree->right = delete_node(tree->right, min); } } else { Node *tmp = tree; tree = tree->left ? tree->left : tree->right; free(tmp); } } return tree; } /* * 删除结点(key是节点值)，返回根节点 * * 参数说明： * tree AVL树的根结点 * key 待删除的结点的键值 * 返回值： * 根节点 */ Node* avltree_delete(AVLTree tree, Type key) { Node *z; if ((z = avltree_search(tree, key)) != NULL) tree = delete_node(tree, z); return tree; }