Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 数据结构 » , ,

AVL树

AVL树是一种自平衡的二叉查找树(Balanced Binary Tree),由于其任意节点的左右子树的高度差至多为一,查找、插入、删除等操作的复杂度在平均和最坏情况下都是O(log n)。AVL树和红黑树都是平衡的二叉查找树,但二者有一些细微的区别,本文将详细讲解AVL树的原理与实现,并且部分实现过程参照了红黑树,具体可以参考 红黑树

简介

AVL树是平衡二叉查找树,它或者是一棵空树,满足是一棵以下两个条件的二叉树:

  • 它的左右两个子树的高度差的绝对值不超过1
  • 左右两个子树也都是平衡二叉树

AVL树首先是一棵二叉查找树,所以一般二叉查找树的操作在这上面是可以同样实现的,比如遍历、搜索,但插入、删除等操作如果直接按照二叉查找树完成可能会破坏AVL树的性质,所以在完成之后需要做一定的修正工作。类似于红黑树,在修正过程中涉及到树的旋转操作,具体的旋转过程请参考红黑树一文。为了表示树的平衡度,每个节点定义了一个平衡因子的概念,具体由其左子树的高度减去右子树的高度得到。因此,平衡因子为-1、0、1的节点都是平衡的,而大于1或小于-1的都是不平衡的,需要进行修正。

AVL树和红黑树性质非常类似,但仍有细微的区别:

  • AVL树是严格平衡的二叉查找树(左右子树高度至多相差一),红黑树是高度平衡的二叉查找树(一棵子树的高度至多是另一棵子树的两倍),于是红黑树的查找性能相对较低。
  • 红黑树的插入操作至多旋转2次、删除操作至多旋转3次,而AVL树则没有相应限制,于是红黑树的插入删除操作性能相对较高。

下面具体介绍AVL树的C++实现过程。
这里的实现是参照红黑树完成的,但没有使用红黑树中的哨兵NIL技术,只是使用普通的NULL指针,于是叶子节点下面不再有NIL节点,这导致部分地方代码不太一致。

节点数据结构

AVL树节点包含1个关键字域、1个高度域以及3个指针域,AVL树结构则只包含一个根节点指针。
为了方便,这里使用struct结构表示,以让成员默认拥有public属性。

struct Node 
{
	int key, height; //关键字、高度
	Node *left, *right, *parent; //左儿子、右儿子、父亲
	Node (int val) : key(val), height(0), left(NULL), right(NULL), parent(NULL) {}
};

struct Tree 
{
	Node *root; //根节点
	Tree () : root(NULL) {}
};

节点查询

对于每个节点,需要在适当的时候获取其平衡因子,具体为左右子树的高度差。这里没有把平衡因子作为节点成员之一,于是每次需要时可以通过以下函数得到。

//获取平衡因子
int getBalance (Node *x) 
{
	Node *l = x->left, *r = x->right;
	if (l && r) return l->height - r->height;
	else if (l) return l->height + 1;
	else if (r) return -r->height - 1;
	else return 0;
}

然后是一般二叉查找树均涉及到的查找操作,以下列举几个后面需要用到的操作。

//非递归查找元素,找到返回关键字的结点指针,没找到返回NULL
Node* searchNode(Tree *tree, int key)
{
	Node *p = tree->root;
	while (p != NULL && key != p->key)
	{
		if (key < p->key) p = p->left;
		else p = p->right;
	}
	return p;
}

//查找最小关键字
Node* searchMin(Tree *tree, Node *x)
{
	//空树时返回NULL
	if (x == NULL) return NULL;

	//一直往左儿子找,直到没有左儿子
	while (x->left != NULL) x = x->left;
	return x;
}

//查找某个结点的后继
Node* searchSuccessor(Tree *tree, Node *x)
{
	//空树
	if (x == NULL) return NULL;

	//有右子树,右子树中最小的那个
	if (x->right != NULL) return searchMin(tree, x->right);

	//无右子树,则为最低的祖先,其左儿子也是祖先
	Node *y = x->parent; //p向上搜索,q为p的父亲
	while (y != NULL &&  x == y->right)
		x = y, y = y->parent;
	return y;
}

最后再写一个AVL树遍历的递归程序,便于后续对结果进行观察。

//前序遍历打印节点
void preorder(Tree *tree, Node *x) 
{
	if (x == NULL) return;

	printf("%-2d left:%2d right:%2d\n", 
		x->key, x->left ? x->left->key: -1, x->right ? x->right->key : -1); //根节点
	preorder(tree, x->left);      //左子树
	preorder(tree, x->right);     //右子树
}

节点更新

当节点经过变动后,需要更新其高度值,具体为左右子树的高度的较大值加一。

//更新高度
void updateHeight (Node *x) 
{
	Node *l = x->left, *r = x->right; 
	if (l && r) x->height = max(l->height, r->height) + 1;
	else if (l) x->height = l->height + 1;
	else if (r) x->height = r->height + 1;
	else x->height = 0;
}

以下是修正时必须涉及的两个旋转操作,代码参考红黑树一文。不同之处是,这里旋转完成后,旋转的点以及其一个儿子的子树发生变动,需要对这两个节点的高度进行修正,其它节点的子树没有变化,于是无需更改。
先是左旋操作:

//左旋
void leftRotate (Tree *tree, Node *x)
{
	//x的右儿子不能为空
	if (x->right == NULL) return;

	//记录图中标识的y节点
	Node *y = x->right;

	//修正x和y的左儿子b之间的链接
	x->right = y->left;
	if (y->left != NULL) y->left->parent = x;

	//修正x的父亲和y之间的链接
	y->parent = x->parent;
	if (x->parent == NULL)   //x为树根
		tree->root = y;
	else if(x == x->parent->left) //x为左儿子
		x->parent->left = y;
	else                          //x为右儿子
		x->parent->right = y;

	//修正x和y之间的链接
	y->left = x;
	x->parent = y;

	updateHeight(x); //更新旋转可能改变的两个节点的高度
	updateHeight(y);
}

再是右旋操作:

//右旋
void rightRotate (Tree *tree, Node *x)
{
	//x的左儿子不能为空
	if (x->left == NULL) return;

	//记录图中标识的y节点
	Node *y = x->left;

	//修正x和y的右儿子b之间的链接
	x->left = y->right;
	if (y->right != NULL) y->right->parent = x;

	//修正x的父亲和y之间的链接
	y->parent = x->parent;
	if (x->parent == NULL)   //x为树根
		tree->root = y;
	else if(x == x->parent->left) //x为左儿子
		x->parent->left = y;
	else                          //x为右儿子
		x->parent->right = y;

	//修正x和y之间的链接
	y->right = x;
	x->parent = y;

	updateHeight(x);  //更新旋转可能改变的两个节点的高度
	updateHeight(y);
}

然后是具体平衡节点的过程。AVL树对于一个节点的平衡相对简单,其情形也较少。如下图所示,z为新插入的节点,根据节点的值的情况,只有四种情况可能导致树变得不平衡:

  1. LL:插入到x的左儿子的左儿子,这时只需对x做一次右旋即可
  2. LR:插入到x的左儿子的右儿子,这时只需对y做一次左旋即可转化为LL的情况,即再对x做一次右旋即可
  3. RL:插入到x的右儿子的左儿子,这时只需对y做一次右旋即可转化为RR的情况,即再对x做一次左旋即可
  4. RR:插入到x的右儿子的右儿子,这时只需对x做一次左旋即可
    x     x     x     x
   /     /       \     \
  y     y         y     y
 /       \       /       \
z         z     z         z

以下是代码实现,首先根据x的平衡因子判断是L还是R的情况,前两种情况下x的平衡因子为-2,后两种情况下x的平衡因子为2。然后根据x的儿子的平衡因子判断是否需要做一次转化,最后再对剩下的LL或RR情况做一次旋转即可。

//平衡节点
void balanceNode (Tree *tree, Node *x) 
{
	int balance = getBalance(x);
	if (balance > 1)
	{
		if (getBalance(x->left) < 0) leftRotate(tree, x->left);
		rightRotate(tree, x);
	}
	else if (balance < -1)
	{
		if (getBalance(x->right) > 0) rightRotate(tree, x->right);
		leftRotate(tree, x);
	}
}

插入节点

介绍完以上更新节点的操作,现在可以真正往AVL树中插入节点了。插入节点的过程跟红黑树以致一般的二叉查找树均非常类似,均是沿着根节点往下走,直到到达叶子节点位置才进行插入。不同的是这里的修正操作是沿着插入的节点一步一步往上进行,直到到达根节点位置。对于到达的每个节点,需要先更新该节点的高度,然后对该节点进行平衡。

