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

<noframes id="sinfk"><option id="sinfk"></option>

<xmp id="sinfk"><rp id="sinfk"></rp>

數(shù)據(jù)結(jié)構(gòu)——二叉搜索樹(附帶C++實(shí)現(xiàn)版本）

2年前作者：暮雨清秋.L分類：Toy博客閱讀(23)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)——二叉搜索樹(附帶C++實(shí)現(xiàn)版本）。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

二叉搜索樹

概念

二叉搜索樹又叫二叉排序樹，二叉搜索樹也是一種樹形結(jié)構(gòu)。
它是一課滿足以下性質(zhì)的搜索樹：

若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值
若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值
它的左右子樹也分別是二叉搜索樹

注意，二叉搜索樹對(duì)于值相同的節(jié)點(diǎn)只能存儲(chǔ)一個(gè)

數(shù)據(jù)結(jié)構(gòu)——二叉搜索樹(附帶C++實(shí)現(xiàn)版本）,C++,數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),c++,開發(fā)語言

優(yōu)點(diǎn)：這樣的結(jié)構(gòu)能夠平均用logn的時(shí)間復(fù)雜度找到我們想要的值，但是其最壞時(shí)間復(fù)雜度是O(n), 這是由于搜索二叉樹不一定是平衡的，如下圖所示：
數(shù)據(jù)結(jié)構(gòu)——二叉搜索樹(附帶C++實(shí)現(xiàn)版本）,C++,數(shù)據(jù)結(jié)構(gòu),算法,數(shù)據(jù)結(jié)構(gòu),c++,開發(fā)語言
這個(gè)結(jié)構(gòu)也滿足二叉搜索樹的性質(zhì)，但是其查找所需要的復(fù)雜度是O(n)

二叉樹的實(shí)際應(yīng)用

K模型：K模型只以key為關(guān)鍵碼，結(jié)構(gòu)中只需要存儲(chǔ)K即可，關(guān)鍵碼即為需要搜索道的值。

例如：給一個(gè)單詞word，判斷該單詞是否拼寫正確，具體方法如下：

以詞庫中的所有單詞集合中的每一個(gè)單詞作為key，構(gòu)建一顆二叉搜索樹。

在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯(cuò)誤

KV模型： 每一個(gè)關(guān)鍵碼key，都有與之對(duì)應(yīng)的值Value，即<Key, Value>的鍵值對(duì)。該種方式在現(xiàn)實(shí)生活中非常常見：

比如英漢詞典就是英文與中文的對(duì)應(yīng)關(guān)系，通過英文可以快速找到與其對(duì)應(yīng)的中文，英文單詞與其對(duì)應(yīng)的中文<word, chinese>就構(gòu)成一種鍵值對(duì)

再比如統(tǒng)計(jì)單詞次數(shù)，統(tǒng)計(jì)成功后，給定單詞就可快速找到其出現(xiàn)的次數(shù)，單詞與其出現(xiàn)次數(shù)就是<word, count>就構(gòu)成一種鍵值對(duì)

二叉樹模擬實(shí)現(xiàn)

在這里為大家以kv模型為例模擬實(shí)現(xiàn)二叉搜索樹，只要稍作修改即可變成k模型。

存儲(chǔ)結(jié)構(gòu)

首先，二叉搜索樹中存儲(chǔ)的是節(jié)點(diǎn)，所以我們需要定義一個(gè)表示節(jié)點(diǎn)的結(jié)構(gòu)體，如下：

	template<typename K, typename V>
	struct BSTree_node
	{
		K _key = K();
		V _value = V();
		BSTree_node* _left = nullptr;
		BSTree_node* _right = nullptr;
		BSTree_node() {}
		BSTree_node(const K& key, const V& value)
			:_key(key)
			, _value(value)
		{}
	};

K模型和K，V模型差別就在k,v模型里面還存儲(chǔ)了鍵所對(duì)應(yīng)的值的內(nèi)容，而k模型沒有

二叉搜索樹構(gòu)成

對(duì)于二叉搜索樹來說，我們想要找到其中的全部成員，和二叉樹一樣，我們只需要存儲(chǔ)它的根節(jié)點(diǎn)即可。

template<typename K, typename V>
class BSTree
{
	//typedef減少代碼長度
	typedef BSTree_node<K, V> node;
private:
	node* _root = nullptr;

二叉搜索樹的查找

由于二叉搜索樹的性質(zhì)，想要從中查找就很簡(jiǎn)單了。
a. 從根開始比較查找，比根大往右走，比根小往左走。
b. 最多查找高度次，如果走到空還沒找到，則這個(gè)值不存在

//循環(huán)操作
node* find(const K& key)
{
	//find不需要查找值，只需要查找鍵
	node* cur = _root;
	while (cur)
	{
		if (cur->_key > key) cur = cur->_left;
		else if (cur->_key < key) cur = cur->_right;
		else return cur;
	}
	return nullptr;
}
//遞歸的方式
//由于遞歸需要傳遞this指針來找到根節(jié)點(diǎn)，而方法不能在外面使用this指針，因此我們需要寫一個(gè)子函數(shù)來完成任務(wù)
private:
			node* _findR(node* root, const K& key)
		{
			if (!root) return nullptr;
			if (root->_key < key) return _findR(root->_right, key);
			else if (root->_key > key) return _findR(root->_left, key);
			else return root;
		}
public:
	node* findR(const K& key)
	{
		return _findR(_root,key);
	}

插入操作

插入操作同樣兩個(gè)要點(diǎn)：
a. 如果樹為空，則直接新增節(jié)點(diǎn)，賦值給root指針
b. 樹不空，按二叉搜索樹的位置不斷進(jìn)行比較找到插入位置，如果找到相同值的節(jié)點(diǎn)則插入失敗，否則插入新節(jié)點(diǎn)
同樣提供遞歸和循環(huán)兩種方法：

//循環(huán)
//對(duì)于循環(huán)，由于當(dāng)找到空節(jié)點(diǎn)的時(shí)候并不知道其在其雙親的左側(cè)還是右側(cè)，所以每次變換時(shí)需要記錄其是在左側(cè)還是右側(cè)
		//成功插入返回true，插入失敗返回false
		bool insert(const K& key, const V& value)
		{
			node* tmp = new node(key, value);
			if (!_root)
			{
				_root = tmp;
				return true;
			}
			//需要存儲(chǔ)parent,還要存儲(chǔ)所在的方向
			node* parent = nullptr;
			node* cur = _root;
			bool is_right = false;
			while (cur)
			{
				if (cur->_key < key) 
				{
					is_right = true;
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key) 
				{
					is_right = false;
					parent = cur;
					cur = cur->_left;
				}
				else return false;
			}
			//出循環(huán)時(shí)，cur已經(jīng)指向空指針
			//如果直接對(duì)cur賦值，是在對(duì)該拷貝賦值，并沒有修改其雙親的指向
			if (is_right) parent->_right = tmp;
			else parent->_left = tmp;
			return true;
		}
		
		//遞歸
		//同樣，我們需要一個(gè)子函數(shù)來傳遞this指針
		private:
			//這里使用引用是為了解決循環(huán)中無法知道新節(jié)點(diǎn)在其雙親的左邊還是右邊的問題
			bool _insertR(node*& root, const K& key, const V& value)
{
	//引用解決了找不到父親的問題
	if (!root)
	{
	//由于使用的是引用，這里其實(shí)是在修改雙親的指向
		root = new node(key, value);
		return true;
	}
	if (root->_key < key) return _insertR(root->_right, key, value);
	else if (root->_key > key) return _insertR(root->_left, key, value);
	else return false;
}

中序遍歷

由于二叉樹的特殊性質(zhì)，其中序遍歷一定是有序的，因此我們可以寫一個(gè)inorder函數(shù)輸出存儲(chǔ)結(jié)果用于檢驗(yàn)我們操作是否正確實(shí)現(xiàn)

private:
			void _inorder(node* root)
		{
			if (!root) return;
			_inorder(root->_left);
			std::cout << root->_key << ":" << root->_value << std::endl;
			_inorder(root->_right);	
		}
public:
			void inorder()
		{
			_inorder(_root);
			std::cout << std::endl;
		}

二叉樹的刪除

首先查找元素是否在二叉樹中，如果不存在，則返回
如果存在，則刪除節(jié)點(diǎn)還需要分以下幾種情況：

要?jiǎng)h除的節(jié)點(diǎn)無左孩子
要?jiǎng)h除的節(jié)點(diǎn)只有左孩子節(jié)點(diǎn)
要?jiǎng)h除的節(jié)點(diǎn)只有右孩子節(jié)點(diǎn)
要?jiǎng)h除的節(jié)點(diǎn)有左，右孩子節(jié)點(diǎn)

在實(shí)際刪除過程中，可以將情況1和情況2或情況3合并起來，刪除過程如下：

情況1: 刪除該節(jié)點(diǎn)且使被刪除節(jié)點(diǎn)的雙親節(jié)點(diǎn)指向被刪除節(jié)點(diǎn)的左孩子——直接刪除
情況2：刪除該節(jié)點(diǎn)且使被刪除節(jié)點(diǎn)的雙親指向被刪除節(jié)點(diǎn)的右孩子
情況3: 尋找和節(jié)點(diǎn)的值最相近的節(jié)點(diǎn)(左子樹最右節(jié)點(diǎn)或者該節(jié)點(diǎn)右子樹的根節(jié)點(diǎn))，用它的值填補(bǔ)道被刪除節(jié)點(diǎn)，然后再來處理該節(jié)點(diǎn)的刪除問題。

節(jié)點(diǎn)的刪除操作實(shí)現(xiàn)是二叉搜索樹中最困難的一個(gè)，由于其的細(xì)節(jié)很多，這里同樣還是給出遞歸和循環(huán)各一種方法。

循環(huán)(利用左子樹最右節(jié)點(diǎn)）

對(duì)于循環(huán)，博主選擇了和左子樹的最右節(jié)點(diǎn)進(jìn)行交換的方法，這是由于只要找到了左子樹的最右節(jié)點(diǎn)，和此時(shí)的根節(jié)點(diǎn)交換，然后就只需要進(jìn)行左右都沒孩子的刪除操作即可。
但是，和插入有著同樣的問題，我們?cè)诓檎掖齽h除節(jié)點(diǎn)的時(shí)候并不知道它在左側(cè)還是右側(cè)，所以我們?nèi)匀灰?strong>保存其雙親節(jié)點(diǎn)的位置，但是，還有例外。
先看情況一和情況二：

對(duì)于這種情況來說，如果要?jiǎng)h除的是根節(jié)點(diǎn)，那么其雙親節(jié)點(diǎn)的指針就是nullptr,如果不加以判斷，就會(huì)出錯(cuò)，當(dāng)待刪除節(jié)點(diǎn)為根節(jié)點(diǎn)時(shí)，我們直接將樹的_root節(jié)點(diǎn)改成_root->left/_root->right即可
情況三：
對(duì)于情況三來說，雖然我們需要找的是左子樹的最右節(jié)點(diǎn)，但是一定不要認(rèn)為左子樹最右節(jié)點(diǎn)一定在其雙親的右邊，有一種情況是例外的。如下：

如果此時(shí)要?jiǎng)h除的是根節(jié)點(diǎn)，那么其左子樹的最右節(jié)點(diǎn)就在其雙親的左邊，所以我們?nèi)匀恍枰粋€(gè)標(biāo)記來判斷該節(jié)點(diǎn)是在雙親的左邊還是右邊。

對(duì)于二叉樹的刪除操作來說，循環(huán)需要考慮的細(xì)節(jié)較多，遞歸雖然也有細(xì)節(jié)，但是相對(duì)更簡(jiǎn)單一些，但是循環(huán)的好處就是不會(huì)爆棧，因此在數(shù)據(jù)量非常大的時(shí)候還是使用循環(huán)更合適。
循環(huán)模擬代碼如下：

bool erase(const K& key)
{
	//可以分為兩種大情況
	//無子節(jié)點(diǎn)，有一個(gè)子節(jié)點(diǎn) -> 采用托孤處理
	//托孤要注意刪根節(jié)點(diǎn)的情況
	//兩個(gè)子節(jié)點(diǎn)都有 -> 將其與左樹最大節(jié)點(diǎn)或者右數(shù)最小節(jié)點(diǎn)相交換，然后刪除
	//第一步先找到要?jiǎng)h除的值的位置
	node* parent = nullptr;
	node* cur = _root;
	//保存節(jié)點(diǎn)位于其雙親的位置
	bool is_right = false;
	while (cur)
	{
		if (cur->_key < key)
		{
			is_right = true;
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			is_right = false;
			parent = cur;
			cur = cur->_left;
		}
		else break;
	}
	if (!cur) return false;
	node* del = cur;
	//這里需要找到父節(jié)點(diǎn)的本質(zhì)原因是引用不能改變指向
	if (!cur->_left)
	{
		//特殊情況，刪除的是根節(jié)點(diǎn)
		if (!parent) _root = _root->_right;
		else
		{
			if (is_right) parent->_right = cur->_right;
			else parent->_left = cur->_right;
		}
	}
	else if (!cur->_right)
	{
		//同理
		if (!parent) _root = _root->_left;
		else
		{
			if (is_right) parent->_right = cur->_left;
			else parent->_left = cur->_left;
		}
	}
	else
	{
		//左右兩邊都不為空
		//這里循環(huán)找左邊最大更方便
		node* leftMax = cur->_left;
		//bool is_up = true;
		//出現(xiàn) 特殊情況的本質(zhì)是下面這個(gè)循環(huán)沒有生效
		while (leftMax->_right)
		{
			parent = leftMax;
			leftMax = leftMax->_right;
			//is_up = false;
		}
		std::swap(leftMax->_key, cur->_key);
		//如果左子樹最大節(jié)點(diǎn)就是初始的leftMax，則將待刪除節(jié)點(diǎn)的左指向leftMax的左
		//if(is_up)
		if (leftMax == cur->_left) cur->_left = leftMax->_left;
		else parent->_right = leftMax->_left;
		//轉(zhuǎn)換待釋放的節(jié)點(diǎn)
		del = leftMax;
	}
	delete del;
	return true;
}

遞歸(利用右子樹根節(jié)點(diǎn))

對(duì)于遞歸來說，如果我們選擇右子樹的根節(jié)點(diǎn)進(jìn)行操作，整個(gè)刪除過程就可以變成子問題解決。

首先，由于遞歸可以使用引用作為參數(shù)，我們不需要糾結(jié)雙親以及其位于雙親左還是右的問題,因此對(duì)于循環(huán)中情況1,2刪除根節(jié)點(diǎn)的問題就不需要考慮了
另外，對(duì)于情況3來說，選擇右子樹的根節(jié)點(diǎn)也使得情況簡(jiǎn)單了許多，因?yàn)閷⒂易訕涔?jié)點(diǎn)與待刪除節(jié)點(diǎn)的值交換后，就變成了刪除其右子樹的根的子問題，完美符合遞歸的邏輯，直到根只有一個(gè)孩子的時(shí)侯就變成情況1了，不需要考慮其他特殊情況。
代碼如下：

private:
	bool _erase(node*& root, const K& key)
{
	if (!root) return false;
	if (root->_key < key) return _erase(root->_right, key);
	else if (root->_key > key) return _erase(root->_left, key);
	else
	{
		//用引用就不需要考慮父親指向的問題了
		if (!root->_left) 
		{
			root = root->_right;
			return true;
		}
		else if (!root->_right)
		{
			root = root->_left;
			return true;
		}
		else
		{
			swap(root->_key, root->_right->_key);
			return _erase(root->_right, key);
		}
	}
}
public:
	bool eraseR(const K& key)
	{
		_erase(_root, key);
	}

二叉樹拷貝

二叉樹的拷貝構(gòu)造也可以利用遞歸的性質(zhì)來實(shí)現(xiàn)，先拷貝根節(jié)點(diǎn)，然后拷貝左子樹，最后拷貝右子樹，拷貝左子樹和右子樹的邏輯與主邏輯相同。
代碼：

private:
		node* _copy(node*& root, node* copy)
		{
			if (!copy) return nullptr;
			root = new node(copy->_key, copy->_value);
			root->_left = _copy(root->_left, copy->_left);
			root->_right = _copy(root->_right, copy->_right);
			return root;
		}
public:
		BSTree(const BSTree& t)
		{
			_copy(_root, t._root);
		}

二叉樹資源的銷毀

由于二叉樹的節(jié)點(diǎn)都是new出來的節(jié)點(diǎn)，所以我們?cè)诮Y(jié)束使用時(shí)也需要釋放資源，否則就會(huì)導(dǎo)致內(nèi)存泄漏的問題，對(duì)于釋放資源，我們可以放在析構(gòu)函數(shù)解決，運(yùn)用遞歸后序遍歷的思路，先釋放左子樹的資源，然后釋放右子樹的資源，最后釋放根節(jié)點(diǎn)的資源，代碼如下：

private:
		void _destroy(node* root)
		{
			if (!root) return;
			_destroy(root->_left);
			_destroy(root->_right);
			delete root;
		}

public:
		~BSTree()
		{
			_destroy(_root);
		}

二叉樹實(shí)現(xiàn)完整代碼

#pragma once
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

namespace key_value
{
	template<typename K, typename V>
	struct BSTree_node
	{
		K _key = K();
		V _value = V();
		BSTree_node* _left = nullptr;
		BSTree_node* _right = nullptr;
		BSTree_node() {}
		BSTree_node(const K& key, const V& value)
			:_key(key)
			, _value(value)
		{}
	};
	template<typename K, typename V>
	class BSTree
	{
		typedef BSTree_node<K, V> node;
	private:
		node* _root = nullptr;
		void _inorder(node* root)
		{
			if (!root) return;
			_inorder(root->_left);
			std::cout << root->_key << ":" << root->_value << std::endl;
			_inorder(root->_right);	
		}
		bool _insertR(node*& root, const K& key, const V& value)
		{
			//引用解決了找不到父親的問題
			if (!root)
			{
				root = new node(key, value);
				return true;
			}
			if (root->_key < key) return _insertR(root->_right, key, value);
			else if (root->_key > key) return _insertR(root->_left, key, value);
			else return false;
		}
		node* _findR(node* root, const K& key)
		{
			if (!root) return nullptr;
			if (root->_key < key) return _findR(root->_right, key);
			else if (root->_key > key) return _findR(root->_left, key);
			else return root;
		}
		//同理，這里要修改的不是局部變量，而是上一個(gè)指針的指向，所以要使用引用
		bool _erase(node*& root, const K& key)
		{
			if (!root) return false;
			if (root->_key < key) return _erase(root->_right, key);
			else if (root->_key > key) return _erase(root->_left, key);
			else
			{
				//用引用就不需要考慮父親指向的問題了
				if (!root->_left) 
				{
					root = root->_right;
					return true;
				}
				else if (!root->_right)
				{
					root = root->_left;
					return true;
				}
				else
				{
					swap(root->_key, root->_right->_key);
					return _erase(root->_right, key);
				}
			}
		}
		void _destroy(node* root)
		{
			if (!root) return;
			_destroy(root->_left);
			_destroy(root->_right);
			delete root;
		}
		node* _copy(node*& root, node* copy)
		{
			if (!copy) return nullptr;
			root = new node(copy->_key, copy->_value);
			root->_left = _copy(root->_left, copy->_left);
			root->_right = _copy(root->_right, copy->_right);
			return root;
		}
	public:
		BSTree() {}
		//循環(huán)
		/
		//插入，如果已經(jīng)存在就不用插入
		bool insert(const K& key, const V& value)
		{
			node* tmp = new node(key, value);
			if (!_root)
			{
				_root = tmp;
				return true;
			}
			//需要存儲(chǔ)parent,還要存儲(chǔ)所在的方向
			node* parent = nullptr;
			node* cur = _root;
			bool is_right = false;
			while (cur)
			{
				if (cur->_key < key) 
				{
					is_right = true;
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key) 
				{
					is_right = false;
					parent = cur;
					cur = cur->_left;
				}
				else return false;
			}
			//出循環(huán)時(shí)，cur已經(jīng)指向空指針
			if (is_right) parent->_right = tmp;
			else parent->_left = tmp;
			return true;
		}
		node* find(const K& key)
		{
			//find不需要查找值，只需要查找鍵
			node* cur = _root;
			while (cur)
			{
				if (cur->_key > key) cur = cur->_left;
				else if (cur->_key < key) cur = cur->_right;
				else return cur;
			}
			return nullptr;
		}
		bool erase(const K& key)
		{
			//可以分為兩種大情況
			//無子節(jié)點(diǎn)，有一個(gè)子節(jié)點(diǎn) -> 采用托孤處理
			//托孤要注意刪根節(jié)點(diǎn)的情況
			//兩個(gè)子節(jié)點(diǎn)都有 -> 將其與左樹最大節(jié)點(diǎn)或者右數(shù)最小節(jié)點(diǎn)相交換，然后刪除
			//第一步先找到要?jiǎng)h除的值的位置
			node* parent = nullptr;
			node* cur = _root;
			//保存節(jié)點(diǎn)位于其雙親的位置
			bool is_right = false;
			while (cur)
			{
				if (cur->_key < key)
				{
					is_right = true;
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					is_right = false;
					parent = cur;
					cur = cur->_left;
				}
				else break;
			}
			if (!cur) return false;
			node* del = cur;
			//這里需要找到父節(jié)點(diǎn)的本質(zhì)原因是引用不能改變指向
			if (!cur->_left)
			{
				//特殊情況，刪除的是根節(jié)點(diǎn)
				if (!parent) _root = _root->_right;
				else
				{
					if (is_right) parent->_right = cur->_right;
					else parent->_left = cur->_right;
				}
			}
			else if (!cur->_right)
			{
				//同理
				if (!parent) _root = _root->_left;
				else
				{
					if (is_right) parent->_right = cur->_left;
					else parent->_left = cur->_left;
				}
			}
			else
			{
				//左右兩邊都不為空
				//這里循環(huán)找左邊最大更方便
				node* leftMax = cur->_left;
				//bool is_up = true;
				//出現(xiàn) 特殊情況的本質(zhì)是下面這個(gè)循環(huán)沒有生效
				while (leftMax->_right)
				{
					parent = leftMax;
					leftMax = leftMax->_right;
					//is_up = false;
				}
				std::swap(leftMax->_key, cur->_key);
				//如果左子樹最大節(jié)點(diǎn)就是初始的leftMax，則將待刪除節(jié)點(diǎn)的左指向leftMax的左
				//if(is_up)
				if (leftMax == cur->_left) cur->_left = leftMax->_left;
				else parent->_right = leftMax->_left;
				//轉(zhuǎn)換待釋放的節(jié)點(diǎn)
				del = leftMax;
			}
			delete del;
			return true;
		}
		//遞歸
		/
		//中序遍歷
		void inorder()
		{
			_inorder(_root);
			std::cout << std::endl;
		}
		bool insertR(const K& key, const V& value)
		{
			return _insertR(_root, key, value);
		}
		node* findR(const K& key) { return _findR(_root, key); }
		bool eraseR(const K& key)
		{
			_erase(_root, key);
		}
		~BSTree()
		{
			_destroy(_root);
		}
		BSTree(const BSTree& t)
		{
			_copy(_root,t._root);
		}
	};

