首页 > 其他 > 详细

平衡二叉树(AVL树)

时间:2014-07-10 22:49:52      阅读:577      评论:0      收藏:0      [点我收藏+]
平衡二叉树:是一颗空树;或者具有以下性质的树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。

平衡二叉树的关键在于插入结点时如何保持整棵树的平衡性。

下面是不平衡发生的四种情况:

(1)平衡二叉树某一节点的左孩子的左子树上插入一个新的节点,使得该节点不再平衡。

LL型(左孩子的左子树)
由于在A的左孩子B的左子树上插入结点F,使A的平衡因子由1增至2而失去平衡。故需进行一次顺时针旋转操作。 即将A的左孩子B向右上旋转代替A作为根结点,A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。

bubuko.com,布布扣

/* return pointer to the new subtree root */
AVLNode *single_rotate_ll(AVLNode *node)	 //LL
{
	AVLNode *p = node->lchild;

	node->lchild = p->rchild;
	p->rchild = node;
	
	node->height = max(height(node->lchild), height(node->rchild)) + 1;
	p->height = max(height(p->lchild), height(p->rchild)) + 1;
	//p->height = max(height(p->lchild), node->height) + 1;

	return p;
}

(2) 平衡二叉树某一节点的右孩子的右子树上插入一个新的节点,使得该节点不再平衡。

RR型平衡旋转法(右孩子的右子树)

由于在A的右孩子C 的右子树上插入结点F,使A的平衡因子由-1减至-2而失去平衡。故需进行一次逆时针旋转操作。即将A的右孩子C向左上旋转代替A作为根结点,A向左下旋转成为C的左子树的根结点。而原来C的左子树则变成A的右子树。

bubuko.com,布布扣

AVLNode *single_rotate_rr(AVLNode *node)	 //RR
{
	AVLNode *p = node->rchild;

	node->rchild = p->lchild;
	p->lchild = node;

	node->height = max(height(node->lchild), height(node->rchild)) + 1;
	p->height = max(height(p->lchild), height(p->rchild)) + 1;
	//p->height = max(node->height, height(p->rchild)) + 1;

	return p;
}

(3)平衡二叉树某一节点的左孩子的右子树上插入一个新的节点,使得该节点不再平衡。

LR型平衡旋转法(左孩子的右子树)
由于在A的左孩子B的右子树上插入结点F,使A的平衡因子由1增至2而失去平衡。故需进行两次旋转操作(先逆时针,后顺时针)。即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置,然后再把该D结点向右上旋转提升到A结点的位置。即先使之成为LL型,再按LL型处理。

bubuko.com,布布扣

AVLNode *double_rotate_lr(AVLNode *node)	//LR
{
	node->lchild = single_rotate_rr(node->lchild);
	return single_rotate_ll(node);
}

(4) 平衡二叉树某一节点的右孩子的左子树上插入一个新的节点,使得该节点不再平衡。

RL型平衡旋转法(右孩子的左子树)
由于在A的右孩子C的左子树上插入结点F,使A的平衡因子由-1减至-2而失去平衡。故需进行两次旋转操作(先顺时针,后逆时针),即先将A结点的右孩子C的左子树的根结点D向右上旋转提升到C结点的位置,然后再把该D结点向左上旋转提升到A结点的位置。即先使之成为RR型,再按RR型处理。

bubuko.com,布布扣

AVLNode *double_rotate_rl(AVLNode *node)	//RL
{
	node->rchild = single_rotate_ll(node->rchild);
	return single_rotate_rr(node);
}
AVl树的结构体为:

typedef struct AVLNode 
{
	int data;
	int height;
	struct AVLNode *lchild, *rchild;
}AVLNode;
计算以node结点为根的树的高度:
int height(AVLNode *node)
{
	if (node == NULL)
		return -1;
	else
		return node->height;
}
现在可以写出avl树的插入代码了:

AVLNode *insert(AVLNode *root, int data)
{
	if (root == NULL)
	{
		root = (AVLNode*)malloc(sizeof(struct AVLNode));
		root->data = data;
		root->lchild = root->rchild = NULL;
		root->height = 0;
	}
	else if (data < root->data)
	{
		root->lchild = insert(root->lchild, data);
		if (height(root->lchild) - height(root->rchild) == 2)   //左子树高度-右子树高度
		{
			if (data < root->lchild->data)	//LL
				root = single_rotate_ll(root);
			else
				root = double_rotate_lr(root);     //LR
		}
	}
	else if (data > root->data)
	{
		root->rchild = insert(root->rchild, data);
		if (height(root->rchild) - height(root->lchild) == 2)	 //右子树高度-左子树高度
		{
			if (data < root->rchild->data)	//RL
				root = double_rotate_rl(root);
			else
				root = single_rotate_rr(root);	   //RR
		}
	}
	//else
	//{}  //data is in the tree already, do nothing

	root->height = max(height(root->lchild), height(root->rchild)) + 1;
	return root;
}


中序遍历avl树:

void inorder_traversal_tree(AVLNode *node)
{
	if (node != NULL)
	{
		inorder_traversal_tree(node->lchild);
		printf("%d ", node->data);
		inorder_traversal_tree(node->rchild);
	}
}


后续遍历以释放树的结点:

void destory_tree(AVLNode*node)
{
	if (node != NULL)
	{
		destory_tree(node->lchild);
		destory_tree(node->rchild);
		free(node), node = NULL;
	}
}


测试代码:

int main()
{
	int arr[] = {3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9};
	AVLNode* T = NULL;
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
		T = insert(T, arr[i]);

	inorder_traversal_tree(T);
	destory_tree(T);
	getchar();
	return 0;
}

参考:AVL树的旋转

平衡二叉树 AVL 的插入节点后旋转方法分析

平衡二叉树(AVL树),布布扣,bubuko.com

平衡二叉树(AVL树)

原文:http://blog.csdn.net/u013071074/article/details/37597611

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!