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

【C++庖丁解?！慷嫠阉鳂洌˙inary Search Tree，BST）

2年前作者：RO-BERRY分類：Toy博客閱讀(32)違法舉報

這篇具有很好參考價值的文章主要介紹了【C++庖丁解?！慷嫠阉鳂洌˙inary Search Tree，BST）。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

【C++庖丁解?！慷嫠阉鳂洌˙inary Search Tree，BST）,c++入門到精通,c++,java,開發(fā)語言

??你好，我是 RO-BERRY ?? 致力于C、C++、數據結構、TCP/IP、數據庫等等一系列知識 ??感謝你的陪伴與支持，故事既有了開頭，就要畫上一個完美的句號，讓我們一起加油

【C++庖丁解?！慷嫠阉鳂洌˙inary Search Tree，BST）,c++入門到精通,c++,java,開發(fā)語言

1. 二叉搜索樹概念

二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質的二叉樹:

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

二叉搜索樹（Binary Search Tree，簡稱BST）是種常用的數據結構，它是一棵二叉樹，并且滿足以下性質：

對任意節(jié)點，其左子樹中的節(jié)點的值都小于該節(jié)點的值。
對于任意節(jié)點，其右子樹中的所有節(jié)點的值都大于該節(jié)點的值。
左子樹和右子樹也都是二叉搜索樹。
二叉搜索樹的這種特性使得它在查找、插入和刪除操作上具有高效性能。通過比較節(jié)點的值，可以快速定位到目標節(jié)點或者確定插入位置。

二叉搜索樹的操作包括：

查找：從根節(jié)點開始，遞歸地比較目標值與當前節(jié)點的值，直到找到目標節(jié)點或者遍歷到葉子節(jié)點。
插入：從根節(jié)點開始，遞歸地比較目標值與當前節(jié)點的值，根據大小關系選擇左子樹或右子樹進行插入，直到找到合適的插入位置。
刪除：刪除操作比較復雜，需要考慮被刪除節(jié)點的子節(jié)點情況。可以分為三種情況：被刪除節(jié)點沒有子節(jié)點、被刪除節(jié)點只有一個子節(jié)點、被刪除節(jié)點有兩個子節(jié)點。
二叉搜索樹的時間復雜度取決于樹的高度，平均情況下為O(log n)，最壞情況下為O(n)。為了保持樹的平衡，可以使用平衡二叉搜索樹（如AVL樹、紅黑樹）來優(yōu)化性能。

【C++庖丁解?！慷嫠阉鳂洌˙inary Search Tree，BST）,c++入門到精通,c++,java,開發(fā)語言

2. 二叉搜索樹操作

【C++庖丁解?！慷嫠阉鳂洌˙inary Search Tree，BST）,c++入門到精通,c++,java,開發(fā)語言

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

二叉搜索樹的查找
a、從根開始比較，查找，比根大則往右邊走查找，比根小則往左邊走查找。
b、最多查找高度次，走到到空，還沒找到，這個值不存在。
二叉搜索樹的插入
插入的具體過程如下：
a. 樹為空，則直接新增節(jié)點，賦值給root指針
b. 樹不空，按二叉搜索樹性質查找插入位置，插入新節(jié)點

【C++庖丁解?！慷嫠阉鳂洌˙inary Search Tree，BST）,c++入門到精通,c++,java,開發(fā)語言

二叉搜索
首先查找元素是否在二叉搜索樹中，如果不存在，則返回, 否則要刪除的結點可能分下面四種情況：

a. 要刪除的結點無孩子結點
b. 要刪除的結點只有左孩子結點
c. 要刪除的結點只有右孩子結點
d. 要刪除的結點有左、右孩子結點

看起來有待刪除節(jié)點有4中情況，實際情況a可以與情況b或者c合并起來，因此真正的刪除過程如下：

情況b：刪除該結點且使被刪除節(jié)點的雙親結點指向被刪除節(jié)點的左孩子結點–直接刪除
情況c：刪除該結點且使被刪除節(jié)點的雙親結點指向被刪除結點的右孩子結點–直接刪除
情況d：在它的右子樹中尋找中序下的第一個結點(關鍵碼最小)，用它的值填補到被刪除節(jié)點中，再來處理該結點的刪除問題–替換法刪除