	//測(cè)試用例1
	void test_BSTree()
	{
		int a[] = { 8,3,1,10,6,4,7,14,13 };
		BSTree<int, int> bst;
		for (auto e : a) bst.insert(e,e);
		std::cout << bst.find(8)->_key << std::endl;
		std::cout << bst.find(13)->_key << std::endl;
		//std::cout << bst.find(18)->_key << std::endl;
		BSTree<int, int> t1(bst);
		t1.inorder();
		bst.erase(4);
		bst.inorder();

		bst.erase(6);
		bst.inorder();

		bst.erase(7);
		bst.inorder();

		bst.erase(3);
		bst.inorder();

		for (auto e : a)
		{
			bst.erase(e);
		}
		bst.inorder();
	}
	//測(cè)試用例2
	void TestBSTree()
	{
		BSTree<string, string> dict;
		dict.insertR("insert", "插入");
		dict.insertR("erase", "刪除");
		dict.insertR("left", "左邊");
		dict.insertR("string", "字符串");

		string str;
		while (cin >> str)
		{
			auto ret = dict.findR(str);
			if (ret)
			{
				cout << str << ":" << ret->_value << endl;
			}
			else
			{
				cout << "單詞拼寫錯(cuò)誤" << endl;
			}
		}

		string strs[] = { "蘋果", "西瓜", "蘋果", "櫻桃", "蘋果", "櫻桃", "蘋果", "櫻桃", "蘋果" };
		// 統(tǒng)計(jì)水果出現(xiàn)的次
		BSTree<string, int> countTree;
		for (auto str : strs)
		{
			auto ret = countTree.findR(str);
			if (ret == nullptr)
			{
				countTree.insertR(str, 1);
			}
			else
			{
				ret->_value++;
			}
		}
		BSTree<string, int> t1(countTree);
		countTree.inorder();
		t1.inorder();
	}
}