//插入节点
void insertNode (Tree *tree, int key)
{
	Node *z = new Node(key);

	// 向下查找待插入的位置,x为当前节点(最终为空节点),y为其父亲
	Node *x = tree->root, *y = NULL;
	while (x != NULL)
	{
		y = x;
		if (z->key == x->key) return;
		else if (z->key < x->key) x = x->left;
		else x = x->right;
	}

	z->parent = y;
	if (y == NULL) tree->root = z;
	else if (z->key < y->key) y->left = z;
	else y->right = z;

	while (z) //反向更新及平衡节点
	{
		updateHeight(z); 
		balanceNode(tree, z);
		z = z->parent;		
	}	
}

删除节点

删除节点的操作也是跟一般的二叉查找树非常类似,首先找到待删除的节点x,然后根据其儿子情况找到真正删除的节点y,y可以是x的后继或者前驱,这里选择使用后继节点,然后把y的值赋给x,删除节点y。而删除后的修正操作则跟插入节点的修正操作类似,即沿着父亲指针一步步往上进行修正。

//删除节点
void deleteNode (Tree *tree, int key)
{
	//查询待删除的节点p,并判断是否为空
	Node *z = searchNode(tree, key); 
	if (z == NULL) return;

	//查找真正删除的节点y及其儿子x
	Node *y = (z->left==NULL || z->right==NULL) ? z : searchSuccessor(tree, z);
	Node *x = (y->left != NULL) ? y->left : y->right;

	//修正删除节点y后,y的父亲和y的儿子之间的链接
	if (x != NULL) x->parent = y->parent;
	if (y->parent == NULL) tree->root = x;
	else if(y == y->parent->left) y->parent->left = x;
	else y->parent->right = x;

	if (y != z) z->key = y->key;

	x = y; //反向更新及平衡节点
	while (x = x->parent)
	{
		updateHeight(x); 
		balanceNode(tree, x);	
	}

	delete(y);
}

AVL树判断

为了验证以上涉及的插入、删除操作是否正确,下面提供一个检验一棵二叉树是否是AVL树的判断程序,主要分成判断该树是否是二叉搜索树和其高度是否平衡等两步进行。判断二叉搜索树时则使用非递归的中序遍历,通过判断遍历结果是否有序得到。判断是否平衡则通过直观的递归算法得到。

//判断是否为二叉搜索树
bool isBST(Node *root)
{
    vector<int> v;
    stack<Node *> s;
    Node *p = root;
    while (p != NULL || !s.empty())
    {
        if (p != NULL)
        {
            s.push(p);
            p = p->left;
        }
        else
        {
            p = s.top(); s.pop();
            v.push_back(p->key);
            p = p->right;
        }
    }
        
    for (int i = 1; i < v.size(); i++)
        if (v[i-1] >= v[i]) return false;
    return true;
}

//判断是否平衡
bool isBalanced(Node *root, int &depth)
{
    if (root == NULL) { depth = 0; return true; }
        
    int l, r;
    if (!isBalanced(root->left, l)) return false;
    if (!isBalanced(root->right, r)) return false;
    if (l - r > 1 || l - r < -1) return false;
    depth = max(l, r) + 1;
    return true;
}

//判断是否为AVL树
bool IsAVL(Node *root)
{
	int depth; //判断是否为二叉搜索树,判断是否平衡
    return isBST(root) && isBalanced(root, depth);
}

测试主程序

最后提供一个测试的主函数,其中相应的头文件需要在程序最开始处包含。
该函数随机生成200个数据,逐个插入到AVL树中并同时判断插入后的树是否满足AVL树要求,然后逐个删除一半的节点并做相同检验。

#include <cstdio>
#include <assert.h>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int main()
{
	Tree avl;

	//随机产生节点数据
	int a[200], n = 200;
	for (int i = 0; i < n; i++) a[i] = rand() % n;

	//插入节点
	for (int i = 0; i < n; i++) 
	{
		insertNode(&avl, a[i]);
		assert(IsAVL(avl.root));
	}
	preorder(&avl, avl.root); printf("\n");

	//删除一半节点
	for (int i = 0; i < n/2; i++)
	{
		deleteNode(&avl, a[i]);
		assert(IsAVL(avl.root));
	}
	preorder(&avl, avl.root); 

	return 0;
}
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论