平衡二叉树的基本操作

写在前面：在学习平衡二叉树之前我们必须对二叉查找树有所了解，请参阅我的另一篇博文http://blog.csdn.net/heart_love/article/details/50943089

一、平衡二叉树的定义

平衡二叉树又称AVL树(AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在1962年的论文

"An algorithm for the organization of information"中发表了它。 )，它是二叉查找树的一种变体，除了满足二叉查找树的性质之外还要满足如下性质：①根节点的左子树深度和右子树的深度之差的绝对值小于2；②左子树和右子树也是一棵平衡二叉树。

既然有了二叉查找树，为何又要发明平衡二叉树？我们知道二叉查找树在插入操作的过程中，比如说要向二叉树

中依次插入节点K1<K2<K3<K4，那么二叉查找树就退变成了链表，对链表的插入、删除、查找的操作时间为O(n)，然而对于平衡二叉树的插入、删除、查找的操作时间为O(lgn)。

二、AVL树的基本操作

1、在介绍AVL树的基本操作之前，我们先来看看AVL树失衡的情况。

①左左情况：如图一所示，K1的左子树的高度与右子树的高度之差为2，所以以K1位根节点的树不是平衡二叉树，K1为失衡的节点。以K1的左孩子K2为根的子树，K2的左子树的高度大于右孩子的高度，所以这样失衡的树为左左情况。我们通过旋转来保持二叉树的平衡性质。以K2为支撑柱，拿着节点K3顺时针转动，然后再调整各节点所指向的指针。

②右右情况：如图二所示，其实右右情况与左左情况是镜像对称的。这里就不再赘述，看图就能明白一切。

③左右情况：如图三所示，K1的左子树的高度与右子树的高度之差为2，所以以K1位根节点的树不是平衡二叉树，K1为失衡的节点。以K1的左孩子K2为根的子树，K2的右子树的高度大于左孩子的高度，所以这样失衡的树为左右情况。我们先对K1的左子树根K2进行右右情况的旋转，然后再以K1为根进行左左情况旋转，也就是进行双旋转。

④右左情况：如图四所示，右左情况和左右情况是镜像对称的，这里也不在赘述。

2、插入和删除操作

平衡二叉树的插入和删除操作很有可能会改变平衡性质，这时我们就要对这棵非平衡的二叉树进行旋转操

作来保持其平衡性质。基本思路是这样：如果是插入操作，因为插入到树中的节点永远是叶子节点，所以我们要沿着插入节点过程的逆方向来寻找最小失衡子树；如果是删除操作，删除节点的左子树有可能会成为非平衡最小二叉树。当调整最小失衡子树为平衡子树时，不会影响其他平衡子树的性质，当所有的最小失衡子树调整为平衡子树时，整个二叉树也就是平衡二叉树了。

3、代码

#include <iostream>

using namespace std;
typedef int ElemType;
/*节点结构*/
typedef struct node
{
	ElemType key;
	struct node *parent, *lchid, *rchild;
}BNode,*BTree;
/*******************二叉树的基本操作*****************************************/
/*获取树的高度*/
int get_depth(BTree root);
/*判断一棵树是不是平衡二叉树*/
bool isBanlace_tree(BTree root);
/*平衡二叉树的插入操作*/
bool insert_tree(BTree *root, ElemType e);
/*平衡二叉树的删除操作*/
bool delete_tree(BTree *root, ElemType e);
/*******************二叉树的基本操作的一些辅助函数*******************************/
/*调整失衡的二叉树，*root为删除或添加的节点的指针*/
void keep_banlace(BTree *root, BTree check);
/*当一棵树不是平衡二叉树的时候需要做的旋转,root为失衡子树的根节点*/
void LL_Rotate(BTree *root,BTree rotate);//情况一:左左情况
void RR_Rotate(BTree *root,BTree rotate);//情况二:右右情况
void LR_Rotate(BTree *root,BTree rotate);//情况三:左右情况
void RL_Rotate(BTree *root,BTree rotate);//情况四:右左情况
/*用节点v替换节点u*/
void replace_node(BTree *root, BTree u, BTree v);
int main()
{
	BTree root = NULL;
	insert_tree(&root, 5);
	insert_tree(&root, 4);
	insert_tree(&root, 3);
	insert_tree(&root, 2);
	insert_tree(&root, 1);
	insert_tree(&root, 6);
	insert_tree(&root, 7);
	insert_tree(&root, 8);
	delete_tree(&root, 2);
	delete_tree(&root, 1);
	if (isBanlace_tree(root))
	{
		cout << "是平衡二叉树" << endl;
	}
	else
	{
		cout << "不是平衡二叉树" << endl;
	}
}

