欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++中AVL樹的底層以及實現(xiàn)方法總結

 更新時間：2024年10月14日 10:11:49   作者：夜晚中的人海  
這篇文章主要介紹了C++中AVL樹的底層以及實現(xiàn)方法的相關資料,AVL樹是一種自平衡的二叉搜索樹,每個節(jié)點的左右子樹高度差不超過1,通過旋轉操作保持平衡,詳解了AVL樹的結構、插入、旋轉、查找和遍歷方法,展示了其保持平衡的機制及對應代碼實現(xiàn),需要的朋友可以參考下

一、AVL樹的概念

AVL樹是一種高度平衡的平衡二叉樹，相比于搜索二叉樹，它的特點在于左右子樹都為AVL樹且樹的高度差的絕對值不超過1。這里我們會引入一個新的概念叫做平衡因子。平衡因子也就是左右子樹的高度差，我們可以通過平衡因子方便我們后續(xù)去觀察和控制樹是否平衡。

二、AVL樹的性質

AVL樹主要有三大性質：

1.每棵樹的左右子樹都是AVL樹。

2.左子樹和右子樹的高度之差的絕對值不超過1。

3.每個節(jié)點都會有一個平衡因子，且任何一個節(jié)點的平衡因子都為1、0、-1。

三、AVL樹的實現(xiàn)

1. 樹的基本結構

AVL樹的結點包含了左右節(jié)點的指針以及父親節(jié)點的指針，同時還有有key、value以及代表樹平衡的平衡因子。

template<class K, class V>
struct AVLTreeNode
{
	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	//平衡因子
	int _bf; 
	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}
};

2. 樹的插入

樹的插入按照搜索二叉樹的規(guī)則進行插入。插入節(jié)點后更新平衡因子，如果沒有違反規(guī)則(即沒有導致節(jié)點的平衡因子變成2/-2)，則插入結束；如果違反規(guī)則，則樹會不平衡，需要進行旋轉操作。

平衡因子的更新規(guī)則：

1.平衡因子 = 右子樹高度 - 左子樹高度。

2.只有子樹高度的變化才會影響當前節(jié)點的平衡因子。

3.插入節(jié)點后會增加數(shù)的高度，若新增節(jié)點在parent的右子樹，則parent的平衡因子++，相反在parent的左子樹時，則平衡因子- -。

每更新完一個節(jié)點的平衡因子都需要進行以下判斷：

1.如果parent的平衡因子等于1/-1時，說明parent原先的平衡因子為0，插入節(jié)點后左子樹或右子樹的高度增加了，說明還需要向上更新平衡因子。

2.如果parent的平衡因子等于0，說明parent原先的平衡因子為1/-1，插入節(jié)點后左右兩棵子樹從不平衡變平衡了，說明無需更新平衡因子。

3.如果parent的平衡因子等于2/-2時，說明parent原先的平衡因子等于1/-1，插入節(jié)點后插入到了較高的那一棵子樹，說明此時以parent為根節(jié)點的子樹已經(jīng)不平衡了，需要進行旋轉處理。

bool Insert(const pair<K, V>& kv)
{
	//如果樹為空，則插入的節(jié)點就是根節(jié)點
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first < kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_kv.first > kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}
	cur = new Node(kv);
	if (parent->_kv.first < kv.first)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	cur->_parent = parent;
	//更新平衡因子
	while (parent)
	{
		if (cur == parent->_left)
		{
			parent->_bf--;
		}
		else
			parent->_bf++;
		if (parent->_bf == 0)
		{
			break;
		}
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			//繼續(xù)往上進行更新
			cur = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			//不平衡，旋轉處理
			if (parent->_bf == -2 && cur->_bf == -1)
			{
				RotateR(parent);
			}
			else if(parent->_bf == 2 && cur->_bf == 1)
			{
				RotateL(parent);
			}
			else if (parent->_bf == -2 && cur->_bf == 1)
			{
				RotateLR(parent);
			}
			else if (parent->_bf == 2 && cur->_bf == -1)
			{
				RotateRL(parent);
			}
			else
			{
				assert(false);
			}
		}
		else
		{
			assert(false);
		}
		break;
	}
	return true;
}

3. 樹的旋轉

旋轉的目的就是讓樹從失衡到平衡，降低樹的高度。旋轉主要分為四種，分別為左單旋、右單旋、左右雙旋和右左雙旋。下面我們具體講講每一種旋轉的內部邏輯。

• 左單旋

條件：新節(jié)點插入到子樹較高的右側。

我們用圖來感受一下其旋轉的過程：

1.先將15的左子樹的節(jié)點12變成10的右子樹。

2.再將10變成15的左子樹，15成為新樹的根節(jié)點。

3.更新平衡因子

由于左單旋的情況很多，我們也可以用一張抽象圖來表示：

代碼所示：

//左單旋
void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	parent->_right = subR;
	if (subRL)
		subRL->_parent = parent;
	Node* pparent = parent->_parent;
	if (pparent == nullptr)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		if (pparent == parent->_right)
		{
			parent->_right = subR;
		}
		else
		{
			parent->_left = subR;
		}
		subR->_parent = pparent;
	}
	parent->_bf = subR->_bf = 0;
}

• 右單旋

條件：新節(jié)點插入到子樹較高的左側

用圖來感受旋轉的過程：

我們會發(fā)現(xiàn)和左單旋和相似

1.先將5的右子樹的值b變成10的左子樹。

2.再將10變成5的右子樹，旋轉完后5成為整棵樹的根節(jié)點。

3.更新平衡因子。

代碼所示：

//右單旋
void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	parent->_left = subLR;
	if(subLR)
		subLR->_parent = parent;
	Node* pparent = parent->_parent;
	subL->_right = parent;
	parent->_parent = subL;
	if (pparent == nullptr)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (pparent == parent->_left)
		{
			parent->_left = subL;
		}
		else
		{
			parent->_right = subL;
		}
		subL->_parent = pparent;
	}
	parent->_bf = subL->_bf = 0;
}

• 左右雙旋

條件：新節(jié)點插入到較高左子樹的右側。

下面我們用圖來演示一下其旋轉過程：

1.插入新節(jié)點

2.以節(jié)點5為旋轉點進行左單旋

3.以節(jié)點為10進行右單旋

4.旋轉完后更新平衡因子。

平衡因子又分為三種情況：

1.當subLR的平衡因子為-1時，左右雙旋后parent、subL,subLR的平衡因子分別為1、0、0。

2.當subLR的平衡因子為1時，左右雙旋后parent、subL,subLR的平衡因子分別為0、-1、0。

3.當subLR的平衡因子為0時，左右雙旋后parent、subL,subLR的平衡因子分別為0、0、0。

代碼所示：

	//左右雙旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;
		RotateL(parent->_left);
		RotateR(parent);
		if (bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)
		{
			subLR->_bf = 0;
			subL->_bf = -1;
			parent->_bf = 0;
		}
		else if (bf == 0)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

• 右左雙旋

條件：插入到較高右子樹的左側

其旋轉過程和左右雙旋類似，這就不一一列舉了。

旋轉完過后也是需要更新平衡因子，平衡因子也是跟左右雙旋一樣有三種情況。

代碼所示：

//右左雙旋
void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;
	RotateR(parent);
	RotateL(parent);
	if (bf == 0)
	{
		subR->_bf = 0;
		subRL->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == 1)
	{
		subR->_bf = 0;
		subRL->_bf = 0;
		parent->_bf = -1;
	}
	else if (bf == -1)
	{
		subR->_bf = 1;
		subRL->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

四、AVL樹的其它功能

1. 樹的查找

定義一個cur指針從樹的根節(jié)點開始查找，按一下規(guī)則進行查找：

1.當key的值小于當前節(jié)點的值時，則在該節(jié)點的左邊進行查找。

2.當key的值大于當前節(jié)點的值時，則在該節(jié)點的右邊進行查找。

3.若key的值等于當前節(jié)點的值時，則說明查找成功，返回true。

4.若遍歷完還沒查找到該節(jié)點的值，則說明沒有此節(jié)點，返回false。

代碼所示：

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

2. 樹的遍歷

我們遍歷方式有前序、中序、后序、層序等方式，我們在這就采用中序遍歷的方式來遍歷樹的每一節(jié)點。

代碼所示：

void _Inorder(Node* root)
{
	if (root == nullptr)
	{
		return;
	}
	_Inorder(root->_left);
	cout << root->_kv.first << ":" << root->_kv.second << endl;
	_Inorder(root->_right);
}

3. 樹的高度

int _Height(Node* root)
{
	if (root == nullptr)
	{
		return;
	}
	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

4. 樹的大小

返回左子樹+右子樹再加上根節(jié)點即可。

int _Size(Node* root)
{
	if (root == nullptr)
	{
		return;
	}
	return _Size(root->_left) + _Size(root->_right) + 1;
}

五、總結

1. AVL樹的優(yōu)缺點

優(yōu)點：

**1.查找效率高：**由于AVL樹總是保持平衡，其高度相對較低，因此查找操作的時間復雜度為O(log2N)，效率較高。

2.結構穩(wěn)定： AVL樹的平衡性使得其結構相對穩(wěn)定，不會出現(xiàn)極端不平衡的情況，從而保證了操作的穩(wěn)定性和可靠性。

缺點：

1.插入和刪除復雜： AVL樹在插入和刪除節(jié)點時，可能需要通過旋轉操作來保持樹的平衡，比較復雜。

2.可能導致性能下降： 在頻繁插入和刪除的場景下，AVL樹需要不斷地進行旋轉操作來保持平衡，這就有可能導致性能降低。

2. 完整代碼

#include<iostream>
#include<assert.h>
using namespace std;

template<class K, class V>
struct AVLTreeNode
{
	// 需要parent指針，后續(xù)更新平衡因子可以看到
	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	//平衡因子
	int _bf; // balance factor
	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}
};

template<class K,class V>
class AVLTree
{
	typedef	AVLTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		//更新平衡因子
		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
				parent->_bf++;
			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				//繼續(xù)往上進行更新
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//不平衡，旋轉處理
				if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				else if(parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				else
				{
					assert(false);
				}
			}
			else
			{
				assert(false);
			}
			break;
		}
		return true;
	}
	
	//右單旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if(subLR)
			subLR->_parent = parent;
		Node* pparent = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;
		if (pparent == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (pparent == parent->_left)
			{
				parent->_left = subL;
			}
			else
			{
				parent->_right = subL;
			}
			subL->_parent = pparent;
		}
		parent->_bf = subL->_bf = 0;
	}

	//左單旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subR;
		if (subRL)
			subRL->_parent = parent;
		Node* pparent = parent->_parent;
		if (pparent == nullptr)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (pparent == parent->_right)
			{
				parent->_right = subR;
			}
			else
			{
				parent->_left = subR;
			}
			subR->_parent = pparent;
		}
		parent->_bf = subR->_bf = 0;
	}

	//左右雙旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;
		RotateL(parent->_left);
		RotateR(parent);
		if (bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)
		{
			subLR->_bf = 0;
			subL->_bf = -1;
			parent->_bf = 0;
		}
		else if (bf == 0)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	//右左雙旋
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;
		RotateR(parent);
		RotateL(parent);
		if (bf == 0)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 1)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)
		{
			subR->_bf = 1;
			subRL->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}

	void Hight()
	{
		return _Hight(_root);
	}

	void Size()
	{
		return _Size(_root);
	}

private:
	void _Inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Inorder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_Inorder(root->_right);
	}

	int _Height(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

	int _Size(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		return _Size(root->_left) + _Size(root->_right) + 1;
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}
private:
	Node* _root = nullptr;
};

總結 

到此這篇關于C++中AVL樹的底層以及實現(xiàn)方法總結的文章就介紹到這了,更多相關C++ AVL樹底層及實現(xiàn)內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

相關文章

  • C++實現(xiàn)猜牌小游戲

    C++實現(xiàn)猜牌小游戲

    這篇文章主要為大家詳細介紹了C++實現(xiàn)猜牌小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2020-07-07
  • C++ decltype類型說明符

    C++ decltype類型說明符

    在C++中，decltype作為操作符，用于查詢表達式的數(shù)據(jù)類型。decltype在C++11標準制定時引入，主要是為泛型編程而設計，以解決泛型編程中，由于有些類型由模板參數(shù)決定，而難以（甚至不可能）表示之的問題。
    2016-03-03
  • 詳解C語言編程之thread多線程

    詳解C語言編程之thread多線程

    這篇文章主要為大家介紹了C語言編程之thread多線程，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
    2021-12-12
  • C++應用Eigen庫對應實現(xiàn)matlab中部分函數(shù)問題

    C++應用Eigen庫對應實現(xiàn)matlab中部分函數(shù)問題

    這篇文章主要介紹了C++應用Eigen庫對應實現(xiàn)matlab中部分函數(shù)問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
    2022-12-12
  • C語言圖書借閱系統(tǒng)源碼

    C語言圖書借閱系統(tǒng)源碼

    這篇文章主要為大家分享了C語言圖書借閱系統(tǒng)源碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2018-02-02
  • C++實現(xiàn)LeetCode(211.添加和查找單詞-數(shù)據(jù)結構設計)

    C++實現(xiàn)LeetCode(211.添加和查找單詞-數(shù)據(jù)結構設計)

    這篇文章主要介紹了C++實現(xiàn)LeetCode(211.添加和查找單詞-數(shù)據(jù)結構設計),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下
    2021-08-08
  • C語言實現(xiàn)掃雷附完整代碼

    C語言實現(xiàn)掃雷附完整代碼

    本文詳細講解了C語言實現(xiàn)掃雷并附完整代碼，文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
    2021-11-11
  • C語言實現(xiàn)繪制余弦曲線

    C語言實現(xiàn)繪制余弦曲線

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)繪制余弦曲線的相關知識,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下
    2024-01-01
  • C++11中的引用限定符示例代碼

    C++11中的引用限定符示例代碼

    C++中有左值和右值的概念，其實，左值和右值的區(qū)分也同樣適用于類對象，本文中將左值的類對象稱為左值對象，將右值的類對象稱為右值對象，對C++11?引用限定符相關知識感興趣的朋友跟隨小編一起看看吧
    2023-01-01
  • 淺談C語言中的sizeof()和strlen()的區(qū)別

    淺談C語言中的sizeof()和strlen()的區(qū)別

    本文主要介紹了C語言中的sizeof()和strlen()的區(qū)別，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-05-05

最新評論