總結(jié)

前面提到了對(duì)于二叉查找樹來說，

最好情況下二叉樹為完全二叉樹(或接近完全二叉樹)，其平均比較次數(shù)為: $log_2 N$
但最壞情況下，二叉搜索樹有可能退化成單支樹（或類似單支），其平均比較次數(shù)為： $\frac{N}{2}$

那么就有一個(gè)問題了，如果退化成單支樹，二叉搜索樹的性能就消失了，那么是否能夠改進(jìn)，不論按什么次數(shù)插入關(guān)鍵碼，二叉搜索樹的性能都能達(dá)到最優(yōu)呢?
那么就需要用到AVL樹和紅黑樹了，這兩種樹都是特殊的搜索二叉樹，但是底層相對(duì)于普通的二叉搜索樹又復(fù)雜了許多，加入了翻轉(zhuǎn)二叉樹等操作來達(dá)到最有優(yōu)效率！
STL中的map和set底層就是用紅黑樹實(shí)現(xiàn)的，其做到了查找最壞時(shí)間復(fù)雜度為 $O(log_2 N)$ ,這樣大家就感受到紅黑樹的強(qiáng)大了把！

對(duì)于AVL樹和紅黑樹的知識(shí)，博主會(huì)在之后的博客中講解，大家敬請(qǐng)期待！

以上就是二叉樹實(shí)現(xiàn)的增刪查改的相關(guān)知識(shí)內(nèi)容，完整代碼以及其作用和性能分析的總結(jié)了，希望大家看完能夠有所收獲！如果對(duì)博主的內(nèi)容有疑惑或者博主內(nèi)容有誤的話，歡迎評(píng)論區(qū)指出！文章來源地址http://www.zghlxwxcb.cn/news/detail-657950.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——二叉搜索樹(附帶C++實(shí)現(xiàn)版本）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

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

分享到：

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