【C++庖丁解?！慷嫠阉鳂洌˙inary Search Tree，BST）,c++入門到精通,c++,java,開發(fā)語言

3. 二叉搜索樹的實現

3.1 準備工作

結點結構體BSTreeNode

我們實現二叉搜索樹需要定義其結點，定義其左右節(jié)點以及value，方便后續(xù)操作進行

template<class K>
struct BSTreeNode      //二叉樹結點
{
	typedef BSTreeNode<K> Node;     //簡化名稱

	Node* _left;        //左節(jié)點
	Node* _right;       //右節(jié)點
	K _key;             //結點value

	BSTreeNode(const K& key)    //構造函數
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};

二叉搜索樹BinarySearchTree

template<class K>
class BinarySearchTree
{
	typedef BSTreeNode<K> Node;    //節(jié)點名稱簡化
public:
	.....         //二叉搜索樹函數接口
private:
	Node* _root = nullptr;        //省略了初始化在定義的時候就進行初始化
};

3.2 函數體實現

??bool Insert(const K& key)

實現思路：

二叉搜索樹的定義是左邊的子結點必定小于父節(jié)點，右邊的子結點必定大于父節(jié)點，所以我們采取key值與節(jié)點value比較，如果key大于節(jié)點value，則繼續(xù)與節(jié)點右子節(jié)點比較；如果key小于節(jié)點value，則繼續(xù)與節(jié)點左子節(jié)點比較，最終如果走到空的位置，則進行插入。

這里我們需要定義一個parent節(jié)點幫助我們定位最終插入后其父節(jié)點的位置，然后將父節(jié)點與新插入的結點進行連接，將父節(jié)點的value與key值比較，若key大于value，那么肯定是被插入到父節(jié)點的右子樹里了；若key小于value，則反之。

另：我們要獨自判斷空樹的情況，不然會出現程序崩潰；搜索二叉樹的每一個節(jié)點數值不能一樣，那么我們如果插入的key與某個value相等，也會返回false

實現代碼：

	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;    //父節(jié)點
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if ((cur->_key > key))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(key);
		if (parent->_key < key)   //連接父節(jié)點
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}

??bool Find(const K& key)

實現思路：

左邊的子結點必定小于父節(jié)點，右邊的子結點必定大于父節(jié)點，所以我們采取key值與節(jié)點value比較，如果key大于節(jié)點value，則繼續(xù)與節(jié)點右子節(jié)點比較；如果key小于節(jié)點value，則繼續(xù)與節(jié)點左子節(jié)點比較，最終如果走到空的位置，則返回false，如果找到與key相等的value，則返回true。

實現代碼：

	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if ((cur->_key > key))
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

??打印二叉搜索樹void InOrder()

實現思路：

使用遞歸實現中序遍歷，二叉搜索樹的中序遍歷其實輸出出來是一個遞增排序的數組，從根節(jié)點開始，訪問其左子樹，并進行打印，然后訪問右子樹進行打印。
這里用了一個巧妙的方法： 我們對二叉搜索樹打印需要傳入根節(jié)點位置，才能進行遞歸，但是根節(jié)點為私有成員，我們要么寫一個GetRoot()函數獲取到根節(jié)點位置，才能傳入，我們在這里可以對其進行封裝，在上面重新定義一個打印函數，然后在這個函數里面調用剛剛的打印函數，并傳入root，這樣就不用在調用的時候傳入root了。

實現代碼：

	void InOrder()       //巧妙調用輸出函數
	{
		_InOrder(_root);
		cout << endl;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

??刪除 Erase

實現思路：
二叉搜索樹（Binary Search Tree，BST）的刪除操作是指在BST中刪除一個指定的節(jié)點。刪除操作的模擬實現可以按照以下步驟進行：

首先，需要找到要刪除的節(jié)點。從根節(jié)點開始，比較要刪除的節(jié)點值與當前節(jié)點值的大小關系，如果相等則找到了要刪除的節(jié)點，如果小于當前節(jié)點值，則繼續(xù)在左子樹中查找，如果大于當前節(jié)點值，則繼續(xù)在右子樹中查找。重復這個過程直到找到要刪除的節(jié)點或者遍歷到葉子節(jié)點為止。

如果找到了要刪除的節(jié)點，需要考慮以下幾種情況：

如果要刪除的節(jié)點是葉子節(jié)點（沒有子節(jié)點），直接刪除即可。
如果要刪除的節(jié)點只有一個子節(jié)點，將其子節(jié)點替代要刪除的節(jié)點即可。
如果要刪除的節(jié)點有兩個子節(jié)點，需要找到其右子樹中的最小節(jié)點（或者左子樹中的最大節(jié)點），將其值替換到要刪除的節(jié)點上，并將最?。ɑ蜃畲螅┕?jié)點刪除。

實現刪除操作時，需要注意維護BST的性質，即左子樹中的所有節(jié)點值都小于當前節(jié)點值，右子樹中的所有節(jié)點值都大于當前節(jié)點值。

實現代碼：

	bool Erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				if (cur->_left == nullptr)   //左子樹為空
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_right)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}

					delete cur;
					return true;
				}
				else if (cur->_right == nullptr)  //右子樹為空
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_right)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}

					delete cur;
					return true;
				}
				else                          //左右子樹都不為空
				{
					// 替換法
					Node* rightMinParent = cur;
					Node* rightMin = cur->_right;
					while (rightMin->_left)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}

					cur->_key = rightMin->_key;

					if (rightMin == rightMinParent->_left)     //根節(jié)點
						rightMinParent->_left = rightMin->_right;    
					else
						rightMinParent->_right = rightMin->_right;

					delete rightMin;
					return true;
				}
			}
		}

		return false;
	}

??構造函數、析構函數、拷貝構造以及復制拷貝

這里直接實現，不再講述原理，因為這一塊比較基礎了

	//強制生成默認構造
	BinarySearchTree() = default;

	BinarySearchTree(const BinarySearchTree<K>& t)   //拷貝構造函數
	{
		_root = Copy(t._root);
	}
	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* newRoot = new Node(root->_key);
		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);
		return new Root;
	}

	BinarySearchTree<K>& operator=(const BinarySearchTree<K>& t)    //賦值拷貝
	{
		swap(_root, t._root);
		return *this;
	}

	~BinarySearchTree()   //析構函數
	{
		Destroy(_root);
	}

3.3 函數體實現(優(yōu)化版)

我們的優(yōu)化主要用了封裝的藝術

??優(yōu)化版insert函數

我們在上面的函數實現時需要判斷最終在左子樹還是在右子樹，并且還要定義一個parent來存儲其父節(jié)點，而我們對其進行優(yōu)化，可以看到我們在函數參數里加了一個Node*& root，正是這個參數，我們使用了引用，就不需要再判斷其是左子樹還是右子樹，也不用記錄其父節(jié)點，因為引用就是別名，我們對其進行修改就是對這個指針進行修改，這里還用了遞歸，讓我們的代碼量大大減小

public:
	bool InsertR(const K& key)      //函數放在public便于訪問
	{
		return _InsertR(_root, key);
	}
private:                              //函數的具體實現放在private
	bool _InsertR(Node*& root,const K& key)   //這里使用別名，修改的就是其本身，就不用判斷左右節(jié)點了
	{
		if (root == nullptr)
		{
			root=new Node(key);
			return true;
		}
		if (root->_key < key)                 //小于key就遍歷右子樹
		{
			return _InsertR(root->_right, key);
	}
		else if (root->_key > key)            //大于key就遍歷左子樹
		{
			return _InsertR(root->_left, key);  
		}
		else
		{
			return false;
		}
	}

??優(yōu)化版find函數

public:
	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	} 
private:
	bool _FindR(Node* root,const K& key)
	{
		if (root == nullptr)
			return false;
		if (root->_key < key)
		{
			return _FindR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _FindR(root->_left, key);
		}
		else
		{
			return true;
		}
	}

??優(yōu)化版Erase函數

public:
	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}
private:
	bool _EraseR(Node*& root, const K& key)
	{
		if (root == nullptr)
			return false;
		if (root->_key < key)
		{
			return _EraseR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _EraseR(root->_left, key);
		}
		else
		{
			Node* del = root;     //保存該節(jié)點便于刪除
			if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else
			{
				Node* rightMin = root->_right;
				while (rightMin->_left)
				{
					rightMin = rightMin->_left;
				}

				swap(root->_key, rightMin->_key);

				return _EraseR(root->_right, key);
			}
			delete del;
			return true;
		}
	}

3.4 源代碼BinarySearchTree.h

#pragma once

#include<iostream>
using namespace std;
template<class K>
struct BSTreeNode
{
	typedef BSTreeNode<K> Node;

	Node* _left;
	Node* _right;
	K _key;

	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};

template<class K>
class BinarySearchTree
{
	typedef BSTreeNode<K> Node;
public:
	//強制生成默認構造
	BinarySearchTree() = default;

	BinarySearchTree(const BinarySearchTree<K>& t)   //拷貝構造函數
	{
		_root = Copy(t._root);
	}
	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* newRoot = new Node(root->_key);
		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);
		return new Root;
	}

	BinarySearchTree<K>& operator=(const BinarySearchTree<K>& t)    //賦值拷貝
	{
		swap(_root, t._root);
		return *this;
	}

	~BinarySearchTree()   //析構函數
	{
		Destroy(_root);
	}

	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;    //父節(jié)點
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if ((cur->_key > key))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(key);
		if (parent->_key < key)   //連接父節(jié)點
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}

	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if ((cur->_key > key))
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}


	bool Erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				if (cur->_left == nullptr)   //左子樹為空
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_right)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}

					delete cur;
					return true;
				}
				else if (cur->_right == nullptr)  //右子樹為空
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_right)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}

					delete cur;
					return true;
				}
				else                          //左右子樹都不為空
				{
					// 替換法
					Node* rightMinParent = cur;
					Node* rightMin = cur->_right;
					while (rightMin->_left)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}

					cur->_key = rightMin->_key;

					if (rightMin == rightMinParent->_left)     //根節(jié)點
						rightMinParent->_left = rightMin->_right;    
					else
						rightMinParent->_right = rightMin->_right;

					delete rightMin;
					return true;
				}
			}
		}

		return false;
	}


	void InOrder()       //巧妙調用輸出函數
	{
		_InOrder(_root);
		cout << endl;
	}

///
	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	} 

	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}

	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}
private:

	void Destroy(Node* root)
	{
		if (root == nullptr)
			return;

		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}

	bool _EraseR(Node*& root, const K& key)
	{
		if (root == nullptr)
			return false;
		if (root->_key < key)
		{
			return _EraseR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _EraseR(root->_left, key);
		}
		else
		{
			Node* del = root;     //保存該節(jié)點便于刪除
			if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else
			{
				Node* rightMin = root->_right;
				while (rightMin->_left)
				{
					rightMin = rightMin->_left;
				}

				swap(root->_key, rightMin->_key);

				return _EraseR(root->_right, key);
			}
			delete del;
			return true;
		}
	}

	bool _InsertR(Node*& root,const K& key)   //這里使用別名，修改的就是其本身，就不用判斷左右節(jié)點了
	{
		if (root == nullptr)
		{
			root=new Node(key);
			return true;
		}
		if (root->_key < key)
		{
			return _InsertR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _InsertR(root->_left, key);
		}
		else
		{
			return false;
		}
	}



	bool _FindR(Node* root,const K& key)
	{
		if (root == nullptr)
			return false;
		if (root->_key < key)
		{
			return _FindR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _FindR(root->_left, key);
		}
		else
		{
			return true;
		}
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

	Node* _root = nullptr;
};

4. 二叉搜索樹的應用

K模型：K模型即只有key作為關鍵碼，結構中只需要存儲Key即可，關鍵碼即為需要搜索到的值。

比如:
給一個單詞word，判斷該單詞是否拼寫正確，具體方式如下：
以詞庫中所有單詞集合中的每個單詞作為key，構建一棵二叉搜索樹在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯誤。

KV模型：每一個關鍵碼key，都有與之對應的值Value，即<Key, Value>的鍵值對。該種方式在現實生活中非常常見：

比如:
英漢詞典就是英文與中文的對應關系，通過英文可以快速找到與其對應的中文，英文單詞與其對應的中文<word, chinese>就構成一種鍵值對；再比如統(tǒng)計單詞次數，統(tǒng)計成功后，給定單詞就可快速找到其出現的次數，單詞與其出現次數就是<word, count>就構成一種鍵值對。

kv二叉樹實現

namespace key_value
{
	template<class K, class V>
	struct BSTreeNode
	{
		typedef BSTreeNode<K, V> Node;

		Node* _left;
		Node* _right;
		K _key;
		V _value;

		BSTreeNode(const K& key, const V& value)
			:_left(nullptr)
			,_right(nullptr)
			,_key(key)
			,_value(value)
		{}
	};

	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

			cur = new Node(key, value);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}

			return true;
		}

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

			return nullptr;
		}

		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_right)
							{
								parent->_right = cur->_right;
							}
							else
							{
								parent->_left = cur->_right;
							}
						}

						delete cur;
						return true;
					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (cur == parent->_right)
							{
								parent->_right = cur->_left;
							}
							else
							{
								parent->_left = cur->_left;
							}
						}

						delete cur;
						return true;
					}
					else
					{
						// 替換法
						Node* rightMinParent = cur;
						Node* rightMin = cur->_right;
						while (rightMin->_left)
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_left;
						}

						cur->_key = rightMin->_key;

						if (rightMin == rightMinParent->_left)
							rightMinParent->_left = rightMin->_right;
						else
							rightMinParent->_right = rightMin->_right;

						delete rightMin;
						return true;
					}
				}
			}

			return false;
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;

			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}

	private:
		Node* _root = nullptr;
	};
}

5. 二叉搜索樹的性能分析

插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹中各個操作的性能。
對有n個結點的二叉搜索樹，若每個元素查找的概率相等，則二叉搜索樹平均查找長度是結點在二叉搜索樹的深度的函數，即結點越深，則比較次數越多。
但對于同一個關鍵碼集合，如果各關鍵碼插入的次序不同，可能得到不同結構的二叉搜索樹：
【C++庖丁解?！慷嫠阉鳂洌˙inary Search Tree，BST）,c++入門到精通,c++,java,開發(fā)語言

最優(yōu)情況下，二叉搜索樹為完全二叉樹(或者接近完全二叉樹)，其平均比較次數為： $log_2 N$
最差情況下，二叉搜索樹退化為單支樹(或者類似單支)，其平均比較次數為： $\frac{N}{2}$

問題：如果退化成單支樹，二叉搜索樹的性能就失去了。那能否進行改進，不論按照什么次序插
入關鍵碼，二叉搜索樹的性能都能達到最優(yōu)？那么我們后續(xù)章節(jié)學習的AVL樹和紅黑樹就可以上
場了。文章來源地址http://www.zghlxwxcb.cn/news/detail-844105.html

到了這里，關于【C++庖丁解?！慷嫠阉鳂洌˙inary Search Tree，BST）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！

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

分享到：

領支付寶紅包贊助服務器費用

