欧美一级特黄大片做受成人-亚洲成人一区二区电影-激情熟女一区二区三区-日韩专区欧美专区国产专区

數(shù)據(jù)結(jié)構(gòu)(C++):AVL樹(shù)實(shí)現(xiàn)篇-創(chuàng)新互聯(lián)

目錄

成都網(wǎng)站建設(shè)、網(wǎng)站建設(shè)服務(wù)團(tuán)隊(duì)是一支充滿著熱情的團(tuán)隊(duì)，執(zhí)著、敏銳、追求更好，是創(chuàng)新互聯(lián)的標(biāo)準(zhǔn)與要求，同時(shí)竭誠(chéng)為客戶提供服務(wù)是我們的理念。成都創(chuàng)新互聯(lián)公司把每個(gè)網(wǎng)站當(dāng)做一個(gè)產(chǎn)品來(lái)開(kāi)發(fā)，精雕細(xì)琢，追求一名工匠心中的細(xì)致，我們更用心！

1.AVL樹(shù)引入

(1)二叉搜索樹(shù)缺點(diǎn)

(2)AVL樹(shù)簡(jiǎn)介

? [1]問(wèn)題的解決

? [2]AVL樹(shù)的性質(zhì)

2.AVL樹(shù)的插入旋轉(zhuǎn)操作

(1)術(shù)語(yǔ)解釋

(2)左單旋

? [1]插入到右側(cè)的左邊

? [2]插入到右側(cè)的右邊

(3)右單旋

? [1]插入到左側(cè)的左邊

? [2]插入到左側(cè)的右邊

(4)左右雙旋

? [1]插入到右側(cè)的左邊

? [2]插入到右側(cè)的右邊

(5)右左雙旋

? [1]插入到左側(cè)的左邊

? [2]插入到左側(cè)的右邊

3.AVL樹(shù)的局部實(shí)現(xiàn)

(1)AVL樹(shù)的結(jié)點(diǎn)類

(2)AVL樹(shù)成員變量

(3)無(wú)參構(gòu)造?

(4)左單旋

(5)右單旋

(6)左右雙旋

(7)右左雙旋

(8)插入函數(shù)

(9)中序遍歷

(10)析構(gòu)函數(shù)

(11)驗(yàn)證函數(shù)

4.AVL樹(shù)的整體實(shí)現(xiàn)與驗(yàn)證

(1)AVL樹(shù)的整體實(shí)現(xiàn)

(2)AVL樹(shù)的驗(yàn)證

AVL樹(shù)也叫平衡二叉搜索樹(shù)，它是二叉搜索樹(shù)的升級(jí)版，修復(fù)了二叉樹(shù)中存在的缺點(diǎn)，但因此也帶來(lái)了更復(fù)雜的邏輯，所以本文需要搭配大量圖片來(lái)理解。

? 本文在win10系統(tǒng)的vs2019中驗(yàn)證。

1.AVL樹(shù)引入 ? (1)二叉搜索樹(shù)缺點(diǎn)

? 來(lái)看這幅圖，這是用二叉搜索樹(shù)存儲(chǔ)的五個(gè)元素：由于二叉搜索樹(shù)的特性，導(dǎo)致了這棵樹(shù)成為了單支樹(shù)。這樣二叉搜索樹(shù)在中序遍歷時(shí)效率就會(huì)降低，為了解決這樣的缺點(diǎn)，又引入了AVL樹(shù)。(平衡二叉搜索樹(shù))

b3830a37758d4c5c91863410dd009c30.png

(2)AVL樹(shù)簡(jiǎn)介 ? ? [1]問(wèn)題的解決

? AVL樹(shù)是為了解決上述問(wèn)題而出現(xiàn)。如何解決呢？

? 當(dāng)向二叉搜索樹(shù)中插入新結(jié)點(diǎn)后，如果能保證每個(gè)結(jié)點(diǎn)的左右子樹(shù)高度之差的絕對(duì)值不超過(guò)1，就可以降低樹(shù)的高度，從而減少平均搜索長(zhǎng)度。

? 如何使高度之差的絕對(duì)值不超過(guò)1就是AVL樹(shù)的難點(diǎn)，需要對(duì)AVL樹(shù)進(jìn)行調(diào)整，才可以達(dá)到這樣的狀態(tài)，這也是本文的重點(diǎn)。

? [2]AVL樹(shù)的性質(zhì)

? 一棵AVL樹(shù)只有兩個(gè)狀態(tài)：

  • 空樹(shù)
  • 滿足下列性質(zhì)的二叉搜索樹(shù)
  1. 它的左右子樹(shù)都是AVL樹(shù)
  2. 左右子樹(shù)高度之差(平衡因子)的絕對(duì)值不超過(guò)1（也就是說(shuō)，平衡因子可以是1 0 -1）
2.AVL樹(shù)的插入旋轉(zhuǎn)操作 ? (1)術(shù)語(yǔ)解釋

b5ca0cd65bd24ab293beae4ef3ec02f1.png

? 較高左子樹(shù)：如圖，以30為根結(jié)點(diǎn)的樹(shù)，左子樹(shù)有2層，右子樹(shù)只有1層，因此左子樹(shù)就是較高左子樹(shù)。

? 較高右子樹(shù)：如圖，以70為根結(jié)點(diǎn)的樹(shù)，左子樹(shù)只有1層，右子樹(shù)有2層，因此右子樹(shù)就是較高右子樹(shù)。

? 較高左子樹(shù)的左側(cè)/右側(cè)：以30為根結(jié)點(diǎn)的樹(shù)，將新結(jié)點(diǎn)作為0的孩子插入。也就是將新結(jié)點(diǎn)插入較高左子樹(shù)的左側(cè)。

? 較高右子樹(shù)的左側(cè)/右側(cè)：以70為根結(jié)點(diǎn)的樹(shù)，將新結(jié)點(diǎn)作為90的孩子插入。也就是將新結(jié)點(diǎn)插入到較高右子樹(shù)的右側(cè)。

?平衡因子：本文中指定用某個(gè)結(jié)點(diǎn)的右子樹(shù)的高度減去左子樹(shù)的高度的值作為平衡因子。如：30這個(gè)結(jié)點(diǎn)的平衡因子就是(1 - 2) == -1。90這個(gè)結(jié)點(diǎn)的平衡因子就是0。

? 接下來(lái)講解的旋轉(zhuǎn)操作就需要用到平衡因子，本文用bf表示平衡因子。

(2)左單旋

? 將新結(jié)點(diǎn)插入到較高右子樹(shù)的右側(cè)，分為兩類：插入到右側(cè)的左邊，插入到右側(cè)的右邊。(以下幾種情況同理，都會(huì)分左右兩邊) 此時(shí)需要左單旋。

? [1]插入到右側(cè)的左邊

692c85dd7bc6463294ab2eefc380748d.png

? 如圖：左右兩棵子樹(shù)的根結(jié)點(diǎn)用parent表示(注意：這里的根結(jié)點(diǎn)不只是整棵樹(shù)的根結(jié)點(diǎn)，也可以是一棵子樹(shù)的根結(jié)點(diǎn))，右子樹(shù)的根結(jié)點(diǎn)用subR表示，右子樹(shù)的左孩子的根節(jié)點(diǎn)用subRL表示（很好記的，右子樹(shù)的左孩子就是RrightLeft---->RL）。

? 此時(shí)圖一中：parent結(jié)點(diǎn)的平衡因子bf就是 (2 - 1) == 1，subR的平衡因子是0，subRL的平衡因子是0。(后面就不會(huì)仔細(xì)介紹圖片的細(xì)節(jié)了，因?yàn)槎己瓦@個(gè)一樣) 圖一此時(shí)的平衡因子的絕對(duì)值都不大于1，說(shuō)明符合AVL樹(shù)的要求。

? 圖二：將75插入到了右側(cè)的左邊。AVL樹(shù)的插入算法和二叉平衡樹(shù)相比，就是多了各種旋轉(zhuǎn)操作，因此如何尋找結(jié)點(diǎn)的合適位置和二叉搜索樹(shù)是一樣的：根結(jié)點(diǎn)左側(cè)比根節(jié)點(diǎn)小，根節(jié)點(diǎn)右側(cè)比根結(jié)點(diǎn)大。

? 圖二中插入了新結(jié)點(diǎn)后，就應(yīng)該把樹(shù)中的各個(gè)結(jié)點(diǎn)的平衡因子更新，更新后subR的平衡因子更新為1，parent的平衡因子更新為2。(平衡因子的更新是從下到上進(jìn)行更新) 更新后parent的平衡因子的絕對(duì)值大于1，不滿足AVL樹(shù)，就應(yīng)該進(jìn)行調(diào)整。

? 調(diào)整方法：首先將parent結(jié)點(diǎn)的右孩子指針指向subRL，然后將subR的左孩子指針指向parent。這個(gè)過(guò)程簡(jiǎn)單的就是說(shuō)，兒變爹，爹變兒。

? 調(diào)整后：不要忘記從修改這幾個(gè)結(jié)點(diǎn)的平衡因子，可以發(fā)現(xiàn)，這個(gè)情況是將三個(gè)結(jié)點(diǎn)的平衡因子都變成0。

? 這種調(diào)整就像是把雙親結(jié)點(diǎn)旋轉(zhuǎn)到了孩子結(jié)點(diǎn)的左側(cè)，所以叫做左單旋。

? [2]插入到右側(cè)的右邊

b7c3221ceacc416fbb6bd66847ff7b29.png

? 新結(jié)點(diǎn)插入到較高右子樹(shù)的右側(cè)的右邊。這個(gè)情況的處理方法和插入到左邊的處理方式完全相同，這里就不贅述了。

(3)右單旋

? 將新結(jié)點(diǎn)插入到較高左子樹(shù)的左側(cè)。

? [1]插入到左側(cè)的左邊

5d9501ef7e7b411d929090316313542b.png

將新結(jié)點(diǎn)插入到較高左子樹(shù)的左側(cè)的左邊，依舊需要標(biāo)結(jié)點(diǎn)，作為根節(jié)點(diǎn)的parent結(jié)點(diǎn)，根結(jié)點(diǎn)的左孩子subL結(jié)點(diǎn)，左孩子的右孩子subLR，同時(shí)標(biāo)出它們的平衡因子。

? 這種情況的解決的辦法：首先讓parent結(jié)點(diǎn)的左孩子指針指向subLR結(jié)點(diǎn)，然后讓subL結(jié)點(diǎn)的右孩子指針指向parent結(jié)點(diǎn)，然后更新平衡因子，這種情況依舊是將這幾個(gè)結(jié)點(diǎn)平衡因子更新為0。

? 這就像是把雙親結(jié)點(diǎn)旋轉(zhuǎn)到了孩子結(jié)點(diǎn)的右側(cè)，所以叫做右單旋。

? [2]插入到左側(cè)的右邊

b2d483dadc93429694f7afb77edd1780.png

將新結(jié)點(diǎn)插入到較高左子樹(shù)的左側(cè)的右邊，這種情況的處理方法和插入到左邊的方法相同，這里也不再贅述了。

(4)左右雙旋

? 雙旋比單旋要復(fù)雜，所以要仔細(xì)看圖。

? 將新結(jié)點(diǎn)插入到較高左子樹(shù)的右側(cè)。

? [1]插入到右側(cè)的左邊

ade2d5a0e16445318d8a92866b1280c6.png

如圖二：將新結(jié)點(diǎn)插入到了較高左子樹(shù)的右側(cè)的左邊，更新平衡因子后需要調(diào)整。此時(shí)如果按照右單旋的方式調(diào)整，調(diào)整完后依然不滿足條件。(讀者可以試著按右單旋畫(huà)圖，這樣就很好理解了)

? 解決辦法：此時(shí)需要把以subL為根的子樹(shù)進(jìn)行左單旋，從而將整棵樹(shù)轉(zhuǎn)換成可以使用右單旋的狀態(tài)，然后把以parent為根的樹(shù)進(jìn)行右單旋。

? 具體操作：首先把以subL為根的子樹(shù)進(jìn)行左單旋：先讓subL的右孩子指針指向subLR的左孩子，然后讓subLR的左孩子指針指向subL結(jié)點(diǎn)，最后讓parent的左孩子指針指向subLR結(jié)點(diǎn)。左單旋完成。

然后把以parent為根的樹(shù)進(jìn)行右單旋：這里就和右單旋的示意圖一樣了，但為了避免命名混亂，這里希望讀者可以對(duì)照著右單旋的圖看一下。

? 注意：這里的三個(gè)結(jié)點(diǎn)的命名始終沒(méi)有變過(guò)，這三個(gè)名字一直都對(duì)應(yīng)這三個(gè)結(jié)點(diǎn)，這很重要，因?yàn)檫@里跟前面的單旋相比多了一個(gè)步驟。

? 大家仔細(xì)看以下前面的單旋，到最后，單旋的三個(gè)結(jié)點(diǎn)的平衡因子全都更新成0。但是雙旋不一樣，仔細(xì)看圖6，parent的平衡因子是1。

? 總結(jié)：左右雙旋中，如果圖二的subLR的平衡因子是-1，那么圖六中parent的平衡因子將被更新為1。如果圖二的subLR的平衡因子是1，那么圖六中subL的平衡因子將被更新為-1。(第二個(gè)是插入到右側(cè)的右邊的特點(diǎn)，這里提前給出)

? [2]插入到右側(cè)的右邊

745c4d8067ba4e109f5f005edf93ded4.png

如圖二：將新結(jié)點(diǎn)插入到了較高左子樹(shù)的右側(cè)的右邊，需要進(jìn)行雙旋來(lái)調(diào)整。解決辦法和上面差不多，但這里還是要寫(xiě)一下，因?yàn)殡p旋比較復(fù)雜。

? 解決辦法：首先把以subL為根的子樹(shù)進(jìn)行左單旋：先把subL的右孩子指針指向subLR的左孩子，然后讓subLR的左孩子指針指向subL結(jié)點(diǎn)，最后讓parent的左孩子指針指向subLR結(jié)點(diǎn)。

然后把以parent為根的樹(shù)進(jìn)行右單旋，同時(shí)雙旋全都需要考慮平衡因子和單旋的不同。

總結(jié)：左右雙旋中，如果圖二的subLR的平衡因子是-1，那么圖六中parent的平衡因子將被更新為1。如果圖二的subLR的平衡因子是1，那么圖六中subL的平衡因子將被更新為-1。

(5)右左雙旋

? 將新結(jié)點(diǎn)插入到較高右子樹(shù)的左側(cè)。

? [1]插入到左側(cè)的左邊

489e7a2a6dcf44c9934bd1152d29dfe4.png

把新結(jié)點(diǎn)插入到較高右子樹(shù)的左側(cè)的左邊，這種情況也是無(wú)法通過(guò)單旋解決的，需要使用雙旋。

? 如圖二：把新結(jié)點(diǎn)插入到較高右子樹(shù)的左側(cè)的左邊，同時(shí)更新平衡因子，發(fā)現(xiàn)不滿足AVL樹(shù)的條件。

? 解決辦法：把以subR為根的樹(shù)進(jìn)行右單旋，然后把以parent為根的樹(shù)進(jìn)行左單旋，然后和左右雙旋一樣，需要更新圖六的平衡因子。

總結(jié)：左右雙旋中，如果圖二的subRL的平衡因子是-1，那么圖六中subR的平衡因子將被更新為1。如果圖二的subRL的平衡因子是1，那么圖六中parent的平衡因子將被更新為-1。

? [2]插入到左側(cè)的右邊

52e5d55f04f54b38b1208921ac31bbdb.png

把新結(jié)點(diǎn)插入到較高右子樹(shù)的左側(cè)的右邊，這種情況也是無(wú)法通過(guò)單旋解決的，需要使用雙旋。

? 如圖二：把新結(jié)點(diǎn)插入到較高右子樹(shù)的左側(cè)的右邊，同時(shí)更新平衡因子，發(fā)現(xiàn)不滿足AVL樹(shù)的條件。

? 解決辦法：把以subR為根的樹(shù)進(jìn)行右單旋，然后把以parent為根的樹(shù)進(jìn)行左單旋，然后和左右雙旋一樣，需要更新圖六的平衡因子。

總結(jié)：左右雙旋中，如果圖二的subRL的平衡因子是-1，那么圖六中subR的平衡因子將被更新為1。如果圖二的subRL的平衡因子是1，那么圖六中parent的平衡因子將被更新為-1。

3.AVL樹(shù)的局部實(shí)現(xiàn)

? AVL樹(shù)的刪除操作也比較繁瑣，因此本文只主要介紹插入操作。同時(shí)為了方便操作，我們規(guī)定這里實(shí)現(xiàn)的AVL樹(shù)中的元素唯一，不存在相同的。

(1)AVL樹(shù)的結(jié)點(diǎn)類