[數(shù)據(jù)結(jié)構(gòu)進(jìn)階 C++] 二叉搜索樹(BinarySearchTree)的模擬實(shí)現(xiàn)
二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹: 若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值它的左右子樹也分別為二叉搜索樹我們先給出兩個(gè)示例：此
2024年02月04日
瀏覽(27)
C++數(shù)據(jù)結(jié)構(gòu)之平衡二叉搜索樹（一）——AVL的實(shí)現(xiàn)（zig與zag/左右雙旋/3+4重構(gòu)）
本文是介紹眾多平衡二叉搜索樹（BBST）的第一篇——介紹AVL樹。故先來引入BBST的概念。由于上一篇介紹的二叉搜索樹（BST）在極度退化的情況下，十分不平衡，不平衡到只朝一側(cè)偏，成為一條鏈表，復(fù)雜度可達(dá) O ( n ) O(n) O ( n ) ，所以我們要在“平衡”方面做一些約束，以防
2024年02月13日
瀏覽(27)
【C++＆數(shù)據(jù)結(jié)構(gòu)】超詳細(xì)一文帶小白輕松全面理解 [ 二叉搜索樹 ]—— [從零實(shí)現(xiàn)＆逐過程分析＆代碼演示&簡(jiǎn)練易懂]（23）
前言大家好吖，歡迎來到 YY 滴數(shù)據(jù)結(jié)構(gòu)系列，熱烈歡迎！本章主要內(nèi)容面向接觸過C++的老鐵主要內(nèi)容含：歡迎訂閱 YY 滴C++專欄！更多干貨持續(xù)更新！以下是傳送門！ YY的《C++》專欄 YY的《C++11》專欄 YY的《Linux》專欄 YY的《數(shù)據(jù)結(jié)構(gòu)》專欄 YY的《C語言基礎(chǔ)》專欄 YY的《初
2024年02月05日
瀏覽(24)
【數(shù)據(jù)結(jié)構(gòu)（C++）】樹型查找——二叉搜索樹
目錄 1. 二叉搜索樹 1.1 二叉搜索樹的概念 1.2 二叉搜索樹類模板 1.3 二叉搜索樹的操作 1.3.1 查找 1.3.2 插入 1.3.3 刪除 1.4 二叉搜索樹的性能分析 2. 平衡二叉樹 2.1 平衡二叉樹的概念 2.2 平衡二叉樹類模板 2.3 二叉搜索樹的插入 3. 紅黑樹 3.1 紅黑樹的概念 3.2 紅黑樹類模板二叉搜索
2024年02月10日
瀏覽(25)
數(shù)據(jù)結(jié)構(gòu)：二叉搜索樹（非遞歸實(shí)現(xiàn)）
目錄 1、二叉搜索樹 2、二叉搜索樹的相關(guān)操作。 1、查找 2、插入 3、刪除 3、代碼實(shí)現(xiàn)（非遞歸）二叉搜索樹（Binary Search Tree，簡(jiǎn)稱BST）是一種特殊的二叉樹，其中每個(gè)節(jié)點(diǎn)的值大于其左子樹中所有節(jié)點(diǎn)的值，小于其右子樹中所有節(jié)點(diǎn)的值。這種特性使得二叉搜索樹具有快速
2024年03月08日
瀏覽(25)
【數(shù)據(jù)結(jié)構(gòu)】二叉搜索樹的實(shí)現(xiàn)
二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值它的左右子樹也分別為二叉搜索樹比如以下就為一個(gè)人二叉搜
2024年02月09日
瀏覽(33)
【Java 數(shù)據(jù)結(jié)構(gòu)】實(shí)現(xiàn)一個(gè)二叉搜索樹
目錄 ? 1、認(rèn)識(shí)二叉搜索樹 2、實(shí)現(xiàn)一個(gè)二叉搜索樹 2.1 成員變量 2.2 insert 方法 2.3 search 方法? 2.4 remove 方法(重點(diǎn)) 3、二叉搜索樹總結(jié) 從字面上來看，它只比二叉樹多了搜索兩個(gè)字，我們回想一下，如果要是在二叉樹中查找一個(gè)元素的話，需要遍歷這棵樹，效率很慢，而二叉搜
2024年02月02日
瀏覽(24)
【數(shù)據(jù)結(jié)構(gòu)】二叉搜索樹BST的實(shí)現(xiàn)（遞歸）
目錄 1.概念 2.圖解： 3.元素插入操作 1.思路分析： 2.代碼展示： 4.元素查找操作 1.前提根節(jié)點(diǎn)不為空 2.代碼展示： 5.查找BST中的最大最小值代碼展示： 6.刪除BST中的最大最小值代碼展示： 7.刪除BST中的任意元素代碼展示： ? 二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，
2023年04月09日
瀏覽(20)
【數(shù)據(jù)結(jié)構(gòu)】二叉搜索樹——二叉搜索樹的概念和介紹、二叉搜索樹的簡(jiǎn)單實(shí)現(xiàn)、二叉搜索樹的增刪查改
??二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹: ??（1）若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值 ??（2）若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值 ??（3）它的左右子樹也分別為二叉
2024年02月09日
瀏覽(26)
Java 數(shù)據(jù)結(jié)構(gòu)篇-實(shí)現(xiàn)二叉搜索樹的核心方法
??博客主頁：?【小扳_-CSDN博客】 ?感謝大家點(diǎn)贊??收藏?評(píng)論? ? 文章目錄 ? ? ? ? 1.0 二叉搜索樹的概述 ? ? ? ? 2.0 二叉搜索樹的成員變量及其構(gòu)造方法 ? ? ? ? 3.0 實(shí)現(xiàn)二叉樹的核心接口 ? ? ? ? 3.1?實(shí)現(xiàn)二叉搜索樹 - 獲取值?get(int key) ? ? ? ? 3.2?實(shí)現(xiàn)二叉搜索樹
2024年02月04日
瀏覽(21)

<xmp id="q0yhp">

<track id="q0yhp"><center id="q0yhp"></center></track>