/*获取树的高度*/
int get_depth(BTree root)
{
	if (root == NULL)
		return 0;
	int left, right, height;
	left = get_depth(root->lchid);
	right = get_depth(root->rchild);
	height = left > right ? (left +1) : (right+1);//树的高度等于max(左子树的高度，右子树的高度)+1

	return height;
}
/*根据平衡二叉树的定义：
1、根节点的左子树和右子树的深度值差不能不大于1,
2、并且其左右子树也是一颗平衡二叉树*/
bool isBanlace_tree(BTree root)
{
	if (root == NULL)
		return true;
	int left, right, diff;

	left = get_depth(root->lchid);
	right = get_depth(root->rchild);

	diff = left - right;
	if (diff > 1 || diff < -1)
		return false;
	return (isBanlace_tree(root->lchid) && isBanlace_tree(root->rchild));
}

bool insert_tree(BTree *root, ElemType e)
{
	/*构造并初始化节点*/
	BTree temp = (BTree)malloc(sizeof(BNode));
	temp->parent = NULL;
	temp->lchid = NULL;
	temp->rchild = NULL;
	temp->key = e;
	/*为空树则直接插入*/
	if (*root == NULL)
	{
		*root = temp;
		return true;
	}
	/*不为空树，在插入的过程中需要保持平衡*/
	BTree x = *root;
	BTree y = x;
	while (x != NULL && x->key != e)
	{
		y = x;
		if (x->key > e)
			x = x->lchid;
		else
			x = x->rchild;
	}
	if (x != NULL)//说明树中存在相等的key
		return false;
	if (y->key > e)
		y->lchid = temp;
	else
		y->rchild = temp;
	temp->parent = y;
	keep_banlace(root, temp->parent);
	return true;
}

/*平衡二叉树的删除操作：
1、删除的节点没有孩子节点
2、删除的节点只有一个孩子节点
3、删除的节点有两个孩子节点*/
bool delete_tree(BTree *root, ElemType e)
{
	BTree x;//用来保存指向有可能会是最小非平衡子树的根节点
	BTree temp = *root;
	/*找到要删除的节点*/
	while (temp != NULL && temp->key != e)
	{
		if (temp->key > e)
			temp = temp->lchid;
		else
			temp = temp->rchild;
	}
	if (temp == NULL)//没有找到该节点
		return 0;

	/*删除的节点有两个孩子节点*/
	BTree y;
	if (temp->lchid != NULL && temp->rchild != NULL)
	{
		/*找z的后继y*/
		y = temp->rchild;
		while (y->lchid != NULL)
			y = y->lchid;
		if (y == temp->rchild)//节点y是z的左孩子
		{
			replace_node(root, temp, y);
			y->lchid = temp->lchid;
			temp->lchid->parent = y;
			/*如果是这种情况那么在删除后，以z->parent为根节点的树可能会成为最小非平衡子树*/
			x = temp->parent;
		}			
		else
		{
			replace_node(root, y, y->rchild);
			replace_node(root, temp, y);
			y->lchid = temp->lchid;
			temp->lchid->parent = y;

			y->rchild = temp->rchild;
			temp->rchild->parent = y;
			/*如果是这种情况那么在删除后，以z->rchild为树根的树的左子树的高度会降低,有可能会成为最小非平衡子树*/
			x = temp->rchild;
		}
	}
	/*有一个孩子节点*/
	else if (temp->lchid != NULL || temp->rchild != NULL)
	{
		if (temp->lchid != NULL)
			replace_node(root, temp, temp->lchid);
		else
			replace_node(root, temp, temp->rchild);
		/*如果是这种情况那么在删除后,以z->parent为根节点的树可能会成为最小非平衡子树*/
		x = temp->parent;
	}
	/*没有孩子节点*/
	else
	{
		replace_node(root, temp, NULL);
		/*如果是这种情况那么在删除后，以z->parent为根节点的树可能会成为最小非平衡子树*/
		x = temp->parent;
	}

	/*完成删除之后，我们要保持删除之后的树任然为平衡二叉树*/

	keep_banlace(root,x);
	free(temp);
	return true;
}

/*调整失衡的二叉树:
首先在插入(或删除)新结点处沿着树向上找到失去平衡的最小子树根结点的指针。
然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。
当失去平衡的最小子树被调整为平衡子树后，原有其他所有平衡子树无需调整，
整个二叉排序树就又成为一棵平衡二叉树。*/
void keep_banlace(BTree *root,BTree check)
{
	int left, right, diff;
	while (check != NULL)//从check节点开始检查是否为平衡二叉树
	{
		left = get_depth( check->lchid);
		right = get_depth(check->rchild);
		diff = left - right;

		if (diff > 1 || diff < -1)//不是平衡二叉树
		{
			if (diff > 1)
			{
				/*左左情况*/
				if (get_depth(check->lchid->lchid) > get_depth(check->lchid->rchild))
				{
					LL_Rotate(root,check);
				}
				else//左右情况
				{
					RR_Rotate(root,check);
					LL_Rotate(root,check);
				}
			}
			else
			{
				/*右右情况*/
				if (get_depth(check->rchild->rchild) > get_depth(check->rchild->lchid))
				{
					RR_Rotate(root,check);
				}
				else
				{
					LL_Rotate(root,check);
					RR_Rotate(root,check);
				}
			}
			check = check->parent->parent;
		}
		else
			check = check->parent;
	}
}
/*情况一:左左情况
失衡节点的左子树高度-左子树高度>1
失衡节点的左孩子的左子树高度大于失衡节点的左孩子的右子树高度
*/
void LL_Rotate(BTree *root, BTree rotate)
{
	BTree temp = rotate->lchid;
	if (rotate->parent == NULL)
	{
		*root = temp;
	}
	else
	{
		if (rotate->parent->lchid == rotate)
			rotate->parent->lchid = temp;
		else
			rotate->parent->rchild = temp;
	}
	temp->parent = rotate->parent;

	rotate->parent = temp;
	rotate->lchid = temp->rchild;

	temp->rchild = rotate;

}

void RR_Rotate(BTree *root, BTree rotate)//情况二:右右情况,与情况一是镜像的
{
	BTree temp = rotate->rchild;
	if (rotate->parent == NULL)
	{
		*root = temp;
	}
	else
	{
		if (rotate->parent->lchid == rotate)
			rotate->parent->lchid = temp;
		else
			rotate->parent->rchild = temp;
	}
	temp->parent = rotate->parent;

	rotate->parent = temp;
	rotate->rchild = temp->lchid;

	temp->lchid = rotate;
}
/*情况三:左右情况
失衡节点的左子树高度-左子树高度>1
失衡节点的左孩子的左子树高度小于失衡节点的左孩子的右子树高度*/
void LR_Rotate(BTree *root, BTree rotate)//情况三:左右情况
{
	/*先右右情况的旋转*/
	RR_Rotate(root,rotate->lchid);
	/*再左左情况的旋转*/
	LL_Rotate(root,rotate);
}
void RL_Rotate(BTree *root, BTree rotate)//情况四:右左情况,与情况三镜像对称
{
	/*先左左情况的旋转*/
	LL_Rotate(root,rotate->rchild);
	/*再右右情况的旋转*/
	RR_Rotate(root, rotate);
}
/*用节点v替换节点u*/
void replace_node(BTree *root, BTree u, BTree v)
{
	if (u->parent == NULL)
		*root = v;
	else if (u == u->parent->lchid)
		u->parent->lchid = v;
	else
		u->parent->rchild = v;
	if (v != NULL)
		v->parent = u->parent;
}

每行代码都有详细的注释，你可以通过加断点调试来验证代码的正确性。

秒客网

平衡二叉树的基本操作

相关文章