? AVL樹(shù)就是升級(jí)版的二叉搜索樹(shù)，因此和二叉搜索樹(shù)一樣也需要實(shí)現(xiàn)結(jié)點(diǎn)類來(lái)存儲(chǔ)元素。因?yàn)榻Y(jié)點(diǎn)中可能存儲(chǔ)各種類型的元素，因此也是模板。

? 結(jié)點(diǎn)中有三個(gè)指針：指向此結(jié)點(diǎn)左右孩子的指針，指向此結(jié)點(diǎn)雙親的指針。保存元素的變量，保存平衡因子的變量。

//結(jié)點(diǎn)類
templatestruct AVLTreeNode {
	AVLTreeNode* left;//左孩子指針
	AVLTreeNode* right;//右孩子指針
	AVLTreeNode* parent;//雙親指針
	T value;//存儲(chǔ)元素的變量
	int bf;//平衡因子

	//用傳入的值構(gòu)造結(jié)點(diǎn)
	AVLTreeNode(const T& _value = T())
		:left(nullptr)
		,right(nullptr)
		,parent(nullptr)
		,value(_value)
		,bf(0)
	{}
};
(2)AVL樹(shù)成員變量

? AVL樹(shù)的成員變量只有指向根結(jié)點(diǎn)的指針。這里需要用typedef關(guān)鍵字給結(jié)點(diǎn)類起別名，使用會(huì)更方便。

//AVL樹(shù)類
templateclass AVLTree {
	//給結(jié)點(diǎn)類起別名，方便使用
	typedef AVLTreeNodeNode;
private:
	//指向根結(jié)點(diǎn)的結(jié)點(diǎn)指針
	Node* root;
};
(3)無(wú)參構(gòu)造?
//無(wú)參構(gòu)造
//讓根結(jié)點(diǎn)指針指向空即可
AVLTree()
	:root(nullptr)
{}
(4)左單旋

? 新結(jié)點(diǎn)插入到較高右子樹(shù)的右側(cè)。

? 根據(jù)圖片講解中的步驟進(jìn)行理解。

? 首先讓parent的右孩子指針指向subL，然后讓subR的左孩子指針指向parent，同時(shí)記得更新結(jié)點(diǎn)的雙親指針，最后更新平衡因子。

//左單旋
//以下過(guò)程建議搭配圖片理解
void RotateLeft(Node* parent) {
	//這里的指針設(shè)計(jì)在講解旋轉(zhuǎn)的時(shí)候已經(jīng)解釋過(guò)
	Node* subR = parent->right;
	Node* subRL = subR->left;

	//用pparent(祖父結(jié)點(diǎn))來(lái)保存parent結(jié)點(diǎn)的雙親
	//因?yàn)閜arent并不一定是整棵樹(shù)的根，還有可能只是一棵子樹(shù)的根
	Node* pparent = parent->parent;

	//第一步：首先讓雙親的右孩子指針指向subRL
	parent->right = subRL;

	//之所以要判斷是因?yàn)閟ubRL結(jié)點(diǎn)可能不存在
	if (subRL)
		//更新雙親
		subRL->parent = parent;

	//第二步：讓subR的左孩子指針指向parent
	subR->left = parent;

	//不要忘記給這些結(jié)點(diǎn)更新它們的雙親
	parent->parent = subR;
	subR->parent = pparent;

	//祖父結(jié)點(diǎn)是空，說(shuō)明parent結(jié)點(diǎn)是整棵樹(shù)的根結(jié)點(diǎn)
	if (pparent == nullptr) {
		root = subR;
	}
	//說(shuō)明parent是子樹(shù)的根結(jié)點(diǎn)
	else {
		//原本祖父結(jié)點(diǎn)的孩子是parent
		//經(jīng)過(guò)旋轉(zhuǎn)他的孩子變成了subR
		//需要判斷parent是祖父結(jié)點(diǎn)的左孩子還是右孩子，然后讓對(duì)應(yīng)指針指向subR結(jié)點(diǎn)
		if (pparent->left == parent) {
			pparent->left = subR;
		}
		else {
			pparent->right = subR;
		}
	}
	//更新平衡因子
	parent->bf = subR->bf = 0;
}
(5)右單旋

? 新結(jié)點(diǎn)插入到較高左子樹(shù)的左側(cè)。

? 與左單旋相似，也是兩步走，然后更新雙親指針和平衡因子。

//右單旋
void RotateRight(Node* parent) {
	Node* subL = parent->left;
	Node* subLR = subL->right;

	//祖父結(jié)點(diǎn)
	Node* pparent = parent->parent;

	//第一步：讓parent的左孩子指針指向subLR
	parent->left = subLR;
	//之所以要判斷是因?yàn)閟ubLR結(jié)點(diǎn)可能不存在
	if (subLR)
		subLR->parent = parent;
	//第二步：讓subL的右孩子指針指向parent
	subL->right = parent;

	//更新雙親結(jié)點(diǎn)
	parent->parent = subL;
	subL->parent = pparent;

	//祖父結(jié)點(diǎn)是空，說(shuō)明parent是整棵樹(shù)的根結(jié)點(diǎn)
	if (pparent == nullptr) {
		root = subL;
	}
	//parent是子樹(shù)的根結(jié)點(diǎn)
	else {
		//這里和左單旋一樣
		if (pparent->left == parent) {
			pparent->left = subL;
		}
		else {
			pparent->right = subL;
		}
	}
	//更新平衡因子
	parent->bf = subL->bf = 0;
}
(6)左右雙旋

? 新結(jié)點(diǎn)插入到較高左子樹(shù)的右側(cè)。

? 首先保存初始狀態(tài)的subLR的平衡因子，后面根據(jù)它來(lái)更新其他結(jié)點(diǎn)的平衡因子。然后對(duì)以subL為根的樹(shù)進(jìn)行左單旋，對(duì)以parent為根的樹(shù)進(jìn)行右單旋。

? 最后根據(jù)保存的subLR結(jié)點(diǎn)的平衡因子進(jìn)行更新，如果BF是-1，就把parent的平衡因子更新為1，否則把subL的平衡因子更新為-1。(這里很重要，一定要跟圖片結(jié)合看)

//左右雙旋
void RotateLR(Node* parent) {
	Node* subL = parent->left;
	Node* subLR = subL->right;
	//保存subLR的平衡因子，后面需要根據(jù)它來(lái)更新別的平衡因子
	int BF = subLR->bf;

	//對(duì)以subL為根結(jié)點(diǎn)的樹(shù)進(jìn)行左單旋
	RotateLeft(subL);
	//對(duì)以parent為根結(jié)點(diǎn)的樹(shù)進(jìn)行右單旋
	RotateRight(parent);

	//根據(jù)保存的平衡因子更新
	//當(dāng)subLR平衡因子為-1，將parent的平衡因子更新為1
	if (BF == -1)
		parent->bf = 1;
	//當(dāng)subLR平衡因子不是-1，將subL的平衡因子更新為-1
	else
		subL->bf = -1;
}
(7)右左雙旋

? 新結(jié)點(diǎn)插入到較高右子樹(shù)的左側(cè)。

? 首先保存初始狀態(tài)的subRL的平衡因子，后面根據(jù)它來(lái)更新其他結(jié)點(diǎn)的平衡因子。然后對(duì)以subR為根的樹(shù)進(jìn)行右單旋，對(duì)以parent為根的樹(shù)進(jìn)行左單旋。

? 最后根據(jù)保存的subRL結(jié)點(diǎn)的平衡因子進(jìn)行更新，如果BF是-1，就把subR的平衡因子更新為1，否則把parent的平衡因子更新為-1。(跟左右雙旋一樣，一定要跟圖片結(jié)合看)

//右左雙旋
void RotateRL(Node* parent) {
	Node* subR = parent->right;
	Node* subRL = subR->left;
	//保存subRL的平衡因子，后面根據(jù)它更新其他結(jié)點(diǎn)平衡因子
	int BF = subRL->bf;

	//對(duì)以subR為根的樹(shù)進(jìn)行右單旋
	RotateRight(subR);
	//對(duì)以parent為根的樹(shù)進(jìn)行左單旋
	RotateLeft(parent);

	//根據(jù)保存的subRL平衡因子的不同來(lái)進(jìn)行不同的更新。
	if (BF == -1)
		subR->bf = 1;
	else
		parent->bf = -1;
}
(8)插入函數(shù)

? 插入函數(shù)首先為元素找合適的位置，同時(shí)判斷是否已經(jīng)有相同元素了。成功插入后，需要更新平衡因子，然后對(duì)平衡因子進(jìn)行檢測(cè)，不符合AVL樹(shù)性質(zhì)的，需要根據(jù)情況進(jìn)行單旋或雙旋。

? 如果進(jìn)行了單旋，那么就需要繼續(xù)往上檢測(cè)平衡因子，因?yàn)閱涡罂赡軙?huì)影響上層的平衡因子。但進(jìn)行雙旋后，就可以直接返回了，因?yàn)殡p旋后已經(jīng)處理好了。

//插入函數(shù)
bool Insert(const T& _value) {
	//樹(shù)為空，將新結(jié)點(diǎn)作為根結(jié)點(diǎn)即可
	if (root == nullptr) {
		root = new Node(_value);
		return true;
	}

	//樹(shù)非空
	Node* cur = root;
	//用來(lái)保存cur的雙親結(jié)點(diǎn)
	Node* parent = nullptr;

	//為新結(jié)點(diǎn)的插入尋找合適的位置
	//同時(shí)判斷是否樹(shù)中有相同結(jié)點(diǎn)
	while (cur) {
		parent = cur;
		if (_value< cur->value) {
			cur = cur->left;
		}
		else if (_value >cur->value) {
			cur = cur->right;
		}
		else {
			return false;
		}
	}

	//構(gòu)造新結(jié)點(diǎn)
	cur = new Node(_value);
	//判斷是新結(jié)點(diǎn)應(yīng)該插在雙親的左邊還是右邊
	if (_value< parent->value) {
		parent->left = cur;
	}
	else {
		parent->right = cur;
	}
	//更新新結(jié)點(diǎn)的雙親
	cur->parent = parent;

	//更新平衡因子
	//從下往上
	while (parent) {
		//cur是雙親左孩子
		//左子樹(shù)高度變高，平衡因子就減1
		//平衡因子：右子樹(shù)高度減左子樹(shù)高度
		if (cur == parent->left) {
			parent->bf--;
		}
		//右子樹(shù)變高，平衡因子加1
		else {
			parent->bf++;
		}

		//判斷更新后的平衡因子是否滿足AVL樹(shù)
		//證明parent之前只有一個(gè)孩子，而新結(jié)點(diǎn)插到另一個(gè)空著的位置了
		if (parent->bf == 0) {
			break;
		}
		//證明parent之前沒(méi)有孩子，新結(jié)點(diǎn)插入后只有一個(gè)孩子
		else if (-1 == parent->bf || 1 == parent->bf) {
			cur = parent;
			parent = cur->parent;
		}
		//如下就是parent的平衡因子變成2或-2了
		//需要根據(jù)圖片進(jìn)行理解
		else {
			//說(shuō)明parent的右子樹(shù)高
			if (parent->bf == 2) {
				//根據(jù)cur的平衡因子判斷是左單旋還是右左雙旋
				if (cur->bf == 1)
					RotateLeft(parent);
				else
					RotateRL(parent);
			}
			//parent左子樹(shù)高
			else {
				if (cur->bf == -1)
					RotateRight(parent);
				else
					RotateLR(parent);
			}

			//使用雙旋調(diào)整后就不需要向上繼續(xù)調(diào)整了，可以直接退出循環(huán)
			break;
		}
	}
	return true;
}
(9)中序遍歷

? 根據(jù)中序遍歷規(guī)則：左、根、右。進(jìn)行遍歷即可。

//中序遍歷
void InOrder() {
	cout<< "中序遍歷：";
	InOrder(root);
	cout<< endl;
}

//中序遍歷內(nèi)部實(shí)現(xiàn)
void InOrder(Node* root) {
	if (root) {
		//首先遞歸遍歷左子樹(shù)，然后打印根結(jié)點(diǎn)，最后遞歸遍歷右子樹(shù)
		InOrder(root->left);
		cout<< root->value<< " ";
		InOrder(root->right);
	}
}
(10)析構(gòu)函數(shù)

? 析構(gòu)函數(shù)沒(méi)有參數(shù)，所以需要單獨(dú)實(shí)現(xiàn)一個(gè)銷(xiāo)毀函數(shù)。先遞歸刪除左右子樹(shù)，最后刪除根結(jié)點(diǎn)。

//析構(gòu)函數(shù)
//因?yàn)槲鰳?gòu)函數(shù)無(wú)參數(shù)，需要單獨(dú)定義銷(xiāo)毀函數(shù)
~AVLTree() {
	Destroy(root);
}

//銷(xiāo)毀函數(shù)(和二叉搜索樹(shù)一模一樣)
void Destroy(Node*& root) {
	if (root) {
		//遞歸銷(xiāo)毀根的左子樹(shù)和右子樹(shù)然后刪除根結(jié)點(diǎn)
		Destroy(root->left);
		Destroy(root->right);
		delete root;
		root = nullptr;
	}
}
(11)驗(yàn)證函數(shù)

? 驗(yàn)證函數(shù)通過(guò)高度函數(shù)獲得左右子樹(shù)的高度，進(jìn)而計(jì)算出高度差，同時(shí)將高度差的絕對(duì)值和高度差與平衡因子的比較結(jié)合在一起判斷這棵樹(shù)是否滿足AVL樹(shù)的性質(zhì)。

//驗(yàn)證函數(shù)
bool IsAVLTree() {
	return IsAVLTree(root);
}

//驗(yàn)證函數(shù)主體實(shí)現(xiàn)
bool IsAVLTree(Node* root) {
	if (root == nullptr) {
		return true;
	}
	//計(jì)算根結(jié)點(diǎn)左右子樹(shù)高度
	int leftHeight = Height(root->left);
	int rightHeight = Height(root->right);

	//根據(jù)平衡因子絕對(duì)值 和 子樹(shù)高度差與根結(jié)點(diǎn)平衡因子是否相等
	//判斷是否滿足AVL樹(shù)性質(zhì)
	if (abs(rightHeight - leftHeight) >1 || rightHeight - leftHeight != root->bf) {
		cout<< "結(jié)點(diǎn)值："<< root->value<< "  結(jié)點(diǎn)平衡因子："<< root->bf<< endl;
		return false;
	}

	//遞歸調(diào)用
	return IsAVLTree(root->left) && IsAVLTree(root->right);
}

//求高度函數(shù)
int Height(Node* root) {
	if (root == nullptr) {
		return 0;
	}

	int leftHeight = Height(root->left);
	int rightHeight = Height(root->right);

	return leftHeight >rightHeight ? (leftHeight + 1) : (rightHeight + 1);
}
4.AVL樹(shù)的整體實(shí)現(xiàn)與驗(yàn)證 ? (1)AVL樹(shù)的整體實(shí)現(xiàn)
#include "iostream"
using namespace std;

//結(jié)點(diǎn)類
templatestruct AVLTreeNode {
	AVLTreeNode* left;//左孩子指針
	AVLTreeNode* right;//右孩子指針
	AVLTreeNode* parent;//雙親指針
	T value;//存儲(chǔ)元素的變量
	int bf;//平衡因子

	//用傳入的值構(gòu)造結(jié)點(diǎn)
	AVLTreeNode(const T& _value = T())
		:left(nullptr)
		,right(nullptr)
		,parent(nullptr)
		,value(_value)
		,bf(0)
	{}
};


