快捷導(dǎo)航

C++?AVL樹的兩單旋和兩雙旋的項目實踐

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

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

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

a/b/c分別是高度為h的AVL子樹

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

代碼

//右單旋
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é)點插入較高右子樹的右側(cè)---右右：左單旋

左單旋與右單旋的操作類似，只有左右節(jié)點的區(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é)點插入較高左子樹的右側(cè)---左右：先左單旋再右單旋

參考30和60的相對位置，將雙旋變成單旋后再旋轉(zhuǎn)，即：先對30進行左單旋，然后再對90進行右單旋，旋轉(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é)點插入較高右子樹的左側(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為根的子樹不平衡，即pParent的平衡因子為2或者-2，分以下情況考慮：
1. pParent的平衡因子為2，說明pParent的右子樹高，設(shè)pParent的右子樹的根為pSubR。
當(dāng)pSubR的平衡因子為1時，執(zhí)行左單旋。
當(dāng)pSubR的平衡因子為-1時，執(zhí)行右左雙旋。
2. pParent的平衡因子為-2，說明pParent的左子樹高，設(shè)pParent的左子樹的根為pSubL。
當(dāng)pSubL的平衡因子為-1是，執(zhí)行右單旋。
當(dāng)pSubL的平衡因子為1時，執(zhí)行左右雙旋。
旋轉(zhuǎn)完成后，原pParent為根的子樹個高度降低，已經(jīng)平衡，不需要再向上更新。

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

您可能感興趣的文章: