国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

<span id="fugjb"><tr id="fugjb"><tt id="fugjb"></tt></tr></span>

<rp id="fugjb"><u id="fugjb"><listing id="fugjb"></listing></u></rp>

數(shù)據(jù)結(jié)構(gòu)：AVL樹講解（C++）

2年前作者：派小星233分類：Toy博客閱讀(20)違法舉報

這篇具有很好參考價值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)：AVL樹講解（C++）。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

1.AVL樹的概念

普通二叉搜索樹：二叉搜索樹

二叉搜索樹雖可以縮短查找的效率，但如果數(shù)據(jù)有序或接近有序普通的二叉搜索樹將退化為單支樹，查找元素相當(dāng)于在順序表中搜索元素，效率低下。因此，兩位俄羅斯的數(shù)學(xué)家G.M.Adelson-Velskii和E.M.Landis在1962年發(fā)明了一種解決上述問題的方法(AVL樹是以這兩位的名字命名的)：當(dāng)向二叉搜索樹中插入新結(jié)點后，如果能保證每個結(jié)點的左右子樹高度之差的絕對值不超過1，超過了需要對樹中的結(jié)點進行調(diào)整(旋轉(zhuǎn))，即可降低樹的高度，從而減少平均搜索長度。

AVL樹也是二叉搜索樹，但有以下特點：

它的左右子樹都是AVL樹
左右子樹高度之差(簡稱平衡因子)的絕對值不超過1(-1/0/1)
如果一棵二叉搜索樹是高度平衡的，它就是AVL樹。如果它有n個結(jié)點，其高度可保持在 $O(log_2 n)$ ，搜索時間復(fù)雜度O( $log_2 n$ )。

2.平衡因子

AVL樹的實現(xiàn)有很多種，本文引入平衡因子來維持高度穩(wěn)定。
本文平衡因子的定義：右子樹高度 - 左子樹的高度。

依據(jù)每個節(jié)點的平衡因子，我們可以判斷樹的情況：

平衡因子在(-1, 0, 1)，當(dāng)前節(jié)點所在子樹是穩(wěn)定的。
平衡因子為2或-2，當(dāng)前節(jié)點所在子樹是不穩(wěn)定的。

插入節(jié)點后平衡因子的更新：

插入節(jié)點在右子樹，平衡因子加一。
插入節(jié)點在左子樹，平衡因子減一。

插入節(jié)點后平衡因子的不同情況（重點）：

當(dāng)前節(jié)點所在子樹平衡因子為0，子樹高度不變，不需要更新
（原來一邊高一邊低，新插入在低一方，變成完全平衡）。
當(dāng)前節(jié)點所在子樹平衡因子為1或-1，子樹高度變化，需要向上更新。
（原來完全平衡，現(xiàn)在一邊高，子樹整體高度加1，會影響到祖先的平衡，故需要向上更新看祖先所在子樹是否平衡）
當(dāng)前節(jié)點所在子樹平衡因子為2或-2，子樹高度變化且不平衡，無需向上更新，對當(dāng)前子樹進行旋轉(zhuǎn)操作。
（當(dāng)前子樹已不平衡，向上更新沒有意義，旋轉(zhuǎn)操作是AVL樹的核心，可以降低當(dāng)前子樹的高度且不影響上面的樹結(jié)構(gòu)）

數(shù)據(jù)結(jié)構(gòu)：AVL樹講解（C++）,高階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),c++,算法,筆記,學(xué)習(xí)

3.節(jié)點的定義

節(jié)點除了需要增加一個平衡因子，還需要增加一個父親指針，方便我們進行平衡因子的向上更新和旋轉(zhuǎn)操作。

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

4.插入操作

PS：因為多加了一個父親指針，所以插入時要注意更新父親指針，平衡因子更新按前面的分析來還是比較簡單的，旋轉(zhuǎn)操作后面單獨講。

bool Insert(const pair<K, V>& kv)
{
	if (_root == nullptr) //一開始為空樹，直接插入即可
	{
		_root = new Node(kv);
		return true;
	}

	//找插入位置加插入
	Node* cur = _root;  //記錄插入位置
	Node* parent = nullptr;  //待插入位置的父親
	while (cur)
	{
		if (kv.first > cur->_kv.first)  //待插入節(jié)點在右子樹
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (kv.first < cur->_kv.first)  //待插入節(jié)點在左子樹
		{
			parent = cur;
			cur = cur->_left;
		}
		else  //待插入節(jié)點已存在
		{
			return false;
		}
	}
	cur = new Node(kv);
	if (kv.first > parent->_kv.first)  //插入在父親的右邊
	{
		parent->_right = cur;
	}
	else  //插入在父親的左邊
	{
		parent->_left = cur;
	}
	cur->_parent = parent;  //注意更新父親指針

	//調(diào)整平衡因子
	while (parent)  //是有可能調(diào)整到根部的
	{
		if (cur == parent->_right)  //如果新插入的在右子樹
		{
			parent->_bf++;
		}
		else if (cur == parent->_left)  //如果新插入的在左子樹
		{
			parent->_bf--;
		}

		if (parent->_bf == 0) //插入后高度不變
		{
			break;
		}
		else if (parent->_bf == 1 || parent->_bf == -1)  //插入后高度變化，但當(dāng)前子樹依然平衡，需要向上更新
		{
			parent = parent->_parent;
			cur = cur->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)  //插入后高度變化，并且當(dāng)前子樹已經(jīng)不平衡,旋轉(zhuǎn)
		{
			//旋轉(zhuǎn)操作（先省略）
			break;
		}
		else //存在大于2小于-2的情況，樹原來就不平衡，應(yīng)該報錯
		{
			assert(false);
		}
	}
	return true;
}

5.旋轉(zhuǎn)操作（重點）

5.1左單旋

主體思想：

數(shù)據(jù)結(jié)構(gòu)：AVL樹講解（C++）,高階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),c++,算法,筆記,學(xué)習(xí)

平衡因子的調(diào)整：
數(shù)據(jù)結(jié)構(gòu)：AVL樹講解（C++）,高階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),c++,算法,筆記,學(xué)習(xí)

代碼加細節(jié)處理：

數(shù)據(jù)結(jié)構(gòu)：AVL樹講解（C++）,高階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),c++,算法,筆記,學(xué)習(xí)

void RotateL(Node* parent)  //左單旋,rotate->旋轉(zhuǎn)
{
	Node* SubR = parent->_right;
	Node* SubRL = SubR->_left;  //這個有可能為空
	Node* ppnode = parent->_parent;  //原來父親的父親

	parent->_right = SubRL;
	if(SubRL)  SubRL->_parent = parent;

	SubR->_left = parent;
	parent->_parent = SubR;

	if (ppnode == nullptr)  //旋轉(zhuǎn)的是整顆樹
	{
		_root = SubR;
		SubR->_parent = nullptr;
	}
	else  //旋轉(zhuǎn)的是部分
	{
		if (ppnode->_left == parent) //是左子樹
		{
			ppnode->_left = SubR;
		}
		else  //是右子樹
		{
			ppnode->_right = SubR;
		}
		SubR->_parent = ppnode;
	}
	//最后更新平衡因子
	parent->_bf = SubR->_bf = 0;
}

5.2右單旋

PS：右單旋和左單旋類似，細節(jié)處理也差不多，這里只講主體思路。
主體思路：
數(shù)據(jù)結(jié)構(gòu)：AVL樹講解（C++）,高階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),c++,算法,筆記,學(xué)習(xí)

平衡因子的調(diào)整：
數(shù)據(jù)結(jié)構(gòu)：AVL樹講解（C++）,高階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),c++,算法,筆記,學(xué)習(xí)

代碼：

void RotateR(Node* parent)  //右單旋細節(jié)處理和左單旋差不多
{
	Node* SubL = parent->_left;
	Node* SubLR = SubL->_right;  //這個有可能為空
	Node* ppnode = parent->_parent;

	parent->_left = SubLR;
	if(SubLR)  SubLR->_parent = parent;

	SubL->_right = parent;
	parent->_parent = SubL;

	if (ppnode == nullptr)  //旋轉(zhuǎn)的是整顆樹
	{
		_root = SubL;
		SubL->_parent = nullptr;
	}
	else  //旋轉(zhuǎn)部分
	{
		if (ppnode->_left == parent)  //是左子樹
		{
			ppnode->_left = SubL;
		}
		else  //右子樹
		{
			ppnode->_right = SubL;
		}
		SubL->_parent = ppnode;
	}
	//最后更新平衡因子
	parent->_bf = SubL->_bf = 0;
}

5.3左右雙旋

PS：雙旋其實就是兩次單旋(復(fù)用即可)，有前面的基礎(chǔ)很好理解，重點在于旋轉(zhuǎn)后平衡因子的更新。

旋轉(zhuǎn)思路：
數(shù)據(jù)結(jié)構(gòu)：AVL樹講解（C++）,高階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),c++,算法,筆記,學(xué)習(xí)

平衡因子的調(diào)整：
想知道平衡因子調(diào)整是那種情況，我們需要在旋轉(zhuǎn)前記錄SubRL的平衡因子bf：

bf為0是第一種情況。
bf為1是第二種情況。
bf為-1是第三種情況。

數(shù)據(jù)結(jié)構(gòu)：AVL樹講解（C++）,高階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),c++,算法,筆記,學(xué)習(xí)

代碼：

void RotateLR(Node* parent)  //左右雙旋
{
	Node* SubL = parent->_left;
	Node* SubLR = SubL->_right;
	int bf = SubLR->_bf;

	RotateL(SubL);
	RotateR(parent);

	if (bf == 1) //插入的是右邊
	{
		SubLR->_bf = 0;
		SubL->_bf = -1;
		parent->_bf = 0;
	}
	else if (bf == -1) //插入的是左邊
	{
		SubLR->_bf = 0;
		SubL->_bf = 0;
		parent->_bf = 1;
	}
	else if (bf == 0) //剛好原來parent的左邊就兩個節(jié)點
	{
		SubLR->_bf = SubL->_bf = parent->_bf = 0;
	}
	else  //原來就不是平衡樹，出現(xiàn)問題
	{

		assert(false);
	}
}

5.4右左雙旋

PS：右左雙旋和左右雙旋思路是差不多的，重點還是在旋轉(zhuǎn)后平衡因子的更新。

旋轉(zhuǎn)思路：
數(shù)據(jù)結(jié)構(gòu)：AVL樹講解（C++）,高階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),c++,算法,筆記,學(xué)習(xí)

平衡因子的調(diào)整：
和前面一樣，旋轉(zhuǎn)前確認SubRL的平衡因子bf即可。
數(shù)據(jù)結(jié)構(gòu)：AVL樹講解（C++）,高階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),c++,算法,筆記,學(xué)習(xí)

代碼：

void RotateRL(Node* parent)  //右左雙旋
{
	Node* SubR = parent->_right;
	Node* SubRL = SubR->_left;
	int bf = SubRL->_bf;

	RotateR(SubR);
	RotateL(parent);

	if (bf == 1)  //插入的是右邊
	{
		SubRL->_bf = 0;
		SubR->_bf = 0;
		parent->_bf = -1;
	}
	else if (bf == -1) //插入的是左邊
	{
		SubRL->_bf = 0;
		parent->_bf = 0;
		SubR->_bf = 1;
	}
	else if (bf == 0)  //原來parent的右邊就兩個節(jié)點
	{
		SubRL->_bf = SubR->_bf = parent->_bf = 0;
	}
	else //原來就有問題
	{
		assert(false);
	}
}

6.一些簡單的測試接口

int Height()
{
	return _Height(_root);
}

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;
}

bool IsBalance()
{
	return IsBalance(_root);
}

//看當(dāng)前樹是不是平衡樹
//（1）看每個子樹是否滿足左右子樹高度差不超過一
//（2）看平衡因子和所求的左右子樹高度差是否一致
bool IsBalance(Node* root)
{
	if (root == nullptr)
		return true;

	int leftHight = _Height(root->_left);
	int rightHight = _Height(root->_right);

	if (rightHight - leftHight != root->_bf)
	{
		cout << "平衡因子異常:" << root->_kv.first << "->" << root->_bf << endl;
		return false;
	}

	return abs(rightHight - leftHight) < 2
		&& IsBalance(root->_left)
		&& IsBalance(root->_right);
}

文章來源地址http://www.zghlxwxcb.cn/news/detail-756146.html

7.完整代碼

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

template<class K, class V>
struct ALVTreeNode
{
	ALVTreeNode<K, V>* _left;
	ALVTreeNode<K, V>* _right;
	ALVTreeNode<K, V>* _parent;
	pair<K, V> _kv;  //存儲鍵值對
	int _bf;
	ALVTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
		,_kv(kv)
	{}
};

template<class K, class V>
class AVLTree
{
public:
	typedef ALVTreeNode<K, V> Node;

	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr) //一開始為空樹，直接插入即可
		{
			_root = new Node(kv);
			return true;
		}
		Node* cur = _root;  //記錄插入位置
		Node* parent = nullptr;  //待插入位置的父親
		while (cur)
		{
			if (kv.first > cur->_kv.first)  //待插入節(jié)點在右子樹
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)  //待插入節(jié)點在左子樹
			{
				parent = cur;
				cur = cur->_left;
			}
			else  //待插入節(jié)點已存在
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (kv.first > parent->_kv.first)  //插入在父親的右邊
		{
			parent->_right = cur;
		}
		else  //插入在父親的左邊
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		//調(diào)整平衡因子
		while (parent)  //是有可能調(diào)整到根部的
		{
			if (cur == parent->_right)  //如果新插入的是右子樹
			{
				parent->_bf++;
			}
			else if (cur == parent->_left)  //如果新插入的是左子樹
			{
				parent->_bf--;
			}

			if (parent->_bf == 0) //插入后高度不變
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)  //插入后高度變化，但當(dāng)前子樹依然平衡，需要向上更新
			{
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)  //插入后高度變化，并且當(dāng)前子樹已經(jīng)不平衡,旋轉(zhuǎn)
			{
				//旋轉(zhuǎn)
				if (parent->_bf == 2 && cur->_bf == 1)  //左單旋
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1) //右單旋
				{
					RotateR(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)  //左子樹的右邊高，左右雙旋
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)  //右子樹的左邊高，右左雙旋
				{
					RotateRL(parent);
				}
				else  //原來就不是平衡樹
				{
					assert(false);
				}
				break;
			}
			else //樹原來就不平衡，應(yīng)該報錯
			{
				assert(false);
			}
		}
		return true;
	}

	/
	
	///
	int Height()
	{
		return _Height(_root);
	}

	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;
	}

	bool IsBalance()
	{
		return IsBalance(_root);
	}

	//看當(dāng)前樹是不是平衡樹
	//（1）看每個子樹是否滿足左右子樹高度差不超過一
	//（2）看平衡因子和所求的左右子樹高度差是否一致
	bool IsBalance(Node* root)
	{
		if (root == nullptr)
			return true;

		int leftHight = _Height(root->_left);
		int rightHight = _Height(root->_right);

		if (rightHight - leftHight != root->_bf)
		{
			cout << "平衡因子異常:" << root->_kv.first << "->" << root->_bf << endl;
			return false;
		}

		return abs(rightHight - leftHight) < 2
			&& IsBalance(root->_left)
			&& IsBalance(root->_right);
	}

private:
	void RotateL(Node* parent)  //左單旋,rotate->旋轉(zhuǎn)
	{
		Node* SubR = parent->_right;
		Node* SubRL = SubR->_left;  //這個有可能為空
		Node* ppnode = parent->_parent;  //原來父親的父親

		parent->_right = SubRL;
		if(SubRL)  SubRL->_parent = parent;

		SubR->_left = parent;
		parent->_parent = SubR;

		if (ppnode == nullptr)  //旋轉(zhuǎn)的是整顆樹
		{
			_root = SubR;
			SubR->_parent = nullptr;
		}
		else  //旋轉(zhuǎn)的是部分
		{
			if (ppnode->_left == parent) //是左子樹
			{
				ppnode->_left = SubR;
			}
			else  //是右子樹
			{
				ppnode->_right = SubR;
			}
			SubR->_parent = ppnode;
		}
		//最后更新平衡因子
		parent->_bf = SubR->_bf = 0;
	}

	void RotateR(Node* parent)  //右單旋細節(jié)處理和左單旋差不多
	{
		Node* SubL = parent->_left;
		Node* SubLR = SubL->_right;  //這個有可能為空
		Node* ppnode = parent->_parent;

		parent->_left = SubLR;
		if(SubLR)  SubLR->_parent = parent;

		SubL->_right = parent;
		parent->_parent = SubL;

		if (ppnode == nullptr)  //旋轉(zhuǎn)的是整顆樹
		{
			_root = SubL;
			SubL->_parent = nullptr;
		}
		else  //旋轉(zhuǎn)部分
		{
			if (ppnode->_left == parent)  //是左子樹
			{
				ppnode->_left = SubL;
			}
			else  //右子樹
			{
				ppnode->_right = SubL;
			}
			SubL->_parent = ppnode;
		}
		//最后更新平衡因子
		parent->_bf = SubL->_bf = 0;
	}

	void RotateLR(Node* parent)  //左右雙旋
	{
		Node* SubL = parent->_left;
		Node* SubLR = SubL->_right;
		int bf = SubLR->_bf;

		RotateL(SubL);
		RotateR(parent);

		if (bf == 1) //插入的是右邊
		{
			SubLR->_bf = 0;
			SubL->_bf = -1;
			parent->_bf = 0;
		}
		else if (bf == -1) //插入的是左邊
		{
			SubLR->_bf = 0;
			SubL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 0) //剛好原來parent的左邊就兩個節(jié)點
		{
			SubLR->_bf = SubL->_bf = parent->_bf = 0;
		}
		else  //原來就不是平衡樹，出現(xiàn)問題
		{

			assert(false);
		}
	}

	void RotateRL(Node* parent)  //右左雙旋
	{
		Node* SubR = parent->_right;
		Node* SubRL = SubR->_left;
		int bf = SubRL->_bf;

		RotateR(SubR);
		RotateL(parent);

		if (bf == 1)  //插入的是右邊
		{
			SubRL->_bf = 0;
			SubR->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1) //插入的是左邊
		{
			SubRL->_bf = 0;
			parent->_bf = 0;
			SubR->_bf = 1;
		}
		else if (bf == 0)  //原來parent的右邊就兩個節(jié)點
		{
			SubRL->_bf = SubR->_bf = parent->_bf = 0;
		}
		else //原來就有問題
		{
			assert(false);
		}
	}

	Node* _root = nullptr;
};

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：AVL樹講解（C++）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經(jīng)查實，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費用

數(shù)據(jù)結(jié)構(gòu)(C++) : AVL樹實現(xiàn)篇
目錄 1.AVL樹引入 ? (1)二叉搜索樹缺點 ? (2)AVL樹簡介 ? ? [1]問題的解決 ? ? [2]AVL樹的性質(zhì) 2.AVL樹的插入旋轉(zhuǎn)操作 ? (1)術(shù)語解釋 ? (2)左單旋 ? ? [1]插入到右側(cè)的左邊 ? ? [2]插入到右側(cè)的右邊 ? (3)右單旋 ? ? [1]插入到左側(cè)的左邊 ? ? [2]插入到左側(cè)的右邊 ? (4)左右雙旋 ? ?
2024年02月05日
瀏覽(20)
數(shù)據(jù)結(jié)構(gòu)與算法——18.avl樹
這篇文章我們來看一下avl樹目錄 1.概述 2.AVL樹的實現(xiàn) 我們前面講了二叉搜索樹，它是有一個key值，然后比父節(jié)點key值大的在左邊，小的在右邊。這樣設(shè)計是為了便于查找。但是有一種極端的情況，就是所有的結(jié)點都在一邊，那查找的時間復(fù)雜度和在鏈表的查找時間復(fù)雜度就
2024年02月07日
瀏覽(20)
[數(shù)據(jù)結(jié)構(gòu) C++] AVL樹的模擬實現(xiàn)
問題引入：在上一篇文章中，我們提到了二叉搜索樹在插入時，可能會形成單邊樹，會降低二叉搜索的性能。因此我們需要平衡二叉搜索樹，降低二叉搜索樹的高度，使得二叉搜索樹趨于一顆完全二叉樹的樣子，這樣就可以提高二叉搜索樹的性能。本篇文章就來介紹一種平衡
2024年02月03日
瀏覽(19)
【數(shù)據(jù)結(jié)構(gòu)與算法】平衡二叉樹（AVL樹）
給你一個數(shù)列{1,2,3,4,5,6}，要求創(chuàng)建二叉排序樹（BST），并分析問題所在。 BST 存在的問題分析：左子樹全部為空，從形式上看，更像一個單鏈表。插入速度沒有影響。查詢速度明顯降低（因為需要依次比較），不能發(fā)揮 BST 的優(yōu)勢，因為每次還需要比較左子樹，其查詢速度
2024年02月13日
瀏覽(26)
數(shù)據(jù)結(jié)構(gòu)07：查找[C++][平衡二叉排序樹AVL]
圖源：文心一言考研筆記整理1w+字，小白友好、代碼可跑，請小伙伴放心食用~~???? 第1版：查資料、寫B(tài)UG、畫導(dǎo)圖、畫配圖~???? 參考用書：王道考研《2024年數(shù)據(jù)結(jié)構(gòu)考研復(fù)習(xí)指導(dǎo)》參考用書配套視頻： 7.3_2 平衡二叉樹_嗶哩嗶哩_bilibili 特別感謝： ?Chat GPT老師、文心
2024年02月11日
瀏覽(46)
Python - 深夜數(shù)據(jù)結(jié)構(gòu)與算法之 AVL 樹 & 紅黑樹
目錄一.引言二.高級樹的簡介 1.樹 2.二叉樹 3.二叉搜索樹 4.平衡二叉樹三.AVL 樹 ◆ 插入節(jié)點 ◆ 左旋 ◆ 右旋 ◆ 左右旋 ◆ 右左旋 ◆ 一般形式 ◆ 實際操作 ◆ 總結(jié) 四.紅黑樹 ◆ 概念 ◆ 示例 ◆ 對比五.總結(jié) 前面我們介紹了二叉樹、二叉搜索樹、多叉樹等基礎(chǔ)的樹形結(jié)構(gòu)，
2024年01月19日
瀏覽(24)
手撕哈希表（HashTable）——C++高階數(shù)據(jù)結(jié)構(gòu)詳解
小編是雙非本科大一菜鳥不贅述，歡迎米娜桑來指點江山哦（QQ：1319365055） ????非科班轉(zhuǎn)碼社區(qū)誠邀您入駐???? 小伙伴們，打碼路上一路向北，彼岸之前皆是疾苦一個人的單打獨斗不如一群人的砥礪前行這是我和夢想合伙人組建的社區(qū)，誠邀各位有志之士的加入??！社
2023年04月08日
瀏覽(26)
C++數(shù)據(jù)結(jié)構(gòu)之平衡二叉搜索樹（一）——AVL的實現(xiàn)（zig與zag/左右雙旋/3+4重構(gòu)）
本文是介紹眾多平衡二叉搜索樹（BBST）的第一篇——介紹AVL樹。故先來引入BBST的概念。由于上一篇介紹的二叉搜索樹（BST）在極度退化的情況下，十分不平衡，不平衡到只朝一側(cè)偏，成為一條鏈表，復(fù)雜度可達 O ( n ) O(n) O ( n ) ，所以我們要在“平衡”方面做一些約束，以防
2024年02月13日
瀏覽(27)
數(shù)據(jù)結(jié)構(gòu)：紅黑樹講解（C++）
本文旨在理解紅黑樹基本概念以及變色旋轉(zhuǎn)規(guī)則，以理解C++ map 和 set 的底層原理，不會講紅黑樹的刪除操作。對于基本的旋轉(zhuǎn)操作(單旋和雙旋)，本文不會展開講，詳細講解在這里： AVL樹旋轉(zhuǎn)講解。 2.1概念紅黑樹，是一種二叉搜索樹，但在每個結(jié)點上增加一個存儲位表示
2024年02月05日
瀏覽(20)
【數(shù)據(jù)結(jié)構(gòu)與算法】棧的講解
棧(stack)是限定僅在表尾進行插入和刪除操作的線性表。我們把允許插入和刪除的一段稱為棧頂(top) , 另一端稱為棧底，不含任何數(shù)據(jù)元素的棧稱為空棧。棧又稱為后進先出的線性表。進一步理解棧，棧首先他是一個線性表，所以棧元素具有前驅(qū)后繼關(guān)系。棧的插入操
2023年04月08日
瀏覽(19)

<span id="qldh8"></span>

<center id="qldh8"></center>

<video id="qldh8"><ul id="qldh8"></ul></video><span id="qldh8"><meter id="qldh8"><font id="qldh8"></font></meter></span>

<span id="qldh8"></span>