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

詳解C++二叉搜索樹的原理及實(shí)現(xiàn)

 更新時(shí)間：2023年08月01日 10:02:52   作者：Ggggggtm  
二叉搜索樹又稱二叉排序樹,二叉搜索樹是一種二叉樹,其中每個(gè)節(jié)點(diǎn)的值大于其左子樹中的任何節(jié)點(diǎn),并且小于其右子樹中的任何節(jié)點(diǎn),本文小編就給大家講講C++二叉搜索樹的操作及實(shí)現(xiàn),感興趣的同學(xué)跟著小編一起來看看吧

一、二叉搜索樹的概念

  二叉搜索樹又稱二叉排序樹，二叉搜索樹是一種二叉樹，其中每個(gè)節(jié)點(diǎn)的值大于其左子樹中的任何節(jié)點(diǎn)，并且小于其右子樹中的任何節(jié)點(diǎn)。這個(gè)特性使得二叉搜索樹具有高效的查找、插入和刪除操作。下圖即為二叉搜索樹：

二、二叉搜索樹的操作及實(shí)現(xiàn)

  由于二叉搜索樹的特性，使得二叉搜索樹具有高效的查找、插入和刪除操作。在我們分析各個(gè)操作的效率和實(shí)現(xiàn)原理之前，我們先把二叉樹的大體結(jié)構(gòu)列出，代碼如下：

template<class K>
struct BSTreeNode
{
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;
	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};
template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree()
		:_root(nullptr)
	{}
private:
	Node* _root;
};

2.1 二叉搜索樹的插入

2.1.1 插入的原理

插入一個(gè)新的值時(shí)，我們需要遵守二叉搜索樹的特性。首先，我們從根節(jié)點(diǎn)開始找到合適的插入位置。具體操作是，將新值與當(dāng)前節(jié)點(diǎn)的值比較，若新值小于當(dāng)前節(jié)點(diǎn)的值，則往左子樹方向找到合適的葉子節(jié)點(diǎn)進(jìn)行插入；反之，若新值大于當(dāng)前節(jié)點(diǎn)的值，則往右子樹方向找到合適的葉子節(jié)點(diǎn)進(jìn)行插入。

合適的葉子節(jié)點(diǎn)指的是一直往下查找，直到該位置為空（nullptr）時(shí)，此時(shí)新值就應(yīng)該插入該位置。即使我們找到了合適的位置，如果不知道該位置的父節(jié)點(diǎn)的話，似乎并不能連接到該樹中。所以在查找合適位置的同時(shí)，還需要維護(hù)一個(gè)父節(jié)點(diǎn)。但是我們需要注意，二叉搜索樹中沒有重復(fù)的值。如果插入重復(fù)的值，那么就會插入失敗。

同時(shí)，我們再插入前，要判斷該樹是否為空。否則就會出現(xiàn)意想不到的bug。

2.1.2 插入的代碼實(shí)現(xiàn)

我們看代碼實(shí)現(xiàn)：

    bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			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);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}

2.2 二叉搜索樹的查找

2.2.1 查找的原理

其實(shí)在上述的插入中，我們不就進(jìn)行了查找嗎？！為了查找一個(gè)特定的值，我們從根節(jié)點(diǎn)開始向下遍歷二叉樹，根據(jù)當(dāng)前節(jié)點(diǎn)的值與目標(biāo)值的大小關(guān)系來選擇往左子樹或者右子樹進(jìn)行遍歷。如果找到目標(biāo)值，則返回成功；否則，如果遍歷到葉子節(jié)點(diǎn)還未找到目標(biāo)值，則返回失敗。

2.2.2 查找的代碼實(shí)現(xiàn)

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

2.3 二叉搜索樹的刪除

2.3.1 刪除的原理

刪除操作是相對復(fù)雜的，因?yàn)槲覀冃枰幚聿煌那闆r。具體步驟如下：

  • 如果要?jiǎng)h除的節(jié)點(diǎn)沒有子節(jié)點(diǎn)，直接刪除即可。

  • 如果要?jiǎng)h除的節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，將子節(jié)點(diǎn)替換為要?jiǎng)h除的節(jié)點(diǎn)即可。

  • 如果要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，需要用其右子樹中最小的節(jié)點(diǎn)替換要?jiǎng)h除的節(jié)點(diǎn)，并且刪除右子樹中最小的節(jié)點(diǎn)。

對上述的情況在進(jìn)行分析和總結(jié)，一共可分為如下情況：

  1. 要?jiǎng)h除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn) 。刪除該結(jié)點(diǎn)且使被刪除節(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除節(jié)點(diǎn)的左孩子結(jié)點(diǎn)--直接刪除。

  2. 要?jiǎng)h除的結(jié)點(diǎn)只有右孩子結(jié)點(diǎn) 。刪除該結(jié)點(diǎn)且使被刪除節(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的右孩子結(jié)點(diǎn)--直接刪除。

  3. 要?jiǎng)h除的結(jié)點(diǎn)有左、右孩子結(jié)點(diǎn)。在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最小)，用它的值填補(bǔ)到被刪除節(jié)點(diǎn)中，再來處理該結(jié)點(diǎn)的刪除問題--替換法刪除

為什么是上述的三種情況呢？我們詳細(xì)分析一下是為什么。

假如我們要?jiǎng)h除的節(jié)點(diǎn)沒有子節(jié)點(diǎn)，我們可以把這種情況看成要?jiǎng)h除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)或者只有右孩子結(jié)點(diǎn)。把另一個(gè)存在的孩子看成空（nullptr）。這樣刪除后，直接可讓其父節(jié)點(diǎn)指向空（nullptr），而不是野指針。

要?jiǎng)h除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)或者要?jiǎng)h除的結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)是兩種不同的情況。因?yàn)樗麄兊牟僮魇遣煌摹?/p>

要?jiǎng)h除的結(jié)點(diǎn)有左、右孩子結(jié)點(diǎn)這種情況較為復(fù)雜。首先我們應(yīng)該找到能夠填充該位置的節(jié)點(diǎn)。根據(jù)二叉搜索樹的特性每個(gè)節(jié)點(diǎn)的值大于其左子樹中的任何節(jié)點(diǎn)，并且小于其右子樹中的任何節(jié)點(diǎn)，我們找到的值應(yīng)該也滿足此特點(diǎn)。有兩個(gè)節(jié)點(diǎn)的只滿足該情況：該節(jié)點(diǎn)左子樹的最大值、該節(jié)點(diǎn)右子樹的最小值。本篇文章講述的是左子樹的最大值。找左子樹的最大值，就是該子樹最右邊的節(jié)點(diǎn)。找到后交值換再刪除。

要?jiǎng)h除的結(jié)點(diǎn)有左、右孩子結(jié)點(diǎn)這種情況，在找左子樹的最大值時(shí)也應(yīng)該維護(hù)一個(gè)父節(jié)點(diǎn)。為什么呢？因?yàn)槲覀冋业阶笞訕涞淖畲笾禃r(shí)，與要?jiǎng)h除的節(jié)點(diǎn)的值交換后，要?jiǎng)h除該節(jié)點(diǎn)（交換前的左子樹最大值的節(jié)點(diǎn)）。此時(shí)該節(jié)點(diǎn)的右節(jié)點(diǎn)一定為空（nullptr），只需要關(guān)心左節(jié)點(diǎn)就行。

2.3.2 刪除的代碼實(shí)現(xiàn)

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 (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}
				}// 右為空
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}					
				} // 左右都不為空 
				else
				{
					// 找替代節(jié)點(diǎn)
					Node* parent = cur;
					Node* leftMax = cur->_left;
					while (leftMax->_right)
					{
						parent = leftMax;
						leftMax = leftMax->_right;
					}
					swap(cur->_key, leftMax->_key);
					if (parent->_left == leftMax)
					{
						parent->_left = leftMax->_left;
					}
					else
					{
						parent->_right = leftMax->_left;
					}
					cur = leftMax;
				}
				delete cur;
				return true;
			}
		}
		return false;
	}

2.4 二叉搜索樹的中序遍歷

二叉搜索樹又稱二叉排序樹，為什么又名二叉排序樹呢？二叉搜索樹的中序遍歷的結(jié)果就是一個(gè)有序的結(jié)果。代碼如下：

public:
    Inorder()
    {
        _Inorder(_root);
    }
private:   
    void _Inorder(Node* root)                                                                                                                                
    {    
        if(root==nullptr)    
        {    
            return ;    
        }    
        _Inorder(root->left);    
        cout<<root->_key<<" ";    
        _Inorder(root->right);    
    }

2.5 遞歸實(shí)現(xiàn)二叉樹的操作

我們上述講解的是非遞歸形式的二叉搜索樹的各個(gè)操作。當(dāng)我們了解非遞歸形式的二叉搜索樹的各個(gè)操作后，我們下面給出遞歸形式的二叉搜索樹的各個(gè)操作的代碼，思路就不在講解：

public:
    bool eraseR(const K& key)
    {
        return _eraseR(_root,key);
    }
    bool insertR(const K& key)
    {
        return _insertR(_root,key);
    }
    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)
        {
            _findR(root->left,key);
        }
        else if(root->_key<key)
        {
            _findR(root->right,key);
        }
        else
        {
            return true;
        }
    }
    bool _eraseR(Node*& root,const K& key)
    {
        if(root==nullptr)
        {
            return false;
        }                                                                                                                                                    
        if(root->_key>key)
        {
            _eraseR(root->left,key);
        }
        else if(root->_key<key)
        {
            _eraseR(root->right,key);
        }
        else
        {
            Node* del=root;
            if(root->left==nullptr)
            {
                root=root->right;
            }
            else if(root->right==nullptr)
            {
                root=root->left;
            }
            else
            {
                Node* min=root->right;
                while(min->left)
                {
                    min=min->left;
                }
                swap(root->_key,min->_key);
                return _eraseR(root->right,key);
            }
            delete del;
            return true;
        }
    }
    bool _insertR(Node*& root,const K& key)
    {
        if(root==nullptr)
        {
            root=new Node(key);
            return true;
        }
        if(root->_key>key)
        {
            _insertR(root->left,key);
        }                                                                                                                                                    
        else if(root->_key<key)
        {
            _insertR(root->right,key);
        }
        else
        {
            return false;
        }
    }

三、二叉搜索樹的性能分析

插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹中各個(gè)操作的性能。對有n個(gè)結(jié)點(diǎn)的二叉搜索樹，若每個(gè)元素查找的概率相等，則二叉搜索樹平均查找長度是結(jié)點(diǎn)在二叉搜索樹的深度的函數(shù)，即結(jié)點(diǎn)越深，則比較次數(shù)越多。 但對于同一個(gè)關(guān)鍵碼集合，如果各關(guān)鍵碼插入的次序不同，可能得到不同結(jié)構(gòu)的二叉搜索樹：

通過上述我們也發(fā)現(xiàn)，二叉搜索樹的性能主要取決于樹的平衡度。最理想的情況下，樹是完全平衡的，即左子樹節(jié)點(diǎn)數(shù)目和右子樹節(jié)點(diǎn)數(shù)目相差不超過1。在這種情況下，查找、插入和刪除操作的平均時(shí)間復(fù)雜度為 O(log n)。但是，最壞情況下，樹可能變得非平衡，導(dǎo)致這些操作的時(shí)間復(fù)雜度退化為O(n)，其中n是樹中節(jié)點(diǎn)的總數(shù)。

為了避免二叉搜索樹在使用過程中出現(xiàn)不平衡的情況，可以使用自平衡的二叉搜索樹，如紅黑樹或AVL樹。這些樹通過旋轉(zhuǎn)、調(diào)整節(jié)點(diǎn)顏色等策略來保持樹的平衡度，從而提高了整體性能。

總結(jié)起來，二叉搜索樹在C++編程語言中的實(shí)現(xiàn)非常靈活且易于理解。但需要注意的是，對于大型數(shù)據(jù)集合，建議使用自平衡的二叉搜索樹，以確保操作的效率和性能。

以上就是詳解C++二叉搜索樹的原理及實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C++二叉搜索樹的資料請關(guān)注腳本之家其它相關(guān)文章！

相關(guān)文章

最新評論