前面我们已经介绍了二叉查找树，今天我们来介绍一个在它的基础上构造的更高级的一种二叉树。它的名字是平衡二叉树，一般我们称之为AVL：除了具有二叉查找树的特点之外，它的左子树和右子树的深度之差的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。 AVL树就是一颗特殊的二叉查找树，但是如果按照二叉查找树那样插入和删除节点，就会破坏它的平衡性。那么需要什么样的算法才能保证每次插入或者删除一个节点之后，它依旧是一颗平衡二叉树呢？
1.1 节点的定义
typedef int Type;
typedef struct AVLTreeNode{
Type key; // 关键字(键值)
int height;
struct AVLTreeNode *left; // 左孩子
struct AVLTreeNode *right; // 右孩子
}Node, *AVLTree;
1.2节点的创建：
/* 创建AVL树结点。
* 参数说明：
* key 是键值。
* left 是左孩子。
* right 是右孩子。*/
static 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;
}
1.3树的高度：
#define HEIGHT(p) ( (p==NULL) ? 0 : (((Node *)(p))->height) )
/* 获取AVL树的高度*/
int avltree_height(AVLTree tree)
{
return HEIGHT(tree);
}
2.1 LL旋转代码
/* LL：左左对应的情况(左单旋转)。
* 返回值：旋转后的根节点*/
static 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.2 RR的旋转代码：
/*RR：右右对应的情况(右单旋转)。
* 返回值：旋转后的根节点*/
static 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;
}
2.3 LR的旋转代码
/* LR：左右对应的情况(左双旋转)。
* 返回值：旋转后的根节点*/
static Node* left_right_rotation(AVLTree k3)
{
k3->left = right_right_rotation(k3->left);
return left_left_rotation(k3);
}
2.4 RL的旋转代码
/*RL：右左对应的情况(右双旋转)。
* 返回值：旋转后的根节点*/
static Node* right_left_rotation(AVLTree k1)
{
k1->right = left_left_rotation(k1->right);
return right_right_rotation(k1);
}
3. 插入节点的代码：
/* 将结点插入到AVL树中，并返回根节点
* 参数说明：
* tree AVL树的根结点
* key 插入的结点的键值
* 返回值：
* 根节点*/
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!\n");
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);
else
tree = left_right_rotation(tree);
}
}
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);
else
tree = right_left_rotation(tree);
}
}
else //key == tree->key)
{
printf("添加失败：不允许添加相同的节点！\n");
}
tree->height = MAX( HEIGHT(tree->left), HEIGHT(tree->right)) + 1;
return tree;
}
4. 删除节点的代码
/*
* 将结点插入到AVL树中，并返回根节点
*
* 参数说明：
* tree AVL树的根结点
* key 插入的结点的键值
* 返回值：
* 根节点
*/
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!\n");
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);
else
tree = left_right_rotation(tree);
}
}
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);
else
tree = right_left_rotation(tree);
}
}
else //key == tree->key)
{
printf("添加失败：不允许添加相同的节点！\n");
}
tree->height = MAX( HEIGHT(tree->left), HEIGHT(tree->right)) + 1;
return tree;
}
/*
* 删除结点(z)，返回根节点
*
* 参数说明：
* ptree AVL树的根结点
* z 待删除的结点
* 返回值：
* 根节点
*/
static 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;
}