快捷導(dǎo)航

C++?AVL樹(shù)的兩單旋和兩雙旋的項(xiàng)目實(shí)踐

更新時(shí)間：2024年03月20日 09:49:41 作者：敲敲er

本文主要介紹了C++?AVL樹(shù)的兩單旋和兩雙旋的項(xiàng)目實(shí)踐,根據(jù)節(jié)點(diǎn)插入位置的不同,AVL樹(shù)的旋轉(zhuǎn)分為四種,下面就來(lái)介紹一下,感興趣的可以了解一下

1. 新節(jié)點(diǎn)插入較高左子樹(shù)的左側(cè)---左左：右單旋

a/b/c分別是高度為h的AVL子樹(shù)

上圖在插入前，AVL樹(shù)是平衡的，新節(jié)點(diǎn)插入到30的左子樹(shù)(注意：此處不是左孩子)中，30左子樹(shù)增加了一層，導(dǎo)致以60為根的二叉樹(shù)不平衡，要讓60平衡，只能將60左子樹(shù)的高度減少一層，右子樹(shù)增加一層，即將左子樹(shù)往上提，這樣60轉(zhuǎn)下來(lái)，因?yàn)?0比30大，只能將其放在30的右子樹(shù)，而如果30有右子樹(shù)，右子樹(shù)根的值一定大于30，小于60，只能將其放在60的左子樹(shù)，旋轉(zhuǎn)完成后，更新節(jié)點(diǎn)的平衡因子即可。在旋轉(zhuǎn)過(guò)程中，有以下幾種情況需要考慮：
1. 30節(jié)點(diǎn)的右孩子可能存在，也可能不存在
2. 60可能是根節(jié)點(diǎn)，也可能是子樹(shù)
如果是根節(jié)點(diǎn)，旋轉(zhuǎn)完成后，要更新根節(jié)點(diǎn)
如果是子樹(shù)，可能是某個(gè)節(jié)點(diǎn)的左子樹(shù)，也可能是右子樹(shù)

代碼

//右單旋
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. 新節(jié)點(diǎn)插入較高右子樹(shù)的右側(cè)---右右：左單旋

左單旋與右單旋的操作類似，只有左右節(jié)點(diǎn)的區(qū)別

代碼

//左單旋
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. 新節(jié)點(diǎn)插入較高左子樹(shù)的右側(cè)---左右：先左單旋再右單旋

參考30和60的相對(duì)位置，將雙旋變成單旋后再旋轉(zhuǎn)，即：先對(duì)30進(jìn)行左單旋，然后再對(duì)90進(jìn)行右單旋，旋轉(zhuǎn)完成后再考慮平衡因子的更新。

代碼

//左右單旋
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. 新節(jié)點(diǎn)插入較高右子樹(shù)的左側(cè)---右左：先右單旋再左單旋

代碼

//右左單旋
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);
	}
}

總結(jié)：
假如以pParent為根的子樹(shù)不平衡，即pParent的平衡因子為2或者-2，分以下情況考慮：
1. pParent的平衡因子為2，說(shuō)明pParent的右子樹(shù)高，設(shè)pParent的右子樹(shù)的根為pSubR。
當(dāng)pSubR的平衡因子為1時(shí)，執(zhí)行左單旋。
當(dāng)pSubR的平衡因子為-1時(shí)，執(zhí)行右左雙旋。
2. pParent的平衡因子為-2，說(shuō)明pParent的左子樹(shù)高，設(shè)pParent的左子樹(shù)的根為pSubL。
當(dāng)pSubL的平衡因子為-1是，執(zhí)行右單旋。
當(dāng)pSubL的平衡因子為1時(shí)，執(zhí)行左右雙旋。
旋轉(zhuǎn)完成后，原pParent為根的子樹(shù)個(gè)高度降低，已經(jīng)平衡，不需要再向上更新。

到此這篇關(guān)于C++ AVL樹(shù)的兩單旋和兩雙旋的項(xiàng)目實(shí)踐的文章就介紹到這了,更多相關(guān)C++ AVL樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: