AVL定义
AVL树是根据它的发明者G.M. Adelson-Velsky和E.M. Landis命名的。相比于“二叉搜索树”，它的特点是：AVL树中任何节点的两个子树的高度差小于等于1。
高度定义：树的高度为树的最大层次。即空的二叉树的高度是0，非空树的高度等于它的最大层次。如下图所示，图中的H表示树的高度：
根据AVL树的定义，任何节点的两个子树的高度差要小于等于1，我们逐个进行判断。首先是关键字为10的节点，左子树高度为2，右子树高度为1，高度差等于H左-H右=1，因此符合，类似地，我们对其余节点进行判断，发现均符合高度差小于等于1的要求，因此这是一棵AVL树。下面我们看一棵不符合要求的树，关键字为10的节点，左子树高度为3，右子树高度为1，H左-H右=2，不符合AVL要求，因此这不是一个AVL树。那么问题来了，我们如何建立一棵AVL树？因为树的建立是逐个插入节点的过程，所以要确保一个树始终是AVL树，我们需要在每次插入或删除一个节点后进行检查和调整。
把上面两棵树做对比，我们发现：新插入一个关键字为2的节点后，导致AVL树失去了平衡，失衡的节点在关键字为10节点的地方，因此我们需要在失衡的节点处下功夫。从图中来看，关键字1节点的插入导致关键字10的节点左侧太重，那么只要我们将整棵树的重心往左挪一点，就可以平衡。移到什么地方呢？因为新插入一个子节点，树的高度增加量不会超过2，要么是1要么是0，所以我们只需要将重心移至左子树的位置，那么就可以解决问题。
既然要移至5节点，那么10节点必然要作为5节点的一个子树，因为是左子树太重，重心向左挪，那么10节点必然是作为5节点的右子树，5节点原来的右子树便成为了10节点的左子树。如下图所示：
上述分析中我们知道，5节点提高一个层次后，其附属的节点层次均提高一个层次，因此可以平衡（抵消）了之前因为1节点插入导致的失衡。但是5节点的右子树并没有随着5节点提升一个层次，它只是平移至10节点的左子树的位置。这里存在个问题，如果，新插入的节点在这棵被平移至10节点左子树位置的分支上，那么失衡问题并不会得到解决，如下图所示：
新插入6节点之后导致10节点失衡，重心左移，由于6节点处于5节点右子树中，因此5节点的右子树平移至10节点左子树位置后，并没有抵消因为节点6带来的高度增加，因此下图中的这棵仍然是不平衡的。
因此，我们就需要想个办法，抵消因为插入节点6带来的高度增加。前面我们已经分析过了，只有处于5节点的左子树位置才会在移动重心后提升一个层次。那么，我们需要将5节点子树的重心右移，这样一来，10节点的子树移动重心后，刚好可以抵消这部分力量，如下图所示：
然后，对10节点的子树向左移动重心，整个树处于平衡。如下图：
类似地，如果失衡发生在某节点的右子树，也需要进行如上述的处理。总共可分为四种情况。
①LL：Left Left，也称为“左左”。插入或删除一个节点后，根节点左子树的左子树还有非空子节点，导致“根的左子树的高度”比“根的右子树的高度”大2，导致AVL树失去了平衡。
②LR：Left Right，也称为“左右”。插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，导致“根的左子树的高度”比“根的右子树的高度”大2，导致AVL树失去了平衡。
③RR：Right Right，也称为“右右”。插入或删除一个节点后，根节点的右子树的右子树还有非空子节点，导致"根的右子树的高度"比"根的左子树的高度"大2，导致AVL树失去了平衡。
④RL：Right Left，也称为“右左”。插入或删除一个节点后，根节点的右子树的左子树还有非空子节点，导致“根的右子树的高度”比“根的左子树的高度”大2，导致AVL树失去了平衡。
首先，我们定义AVL树节点结构。
typedef struct AVLTreeNode
{
Type key;
int height;
struct AVLTreeNode *left;
struct AVLTreeNode *right;
} AVLTreeNode, *pAVLTreeNode;
①针对LL情况的调平：
/**
* LL调平
* n0 : 失衡的节点
* return : 调平后的根节点
*/
static pAVLTreeNode left_left_rotation( pAVLTreeNode n0 )
{
pAVLTreeNode n1;
n1 = n0->left;
n0->left = n1->right;
n1->right = n0;
n0->height = MAX( HEIGHT(n0->left), HEIGHT(n0->right) );
n1->height = MAX( HEIGHT(n1->left), HEIGHT(n1->right) );
return n1;
}
②针对RR情况的调平：
/**
* RR调平
* n0 : 失衡的节点
* return : 调平后的根节点
*/
static pAVLTreeNode right_right_rotation( pAVLTreeNode n0 )
{
pAVLTreeNode n1;
n1 = n0->right;
n0->right = n1->left;
n1->left = n0;
n0->height = MAX( HEIGHT(n0->left), HEIGHT(n0->right) );
n1->height = MAX( HEIGHT(n1->left), HEIGHT(n1->right) );
return n1;
}
③针对LR情况的调平：
/**
* LR调平
* n0 : 失衡的节点
* return : 调平后的根节点
*/
static pAVLTreeNode left_right_rotation( pAVLTreeNode n0 )
{
pAVLTreeNode n1;
n0->left = right_right_rotation( n0->left );
n1 = left_left_rotation( n0 );
return n1;
}
④针对RL情况的调平：
/**
* RL调平
* n0 : 失衡的节点
* return : 调平后的根节点
*/
static pAVLTreeNode right_left_rotation( pAVLTreeNode n0 )
{
pAVLTreeNode n1;
n0->left = left_left_rotation( n0->left );
n1 = right_right_rotation( n0 );
return n1;
}
此外，还有上面用到的两个宏：
#define HEIGHT(P) ( (P==NULL) ? 0 : (((Node * )(P))->height) )
#define MAX(LEFT, RIGHT) ( (LEFT) > (RIGHT) ? (LEFT) : (RIGHT) )
那么，现在我们看看在插入和删除节点的过程中如何实现AVL树的调平。
我们知道，每次节点发生变化后，从根部到此节点相关联的节点高度都会发生变动，因此，我们可以采取递归的方式，先递归到插入或删除的位置，然后进行调平，接着在回溯的过程中不断更新与之关联的节点高度。
AVL基本操作
插入节点
/**
* 插入节点
* tree : 失衡的节点
* key ： 插入节点的key，整棵树唯一，不能有重复
* return : 调平后的根节点
*/
pAVLTreeNode static insert_avltree( pAVLTreeNode tree, Type key )
{
if ( tree == null ) {
tree = (pAVLTreeNode)malloc(sizeof(AVLTreeNode));
if( tree == NULL ) {
printf("分配节点失败！\r\n");
return NULL;
}
tree->height = 0;
tree->left = NULL;
tree->right = NULL;
} else if (key < tree->key) {
// 递归左子树
tree->left = insert_avltree( tree->left, key );
// 检查是否调平
if ( HEIGHT(tree->left) - HEIGHT(tree->right) == 2 ) {
if ( key < tree->left->key ) {
// LL
tree = left_left_rotation(tree);
} else {
// LR
tree = left_right_rotation(tree);
}
}
} else if (key > tree->key) {
// 递归右子树
tree->right = insert_avltree( tree->right, key );
// 检查是否调平
if ( HEIGHT(tree->right) - HEIGHT(tree->left) == 2 ) {
if ( key > tree->right->key ==NULL ) {
// RR
tree = right_right_rotation(tree);
} else {
// RL
tree = right_left_rotation(tree);
}
}
} else {
// key == tree->key invalid
printf("不能插入key重复的节点！\r\n");
return NULL;
}
// 调平后，更新节点高度
tree->height = MAX(tree->left, tree->right);
return tree;
}
删除节点
/**
* 删除节点
* tree : 失衡的节点
* key ： 要删除节点的key，整棵树唯一，不能有重复
* return : 调平后的根节点
*/
pAVLTreeNode static delete_avltree( pAVLTreeNode tree, Type key )
{
if ( tree == NULL ) {
return NULL;
} else if ( key < tree->key ) {
// 递归左子树
tree = delete_avltree( tree->left, key );
// 检查是否需要调平
if ( HEIGHT(tree->left) - HEIGHT(tree->right) == 2 ) {
// LL
tree = left_left_rotation(tree);
// LR
tree = left_right_rotation(tree);
}
} else if ( key > tree->key ) {
// 递归右子树
tree = delete_avltree( tree->right, key );
// 检查是否需要调平
if ( HEIGHT(tree->right) - HEIGHT(tree->left) == 2 ) {
// RR
tree = right_right_rotation(tree);
// RL
tree = right_left_rotation(tree);
}
} else {
// 就是要删除的节点
if ( tree->left && tree->right ) {
// 节点的左右子树都存在，需要从左右子节点挑选出高度最高的那棵子树
// 替换删除的节点
if ( HEIGHT(tree->left) > HEIGHT(tree->right) ) {
// 左子树比右子树高，从左子树中找出最大的那个节点进行替换
pAVLTreeNode max = maxnode_avltree( tree->left );
tree->key = max->key;
// 删除左子树中最大的那个节点
tree = delete_avltree(tree->left);
} else {
// 左子树比右子树矮，从右子树中找出最小的那个节点进行替换
pAVLTreeNode min = minnode_avltree( tree->right );
tree->key = min->key;
// 删除左子树中最大的那个节点
tree = delete_avltree(tree->right);
}
} else {
// 只有一个孩子或者没有
pAVLTreeNode pTemp = tree;
tree = tree->left ? tree->left : tree->right;
// 销毁节点
free(pTemp);
}
}
// 修正根节点的高度
tree->height = MAX( HEIGHT(tree->left), HEIGHT(tree->right) );
return tree;
}
查找最小节点
/**
* 查找最小节点
* return : 最小节点
*/
static pAVLTreeNode minnode_avltree( pAVLTreeNode tree )
{
if ( tree == NULL ) return NULL;
while ( tree->left != NULL ){
tree = tree->left;
}
return tree;
}
查找最大节点
/**
* 查找最大节点
* return : 最大节点
*/
static pAVLTreeNode minnode_avltree( pAVLTreeNode tree )
{
if ( tree == NULL ) return NULL;
while ( tree->right != NULL ){
tree = tree->right;
}
return tree;
}
觉得有用就点个赞!
网友评论