4、【数据结构】树形结构之平衡二叉查找树（AVL树）
一、AVL树简介
1、定义
AVL树是高度平衡的二叉查找树，它的特点是：AVL树中任何结点的两个子树的高度最大差别为1。
AVL树的示意图如下：
typedef int Type;
typedef struct AVLTreeNode{
Type key; // 关键字(键值)，是用来对AVL树的节点进行排序的。
int height; //AVL树高度
struct AVLTreeNode *left; // 左孩子
struct AVLTreeNode *right; // 右孩子
}Node, *AVLTree;
1.2 结点创建
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);
}
AVL树的高度的定义：树的高度为最大层次。即空的二叉树的高度为0，非空树的高度等于它的最大层次（根的层次为1，根的子结点为第2层，以此类推）。
2、AVL树的时间复杂度分析
AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。
二、AVL树相关操作
如果在AVL树中插入或删除节点后，使得高度之差大于1。此时，AVL树的平衡状态就被破坏，它就不再是一棵二叉树；为了让它重新维持在一个平衡状态，就需要对其进行旋转处理。
1、AVL树失衡分类
如果在AVL树中进行插入或删除节点后，可能导致AVL树失去平衡。这种失去平衡的可以概括为4种姿态：LL(左左)，LR(左右)，RR(右右)和RL(右左)。它们都有各自的定义：
(1) LL：LeftLeft，也称为"左左"。插入或删除一个节点后，根节点的左子树的左子树还有非空子节点，导致"根的左子树的高度"比"根的右子树的高度"大2，导致AVL树失去了平衡。
(2) LR：LeftRight，也称为"左右"。插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，导致"根的左子树的高度"比"根的右子树的高度"大2，导致AVL树失去了平衡。
(3) RL：RightLeft，称为"右左"。插入或删除一个节点后，根节点的右子树的左子树还有非空子节点，导致"根的右子树的高度"比"根的左子树的高度"大2，导致AVL树失去了平衡。
(4) RR：RightRight，称为"右右"。插入或删除一个节点后，根节点的右子树的右子树还有非空子节点，导致"根的右子树的高度"比"根的左子树的高度"大2，导致AVL树失去了平衡。
2、AVL树的旋转操作
AVL失去平衡之后，可以通过旋转使其恢复平衡，下面分别介绍"LL(左左)，LR(左右)，RR(右右)和RL(右左)"这4种情况对应的旋转方法。
2.1 LL旋转
//返回值为旋转后的根节点
static Node* left_left_rotation(AVLTree k2)
{
AVLTree k1;
k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
//重新计算AVL树的高度
k2->height = MAX( HEIGHT(k2->left), HEIGHT(k2->right)) + 1;
k1->height = MAX( HEIGHT(k1->left), k2->height) + 1;
return k1;
}
2.2 RR旋转
//返回值为旋转后的根节点
static Node* right_right_rotation(AVLTree k1)
{
AVLTree k2;
k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
//重新计算AVL树的高度
k1->height = MAX( HEIGHT(k1->left), HEIGHT(k1->right)) + 1;
k2->height = MAX( HEIGHT(k2->right), k1->height) + 1;
return k2;
}
LL失衡和RR失衡的情况只需要一次旋转就可以是AVL树恢复平衡，当LR失衡和RL失衡需要两次旋转才能使AVL树恢复平衡。
2.3 LR旋转
//返回值为旋转后的根节点
static Node* left_right_rotation(AVLTree k3)
{
k3->left = right_right_rotation(k3->left);
return left_left_rotation(k3);
}
2.4 RL旋转
RL旋转是与LR旋转对称的情况，同样需要两次旋转才能使AVL树恢复平衡。具体过程如下：
//返回值为旋转后的根节点
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树的根节点
//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;
}
//对外接口函数
//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;
}
AVL树的遍历、最大值查找、最小值查找，打印、销毁等接口与“二叉查找树”的基本一样。
参考文章：http://www.cnblogs.com/skywang12345/p/3576969.html