//AVL樹(shù)類
templateclass AVLTree {
	//給結(jié)點(diǎn)類起別名，方便使用
	typedef AVLTreeNodeNode;
private:
	//指向根結(jié)點(diǎn)的結(jié)點(diǎn)指針
	Node* root;
public:
	//無(wú)參構(gòu)造
	//讓根結(jié)點(diǎn)指針指向空即可
	AVLTree()
		:root(nullptr)
	{}

	//析構(gòu)函數(shù)
	//因?yàn)槲鰳?gòu)函數(shù)無(wú)參數(shù)，需要單獨(dú)定義銷(xiāo)毀函數(shù)
	~AVLTree() {
		Destroy(root);
	}

	//銷(xiāo)毀函數(shù)(和二叉搜索樹(shù)一模一樣)
	void Destroy(Node*& root) {
		if (root) {
			//遞歸銷(xiāo)毀根的左子樹(shù)和右子樹(shù)然后刪除根結(jié)點(diǎn)
			Destroy(root->left);
			Destroy(root->right);
			delete root;
			root = nullptr;
		}
	}

	//左單旋
	//以下過(guò)程建議搭配圖片理解
	void RotateLeft(Node* parent) {
		//這里的指針設(shè)計(jì)在講解旋轉(zhuǎn)的時(shí)候已經(jīng)解釋過(guò)
		Node* subR = parent->right;
		Node* subRL = subR->left;

		//用pparent(祖父結(jié)點(diǎn))來(lái)保存parent結(jié)點(diǎn)的雙親
		//因?yàn)閜arent并不一定是整棵樹(shù)的根，還有可能只是一棵子樹(shù)的根
		Node* pparent = parent->parent;

		//第一步：首先讓雙親的右孩子指針指向subRL
		parent->right = subRL;

		//之所以要判斷是因?yàn)閟ubRL結(jié)點(diǎn)可能不存在
		if (subRL)
			//更新雙親
			subRL->parent = parent;

		//第二步：讓subR的左孩子指針指向parent
		subR->left = parent;

		//不要忘記給這些結(jié)點(diǎn)更新它們的雙親
		parent->parent = subR;
		subR->parent = pparent;

		//祖父結(jié)點(diǎn)是空，說(shuō)明parent結(jié)點(diǎn)是整棵樹(shù)的根結(jié)點(diǎn)
		if (pparent == nullptr) {
			root = subR;
		}
		//說(shuō)明parent是子樹(shù)的根結(jié)點(diǎn)
		else {
			//原本祖父結(jié)點(diǎn)的孩子是parent
			//經(jīng)過(guò)旋轉(zhuǎn)他的孩子變成了subR
			//需要判斷parent是祖父結(jié)點(diǎn)的左孩子還是右孩子，然后讓對(duì)應(yīng)指針指向subR結(jié)點(diǎn)
			if (pparent->left == parent) {
				pparent->left = subR;
			}
			else {
				pparent->right = subR;
			}
		}
		//更新平衡因子
		parent->bf = subR->bf = 0;
	}

	//右單旋
	void RotateRight(Node* parent) {
		Node* subL = parent->left;
		Node* subLR = subL->right;

		//祖父結(jié)點(diǎn)
		Node* pparent = parent->parent;

		//第一步：讓parent的左孩子指針指向subLR
		parent->left = subLR;
		//之所以要判斷是因?yàn)閟ubLR結(jié)點(diǎn)可能不存在
		if (subLR)
			subLR->parent = parent;
		//第二步：讓subL的右孩子指針指向parent
		subL->right = parent;

		//更新雙親結(jié)點(diǎn)
		parent->parent = subL;
		subL->parent = pparent;

		//祖父結(jié)點(diǎn)是空，說(shuō)明parent是整棵樹(shù)的根結(jié)點(diǎn)
		if (pparent == nullptr) {
			root = subL;
		}
		//parent是子樹(shù)的根結(jié)點(diǎn)
		else {
			//這里和左單旋一樣
			if (pparent->left == parent) {
				pparent->left = subL;
			}
			else {
				pparent->right = subL;
			}
		}
		//更新平衡因子
		parent->bf = subL->bf = 0;
	}

	//左右雙旋
	void RotateLR(Node* parent) {
		Node* subL = parent->left;
		Node* subLR = subL->right;
		//保存subLR的平衡因子，后面需要根據(jù)它來(lái)更新別的平衡因子
		int BF = subLR->bf;

		//對(duì)以subL為根結(jié)點(diǎn)的樹(shù)進(jìn)行左單旋
		RotateLeft(subL);
		//對(duì)以parent為根結(jié)點(diǎn)的樹(shù)進(jìn)行右單旋
		RotateRight(parent);

		//根據(jù)保存的平衡因子更新
		//當(dāng)subLR平衡因子為-1，將parent的平衡因子更新為1
		if (BF == -1)
			parent->bf = 1;
		//當(dāng)subLR平衡因子不是-1，將subL的平衡因子更新為-1
		else
			subL->bf = -1;
	}

	//右左雙旋
	void RotateRL(Node* parent) {
		Node* subR = parent->right;
		Node* subRL = subR->left;
		//保存subRL的平衡因子，后面根據(jù)它更新其他結(jié)點(diǎn)平衡因子
		int BF = subRL->bf;

		//對(duì)以subR為根的樹(shù)進(jìn)行右單旋
		RotateRight(subR);
		//對(duì)以parent為根的樹(shù)進(jìn)行左單旋
		RotateLeft(parent);

		//根據(jù)保存的subRL平衡因子的不同來(lái)進(jìn)行不同的更新。
		if (BF == -1)
			subR->bf = 1;
		else
			parent->bf = -1;
	}

	//插入函數(shù)
	bool Insert(const T& _value) {
		//樹(shù)為空，將新結(jié)點(diǎn)作為根結(jié)點(diǎn)即可
		if (root == nullptr) {
			root = new Node(_value);
			return true;
		}

		//樹(shù)非空
		Node* cur = root;
		//用來(lái)保存cur的雙親結(jié)點(diǎn)
		Node* parent = nullptr;

		//為新結(jié)點(diǎn)的插入尋找合適的位置
		//同時(shí)判斷是否樹(shù)中有相同結(jié)點(diǎn)
		while (cur) {
			parent = cur;
			if (_value< cur->value) {
				cur = cur->left;
			}
			else if (_value >cur->value) {
				cur = cur->right;
			}
			else {
				return false;
			}
		}

		//構(gòu)造新結(jié)點(diǎn)
		cur = new Node(_value);
		//判斷是新結(jié)點(diǎn)應(yīng)該插在雙親的左邊還是右邊
		if (_value< parent->value) {
			parent->left = cur;
		}
		else {
			parent->right = cur;
		}
		//更新新結(jié)點(diǎn)的雙親
		cur->parent = parent;

		//更新平衡因子
		//從下往上
		while (parent) {
			//cur是雙親左孩子
			//左子樹(shù)高度變高，平衡因子就減1
			//平衡因子：右子樹(shù)高度減左子樹(shù)高度
			if (cur == parent->left) {
				parent->bf--;
			}
			//右子樹(shù)變高，平衡因子加1
			else {
				parent->bf++;
			}

			//判斷更新后的平衡因子是否滿足AVL樹(shù)
			//證明parent之前只有一個(gè)孩子，而新結(jié)點(diǎn)插到另一個(gè)空著的位置了
			if (parent->bf == 0) {
				break;
			}
			//證明parent之前沒(méi)有孩子，新結(jié)點(diǎn)插入后只有一個(gè)孩子
			else if (-1 == parent->bf || 1 == parent->bf) {
				cur = parent;
				parent = cur->parent;
			}
			//如下就是parent的平衡因子變成2或-2了
			//需要根據(jù)圖片進(jìn)行理解
			else {
				//說(shuō)明parent的右子樹(shù)高
				if (parent->bf == 2) {
					//根據(jù)cur的平衡因子判斷是左單旋還是右左雙旋
					if (cur->bf == 1)
						RotateLeft(parent);
					else
						RotateRL(parent);
				}
				//parent左子樹(shù)高
				else {
					if (cur->bf == -1)
						RotateRight(parent);
					else
						RotateLR(parent);
				}

				//使用雙旋調(diào)整后就不需要向上繼續(xù)調(diào)整了，可以直接退出循環(huán)
				break;
			}
		}
		return true;
	}


	//中序遍歷
	void InOrder() {
		cout<< "中序遍歷：";
		InOrder(root);
		cout<< endl;
	}

	//中序遍歷內(nèi)部實(shí)現(xiàn)
	void InOrder(Node* root) {
		if (root) {
			//首先遞歸遍歷左子樹(shù)，然后打印根結(jié)點(diǎn)，最后遞歸遍歷右子樹(shù)
			InOrder(root->left);
			cout<< root->value<< " ";
			InOrder(root->right);
		}
	}
	


	//驗(yàn)證函數(shù)
	bool IsAVLTree() {
		return IsAVLTree(root);
	}

	//驗(yàn)證函數(shù)主體實(shí)現(xiàn)
	bool IsAVLTree(Node* root) {
		if (root == nullptr) {
			return true;
		}
		//計(jì)算根結(jié)點(diǎn)左右子樹(shù)高度
		int leftHeight = Height(root->left);
		int rightHeight = Height(root->right);

		//根據(jù)平衡因子絕對(duì)值 和 子樹(shù)高度差與根結(jié)點(diǎn)平衡因子是否相等
		//判斷是否滿足AVL樹(shù)性質(zhì)
		if (abs(rightHeight - leftHeight) >1 || rightHeight - leftHeight != root->bf) {
			cout<< "結(jié)點(diǎn)值："<< root->value<< "  結(jié)點(diǎn)平衡因子："<< root->bf<< endl;
			return false;
		}

		//遞歸調(diào)用
		return IsAVLTree(root->left) && IsAVLTree(root->right);
	}

	//求高度函數(shù)
	int Height(Node* root) {
		if (root == nullptr) {
			return 0;
		}

		int leftHeight = Height(root->left);
		int rightHeight = Height(root->right);

		return leftHeight >rightHeight ? (leftHeight + 1) : (rightHeight + 1);
	}
};