二叉搜索樹（Binary Search Tree，BST）
二叉搜索樹（Binary Search Tree），也稱二叉查找樹或二叉排序樹，是一種特殊的二叉樹，它滿足以下性質對于二叉搜索樹的每個節(jié)點左子樹中的所有節(jié)點的值都小于該節(jié)點的值右子樹中的所有節(jié)點的值都大于（或等于）該節(jié)點的值對于二叉搜索樹的任意節(jié)點，其左子樹和右子
2024年02月09日
瀏覽(21)
二叉搜索樹(Binary_Search_Tree)
二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質的二叉樹：若它的左子樹不為空，則左子樹上所有節(jié)點的值都小于根節(jié)點的值。若它的右子樹不為空，則右子樹上所有節(jié)點的值都大于根節(jié)點的值。它的左右子樹也分別為二叉搜索樹。如： a、從根開始
2024年04月28日
瀏覽(20)
【C++庖丁解?！繉崿Fstring容器的增刪查改 | string容器的基本接口使用
??你好，我是 RO-BERRY ?? 致力于C、C++、數據結構、TCP/IP、數據庫等等一系列知識 ??感謝你的陪伴與支持，故事既有了開頭，就要畫上一個完美的句號，讓我們一起加油函數名稱功能說明 push_back 在字符串后尾插字符c append 在字符串后追加一個字符串 operator+= (重點) 在字符
2024年03月14日
瀏覽(29)
最優(yōu)二叉搜索樹(Optimal Binary Search Tree)_20230401
前言如果有序數組或有序表中的各個元素查找概率相等，那么采用二叉搜索樹(BST)進行折半查找，性能最優(yōu)。如果有序表中各個記錄的查找概率不相等，情況又如何呢？先看一個具體例子。已知有序表keys，同時給出各個元素的查詢頻率，注意到各個元素的查詢頻率不相同。
2024年02月12日
瀏覽(41)
【C++庖丁解?！縎TL之vector容器的介紹及使用 | vector迭代器的使用 | vector空間增長問題
??你好，我是 RO-BERRY ?? 致力于C、C++、數據結構、TCP/IP、數據庫等等一系列知識 ??感謝你的陪伴與支持，故事既有了開頭，就要畫上一個完美的句號，讓我們一起加油 vector的文檔介紹 vector是表示可變大小數組的序列容器。就像數組一樣，vector也采用的連續(xù)存儲空間來存
2024年03月14日
瀏覽(36)
數據結構第四天： Complete Binary Search Tree 【搜索二叉樹，完全二叉樹】
?這道題需要的操作時排序并且需要遍歷，最重要的一點它是個完全二叉樹，所以數組是最適合的這道題我的思路來自于浙江大學課件7.0.2完全二叉樹這道題說白就是將輸入的樣例構造成一個完全搜索二叉樹。因為完全線索二叉樹的根節(jié)點一定是是一個處于左右子樹中間的那
2024年02月06日
瀏覽(28)
數據結構英文習題解析-第五章二叉搜索樹Binary Search Tree
前言：最近快到FDS考試了，po重刷了一下學校的題目，自己整理了一些解析orz 因為po在自己找解析和學習的過程中非常痛苦，所以在此共享一下我的題目和自己寫的解題思路，歡迎各位指出錯誤~全章節(jié)預計會陸續(xù)更新，可在專欄查看~ HW5 1.In a binary search tree, the keys on the same
2024年04月09日
瀏覽(22)
【C++庖丁解牛】面向對象的三大特性之一多態(tài) | 抽象類 | 多態(tài)的原理 | 單繼承和多繼承關系中的虛函數表
??你好，我是 RO-BERRY ?? 致力于C、C++、數據結構、TCP/IP、數據庫等等一系列知識 ??感謝你的陪伴與支持，故事既有了開頭，就要畫上一個完美的句號，讓我們一起加油需要聲明的，本節(jié)課件中的代碼及解釋都是在vs2013下的x86程序中，涉及的指針都是4bytes。如果要其他平臺
2024年04月10日
瀏覽(28)
庖丁解牛函數知識---C語言《1》
目錄前言： 1.程序中的函數 2.庫函數的學習和使用 3.自定義函數 4.傳值調用與傳址調用 5.形參與實參 6.練習---二分查找函數 ?博主CSDN:啊蘇要學習 ? ?專欄分類：C語言? ? C語言的學習，是為我們今后學習其它語言打好基礎，C生萬物！ ? 開始我們的C語言之旅吧！? ? 在計
2024年02月02日
瀏覽(16)
庖丁解牛函數知識---C語言《2》
目錄前言： 1.嵌套調用函數 2.鏈式訪問 3.函數的聲明與定義 4.*遞歸 5.遞歸與非遞歸 ?博主CSDN:啊蘇要學習 ? ?專欄分類：C語言? ? C語言的學習，是為我們今后學習其它語言打好基礎，C生萬物！ ? 開始我們的C語言之旅吧！? ? 在第一篇的基礎上，我們接著學習函數相關的
2024年02月02日
瀏覽(24)

<pre id="jhk4h"></pre>

<p id="jhk4h"><blockquote id="jhk4h"><tfoot id="jhk4h"></tfoot></blockquote></p>

<em id="jhk4h"><abbr id="jhk4h"><kbd id="jhk4h"></kbd></abbr></em>