远航休息栈
首页 > 笔记 > 各种树结构之二 AVL树

各种树结构之二 AVL树

闲话不多说

接着来

二叉搜索树的深度与搜索效率

一个有n个节点的二叉树，它的最小深度为log(n)，最大深度为n。比如下面两个二叉树:
images

深度为n

images深度为log(n)

这两个二叉树同时也是二叉搜索树(参考这里)。注意，log以2为基底。log(n)是指深度的量级。根据我们对深度的定义，精确的最小深度为floor(log(n)+1)。

我们将处于同一深度的节点归为一层。如果除最后一层外的其他层都被节点填满时，二叉树有最小深度log(n)。

二叉搜索树的深度越小，那么搜索所需要的运算时间越小。一个深度为log(n)的二叉搜索树，搜索算法的时间复杂度也是log(n)。然而，我们在二叉搜索树中已经实现的插入和删除操作并不能让保持log(n)的深度。如果我们按照8，7，6，5，4，3，2，1的顺序插入节点，那么就是一个深度为n的二叉树。那么，搜索算法的时间复杂度为n。

n和log(n)的时间复杂度意味着什么呢？时间复杂度代表了完成算法所需要的运算次数。时间复杂度越小，算法的速度越快。

images

可以看到，随着元素的增加，log(n)的时间复杂度的增长要远小于n。所以，我们自然希望二叉搜索树能尽可能保持log(n)的深度。在上面深度为n的例子中，我们发现，每个节点只有左节点被填满。树的每一层都有很多空位。能不能尽可能减少每一层的空位呢？ (相应的，减少树的深度)

一种想法是先填满一层，再去填充下一层，这样就是一个完全二叉树(complete binary tree)。这样的二叉树实现插入算法会比较复杂。所以今天介绍一种思路相似，但比较容易实现的树状数据结构——AVL树。

AVL树

AVL树是最先发明的自平衡二叉查找树，也被称为高度平衡树。相比于”二叉查找树”，它的特点是：AVL树中任何节点的两个子树的高度最大差别为1。

如下图:

images

AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。

如果在AVL树中插入或删除节点后，使得高度之差大于1。此时，AVL树的平衡状态就被破坏，它就不再是一棵二叉树；为了让它重新维持在一个平衡状态，就需要对其进行旋转处理。学AVL树，重点的地方也就是它的旋转算法；在后文的介绍中，再来对它进行详细介绍。

AVL树的实现

1.基本定义

1.1树的节点

typedef int datatype;

typedef struct avltrees
{
	datatype key;
	int height;
	struct avltrees *rson;
	struct avltrees *lson;
}avlnode,*avltree;

1.2获取高度

#define height(p) ((p==NULL) ? -1 :(((avlnode *)(p))->height))

1.3 计算高度

两子树高度最大者加一

int count_height(avlnode *x)
{
	return (max(height(x->lson),height(x->rson))+1)
}

2. 旋转
前面说过，如果在AVL树中进行插入或删除节点后，可能导致AVL树失去平衡。这种失去平衡的可以概括为4种姿态：LL(左左)，LR(左右)，RR(右右)和RL(右左)。下面给出它们的示意图：

images

总的来说，AVL树失去平衡时的情况一定是LL、LR、RL、RR这4种之一，它们都由各自的定义：

(1) LL：LeftLeft，也称为”左左”。插入或删除一个节点后，根节点的左子树的左子树还有非空子节点，导致”根的左子树的高度”比”根的右子树的高度”大2，导致AVL树失去了平衡。
例如，在上面LL情况中，由于”根节点(8)的左子树(4)的左子树(2)还有非空子节点”，而”根节点(8)的右子树(12)没有子节点”；导致”根节点(8)的左子树(4)高度”比”根节点(8)的右子树(12)”高2。

(2) LR：LeftRight，也称为”左右”。插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，导致”根的左子树的高度”比”根的右子树的高度”大2，导致AVL树失去了平衡。
 例如，在上面LR情况中，由于”根节点(8)的左子树(4)的左子树(6)还有非空子节点”，而”根节点(8)的右子树(12)没有子节点”；导致”根节点(8)的左子树(4)高度”比”根节点(8)的右子树(12)”高2。

(3) RL：RightLeft，称为”右左”。插入或删除一个节点后，根节点的右子树的左子树还有非空子节点，导致”根的右子树的高度”比”根的左子树的高度”大2，导致AVL树失去了平衡。
例如，在上面RL情况中，由于”根节点(8)的右子树(12)的左子树(10)还有非空子节点”，而”根节点(8)的左子树(4)没有子节点”；导致”根节点(8)的右子树(12)高度”比”根节点(8)的左子树(4)”高2。

(4) RR：RightRight，称为”右右”。插入或删除一个节点后，根节点的右子树的右子树还有非空子节点，导致”根的右子树的高度”比”根的左子树的高度”大2，导致AVL树失去了平衡。
例如，在上面RR情况中，由于”根节点(8)的右子树(12)的右子树(14)还有非空子节点”，而”根节点(8)的左子树(4)没有子节点”；导致”根节点(8)的右子树(12)高度”比”根节点(8)的左子树(4)”高2。

前面说过，如果在AVL树中进行插入或删除节点后，可能导致AVL树失去平衡。AVL失去平衡之后，可以通过旋转使其恢复平衡，下面分别介绍”LL(左左)，LR(左右)，RR(右右)和RL(右左)”这4种情况对应的旋转方法。

2.1 LL的旋转

LL失去平衡的情况，可以通过一次旋转让AVL树恢复平衡。如下图：

images

图中左边是旋转之前的树，右边是旋转之后的树。从中可以发现，旋转之后的树又变成了AVL树，而且该旋转只需要一次即可完成。
对于LL旋转，你可以这样理解为：LL旋转是围绕”失去平衡的AVL根节点”进行的，也就是节点k2；而且由于是LL情况，即左左情况，就用手抓着”左孩子，即k1″向上拔。将k1变成根节点，k2变成k1的右子树，”k1的右子树”变成”k2的左子树”。

LL的旋转代码

avlnode *left_left_rotation(avlnode *k2)
{
	avlnode *k1=k2->lson;
	k2->lson=k1->rson;
	k1->rson=k2;

	k1->height=count_height(k1);
	k2->height=count_height(k2);

	return k1;
}

 

2.2 RR的旋转

理解了LL之后，RR就相当容易理解了。RR是与LL对称的情况！RR恢复平衡的旋转方法如下：

images

图中左边是旋转之前的树，右边是旋转之后的树。RR旋转也只需要一次即可完成。

RR的旋转代码

avlnode *right_right_rotation(avlnode *k1)
{
	avlnode *k2=k1->rson;
	k1->rson=k2->lson;
	k2->lson=k1;

	k2->height=count_height(k1);
	k2->height=count_height(k2);

	return k2;
}

 

2.3 LR的旋转

LR失去平衡的情况，需要经过两次旋转才能让AVL树恢复平衡。如下图：

images

第一次旋转是围绕”k1″进行的”RR旋转”，第二次是围绕”k3″进行的”LL旋转”。

LR的旋转代码

avlnode *left_right_rotation(avlnode *k3)
{
	k3->lson=right_right_rotation(k3->lson);

	return left_left_rotation(k3);
}

 

2.4 RL的旋转

RL是与LR的对称情况！RL恢复平衡的旋转方法如下：

images

第一次旋转是围绕”k3″进行的”LL旋转”，第二次是围绕”k1″进行的”RR旋转”。

RL的旋转代码

avlnode *right_left_rotation(avlnode *k1)
{
	k1->rson=left_left_rotation(k1->rson);

	return right_right_rotation(k1);
}

 

3. 插入

对于AVL树，可以证明，在新增一个节点时，总可以通过一次旋转恢复AVL树的性质。

当我们插入一个新的节点时，在哪里旋转？是用单旋转还是双旋转?

我们按照如下基本步骤进行：

1. 按照二叉搜索树的方式增加节点，新增节点称为一个叶节点。

2. 从新增节点开始，回溯到第一个失衡节点(5)。

(如果回溯到根节点，还没有失衡节点，就说明该树已经符合AVL性质。)

3. 找到断的边(5->3)，并确定断弦的方向(5的左侧)

4. 以断边下端(3)为根节点，确定两个子树中的哪一个深度大(左子树还是右子树)。

(这两棵子树的深度不可能相等，而且深度大的子树包含有新增节点。)

5. 如果第2和第3步中的方向一致(都为左或者都为右)，需要单旋转以失衡节点为根节点的子树。

否则，双旋转以失衡节点为根节点的子树。

插入节点的代码

avlnode *tree_insert(avltree t,datatype key)
{
	if (t==NULL)
	{
		t=create_node(key,NULL,NULL);
	}
	else
	if (key < t->key)
	{
		t->lson=tree_insert(t->lson,key);
		if (height(t->lson)-height(t->rson)==2)
		{
			//if (t->lson->rson==NULL)
			if (key<t->lson->key)
				t=left_left_rotation(t);
			else
				t=left_right_rotation(t);
		}
	}
	else
	if (key > t->key)
	{
		t->rson=tree_insert(t->rson,key);
		if (height(t->rson)-height(t->lson)==2)
		{
			//if (t->rson->lson==NULL)
			if (key>t->rson->key)
				t=right_right_rotation(t);
			else
				t=right_left_rotation(t);
		}
	}
	else
	{
		error();
	}
	t->height=count_height(t);
	return t;
}

4.删除

删除的方案有很多，但一般都会旋转下面这种，因为对整棵树各个分支深度的影响较小。

a.当被删除节点n是叶子节点，直接删除

b.当被删除节点n只有一个孩子，删除n，用孩子替代该节点的位置

c.当被删除结点n存在左右孩子时，真正的删除点是左子树最大的节点或右子树中最小的节点，之后n的值替换为真正删除点的值。这就把c归结为a，b的问题。

删除节点的代码

avlnode *delete_node(avltree t,avlnode *x)
{
	if (t==NULL || x==NULL)
		return NULL;
	if (x->key < t->key)
	{
		t->lson=delete_node(t->lson,x);
		if (height(t->rson)-height(t->lson)==2)
		{
			if (height(t->rson->lson)<height(t->rson->rson))
				right_right_rotation(t);
			else
				right_left_rotation(t);
		}
	}
	else
	if (x->key > t->key)
	{
		t->rson=delete_node(t->rson,x);
		if (height(t->lson)-height(t->rson)==2)
		{
			if (height(t->lson->lson)>height(t->lson->rson))
				t=left_left_rotation(t);
			else
				t=left_right_rotation(t);
		}
	}
	else
	if (x->key == t->key)
	{
		if (t->lson && t->rson)
		{
			if (height(t->lson)>height(t->rson))
			{
				avlnode *y;
				y=tree_max(x->lson);
				t->key=y->key;
				t->lson=delete_node(t->lson,y);
			}
			else
			{
				avlnode *y;
				t=tree_min(t->rson);
				t->key=y->key;
				t->rson=delete_node(t->rson,y);
			}
		}
		else
		{
			avlnode *y=t;
			t=t->lson ? t->lson : t->rson;
			free(t);
		}
	}
	else
	{
		error();
	}
	return t;
}

其他的操作和bst一样

参见 这里

The end.