C++ AVL树的两单旋和两双旋的项目实践

来自:网络
时间:2024-06-09
阅读:

如果在一棵原本是平衡的AVL树中插入一个新节点,可能造成不平衡,此时必须调整树的结构,使之平衡化。根据节点插入位置的不同,AVL树的旋转分为四种。

1. 新节点插入较高左子树的左侧---左左:右单旋

C++ AVL树的两单旋和两双旋的项目实践

a/b/c分别是高度为h的AVL子树

上图在插入前,AVL树是平衡的,新节点插入到30的左子树(注意:此处不是左孩子)中,30左子树增加了一层,导致以60为根的二叉树不平衡,要让60平衡,只能将60左子树的高度减少一层,右子树增加一层,即将左子树往上提,这样60转下来,因为60比30大,只能将其放在30的右子树,而如果30有右子树,右子树根的值一定大于30,小于60,只能将其放在60的左子树,旋转完成后,更新节点的平衡因子即可。在旋转过程中,有以下几种情况需要考虑:
1. 30节点的右孩子可能存在,也可能不存在
2. 60可能是根节点,也可能是子树
如果是根节点,旋转完成后,要更新根节点
如果是子树,可能是某个节点的左子树,也可能是右子树

代码

//右单旋
void RotateR(Node* parent)
{
	Node* SubL = parent->_left;
	Node* subLR = subL->_right;

	parent->_left = subLR;
	if (subLR)
	{
		subL->_right = parent;
	}

	subL->_right = parent;
	Node* ppnode = parent->_parent;
	parent->_parent = subL;

	if (parent == _root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = subL;
		}
		else
		{
			ppnode->_right = subL;
		}
		subL->_parent = ppnode;
	}
	parent->_bf = 0;
	subL->_bf = 0;
}

2. 新节点插入较高右子树的右侧---右右:左单旋

C++ AVL树的两单旋和两双旋的项目实践

左单旋与右单旋的操作类似,只有左右节点的区别

 代码

//左单旋
void RotateL(Node* parent)
{
	Node* SubR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	if (subRL)
	{
		subR->_left = parent;
	}

	subR->_left = parent;
	Node* ppnode = parent->_parent;
	parent->_parent = subR;

	if (parent == _root)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = subR;
		}
		else
		{
			ppnode->_right = subR;
		}
		subR->_parent = ppnode;
	}
	parent->_bf = 0;
	subR->_bf = 0;
	
}

3. 新节点插入较高左子树的右侧---左右:先左单旋再右单旋

C++ AVL树的两单旋和两双旋的项目实践

参考30和60的相对位置,将双旋变成单旋后再旋转,即:先对30进行左单旋,然后再对90进行右单旋,旋转完成后再考虑平衡因子的更新。

代码 

//左右单旋
void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;
	RotateL(parent->_left);
	RotateR(parent);

	if (bf == 1)
	{
		parent->_bf = 0;
		subL->_bf = 0;
		subLR->_bf = 1;
	}
	else if (bf == -1)
	{
		parent->_bf = 0;
		subL->_bf = -1;
		subLR->_bf = 0;
	}
	else if(bf==0)
	{
		parent->_bf = 0;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

4. 新节点插入较高右子树的左侧---右左:先右单旋再左单旋

C++ AVL树的两单旋和两双旋的项目实践

代码

//右左单旋
void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;
	RotateR(parent->_right);
	RotateL(parent);

	if (bf == 1)
	{
		parent->_bf = 0;
		subR->_bf = 0;
		subRL->_bf = 1;
	}
	else if (bf == -1)
	{
		parent->_bf = 0;
		subR->_bf = -1;
		subRL->_bf = 0;
	}
	else if (bf == 0)
	{
		parent->_bf = 0;
		subR->_bf = 0;
		subRL->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

总结:
假如以pParent为根的子树不平衡,即pParent的平衡因子为2或者-2,分以下情况考虑:
1. pParent的平衡因子为2,说明pParent的右子树高,设pParent的右子树的根为pSubR。
当pSubR的平衡因子为1时,执行左单旋。
当pSubR的平衡因子为-1时,执行右左双旋。
2. pParent的平衡因子为-2,说明pParent的左子树高,设pParent的左子树的根为pSubL。
当pSubL的平衡因子为-1是,执行右单旋。
当pSubL的平衡因子为1时,执行左右双旋。
旋转完成后,原pParent为根的子树个高度降低,已经平衡,不需要再向上更新。

返回顶部
顶部