int main() {

	int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	AVLTreeavl;

	for (int i = 0; i< 10; i++) {
		avl.Insert(arr[i]);
		avl.InOrder();
	}

	if (avl.IsAVLTree()) {
		cout<< "是AVL樹(shù)"<< endl;
	}
	else {
		cout<< "不是AVL樹(shù)"<< endl;
	}
}
(2)AVL樹(shù)的驗(yàn)證

? 上文代碼的運(yùn)行結(jié)果如下：符合AVL樹(shù)的性質(zhì)。同時(shí)中序遍歷也是一個(gè)升序的序列。

8e108958b3cc4d60976f6a01e0dbad19.png

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享標(biāo)題：數(shù)據(jù)結(jié)構(gòu)(C++):AVL樹(shù)實(shí)現(xiàn)篇-創(chuàng)新互聯(lián)
網(wǎng)站鏈接：http://aaarwkj.com/article16/icidg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開(kāi)發(fā)、App開(kāi)發(fā)、服務(wù)器托管、網(wǎng)站設(shè)計(jì)公司、營(yíng)銷(xiāo)型網(wǎng)站建設(shè)、標(biāo)簽優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

成都定制網(wǎng)站建設(shè)
欧美三级欧美一级视频看| 青青草原在线免费视频| 天堂中文在线免费观看av| 亚洲av日韩精品一区二区| 成熟人妻中文字幕在线看| 久久免费观看性生活片| 日韩欧美中文字幕一区二区| 免费不卡无码毛片观看| 日本在线有码中文视频| av毛片在线播放免费| 国产激情片午夜福利| 人人妻人人澡人人爱| 日本色小姐美国青青草原| 亚洲人妻在线一区二区三区| 亚洲精品在线一二三区| 一区二区三区特黄色片| 九九re久久这里有精品| 熟妇人妻中文字幕在线| 久热伊人精品国产中文| 亚洲欧美中文字幕乱码| 亚洲熟女精品不卡一区二区| 蜜桃久久国产精品一区二区| 日本熟女肥臀一区二区| 99精品国产中文字幕| 国产精品福利午夜在线观看| 人人妻人人澡人人爽久久av| 国产美女精品一区二区三区| 另类视频在线观看免费| 日本一区二区久久人妻高清| 亚洲国产精品第一区第二区| 亚洲美女高清一区二区三区| 熟女人妻视频一区二区| 亚洲乱码中文字幕久久| 另类视频在线免费观看| 免费精品99久久久国产| 日本黄色小网站在线播放| 久久人体午夜激情视频| 国产成人精品久久一区二区| 国产精品中文字幕第一区| 成人国产av一区二区三区| 伊人狼人综合视频在线播放|