C++深入細致探究二叉搜索樹

Posted on by

1、二叉搜索樹的概念

 二叉搜索樹又稱二叉排序樹，它可以是一顆空樹，亦可以是一顆具有如下性質的二叉樹：

  ①若根節點的左子樹不為空，則左子樹上的所有節點的值域都小於根節點的值

  ②若根節點的右子樹不為空，則右子樹上的所有節點的值域都大於根節點的值

  ③根節點的左右子樹分別也是一顆二叉搜索樹

例如下面的這棵二叉樹就是一棵二叉搜索樹：

註意：判定一棵二叉樹是否為二叉搜索樹一定要緊扣二叉搜索樹的概念~

2、二叉搜索樹的操作

聲明：該文章討論的是二叉搜索樹中節點值唯一的情況。

二叉搜索樹的查找

對於查找部分，充分利用二叉搜索樹的特性，即右子樹的value 大於根節點，左子樹的value小於根節點。

例如：查找下圖中的紅色方框中的節點

以6對應的節點為列，查找過程主要經歷如下幾個步驟：

  ①6與根節點5比較，6 > 5,因此到5的右子樹查找

  ①6與根節點7比較，6 < 7,因此到7的左子樹查找

  ①6與根節點6比較，6 == 6,此時查找成功！

總結基本步驟：

若根節點不為空：

  如果根節點的key == 查找的key—–>返回true

  如果根節點的key > 查找的key—–>轉到根節點的右子樹查找

  如果根節點的key < 查找的key—–>轉到根節點的左子樹查找

否則（根節點為空瞭），直接返回false，表示樹中不存在要查找的key

二叉搜索樹的插入

主要分兩大類的情況進行討論：

1、樹為空，直接插入

如下圖所示：

2、樹不空

①按照二叉搜索樹的性質查找插入的位置

②插入新的節點

e.g:在下面的二叉搜索樹中插入-1

第一步，查找插入位置：

 註意：要標記當前訪問的節點的雙親，否則，就算找到瞭插入位置，由於無法訪問其雙親，也是無法進行插入的。這裡使用parent來標記當前訪問節點的雙親節點。

具體過程如下圖：

第二步，插入新節點

判斷待插入節點(node)的值與parent標記的節點值的大小關系

if(node->value < parent->value)//新節點作為parent的左孩子
{
	parent->left = node;
}
else//新節點作為parent的右孩子
{
	parent->right = node;
}

以上就是二叉搜索樹插入的兩大類情況及其處理方式

二叉搜索樹的刪除

刪除也是分為兩大步驟：

1、找到待刪除結點，並標記其雙親

具體代碼片段如下：

Node* delNode = root;//標記待刪除結點
Node* parent = nullptr;//標記待刪除結點的雙親
while(delNode)
{
	if(delNode->value == value)
	{
		break;
	}
	else if(delNode->value > value)
	{
		parent = delNode;
		delNode = delNode->left;
	}
	else
	{
		parent = delNode;
		delNode = delNode->right;
	}
}

上述代碼執行完畢後，delNode有兩種情況，delNode == nullptr || delNode!=nullptr

下面我們就這兩種情況展開討論：

2、刪除該節點

Ⅰ、nullptr == delNode

  說明在二叉搜索樹中不存在要刪除的結點。直接return false；

Ⅱ、delNode != nullptr;

  在二叉搜索樹中找到瞭刪除結點，開始刪除。

刪除時，對於待刪除結點要根據其孩子節點分情況討論：

  ①待刪除結點是葉子結點

  ②待刪除結點隻有左孩子

  ③待刪除結點隻有有孩子

  ④待刪除結點左右孩子均存在

下面，我們就這4中情況展開討論：

情況一：待刪除結點時葉子節點

可以直接刪除，具體如下圖：

情況二：待刪除結點隻有左孩子

在此前提下，有兩類情形

1、delNode的雙親存在  

2、delNode的雙親不存在

下面就這兩種情況展開討論：

1、delNode的雙親存在

刪除過程見下圖：

2、delNode的雙親不存在

與上述僅存在葉子節點時存在的問題一樣，需要在delete待刪除結點之前，判斷delNode與parent的位置關系，進而確定是更新parent的left指針域還是right指針域

結合上述兩種情況，初步確定僅有左孩子的刪除代碼片段如下：

if(nullptr == parent)
{
	root = delNode->left;
}
else
{
	if(delNode == parent->left)
	{
		parent->left = delNode->left;
	}
	else
	{
		parent->right = delNode->left;
	}
}
delete delNode;

我們結合刪除節點是葉子節點 && 刪除節點僅有左子樹兩種情況來看，發現這兩種情況可以進行合並。合並後的代碼如下圖：

情況三：待刪除結點隻有右孩子

該情況與隻有左孩子的分析過程一樣，存在兩類情形，分別是

1、delNode的雙親存在  

2、delNode的雙親不存在

這裡不再進行分析，直接給出代碼：

情況四：待刪除結點左右孩子均存在

明確：該情況無法直接刪除，需要在其子樹中尋找替代結點 具體刪除步驟如下：

1、找替代節點：在delNode的右子樹（左子樹）找最左側（最右側）的結點並保存其雙親

2、將替代節點中的值域賦值給待刪除結點

3、將替代節點刪除掉

①如果替代節點找的是delNode右子樹的最左側結點，那麼待刪除的替代節點一定不會有左子樹，可能會有右子樹

②如果替代節點找的是delNode左子樹的最右側結點，那麼待刪除的替代節點一定不會有右子樹，可能會有左子樹 註意：一般情況下采用delNode右子樹的最左側結點作為替代節點

具體過程見下圖：

ok,下面給出實現的代碼：

3、二叉搜索樹的實現

數據結構：

template<class T>
struct BSTNode//每一個結點的結構
{
	BSTNode<T>* _left;//左指針域
	BSTNode<T>* _right;//右指針域
	T _value;//值域

	BSTNode(const T& value = T())
		:_left(nullptr)
		, _right(nullptr)
		, _value(value)
	{}
};

采用模板的方式實現，具體代碼見 BinarySearchTree

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

插入和刪除操作都必須先查找，查找效率代表瞭二叉搜索樹中各個操作的性能

對於有n個結點的二叉搜索樹，若每個元素查找的概率相等，則二叉搜索樹平均查找長度是結點在二叉搜索樹的深度的函數。即結點越深，比較次數越多。

但對於同一個關鍵碼的集合，如果各關鍵碼插入的次序不同，可能會得到不同的二叉搜索樹：

最優情況下：二叉搜索樹為完全二叉樹，其平均比較次數為log2N

最差情況下：二叉搜索樹退化為單支樹，其平均比較次數為N/2

因此，二叉搜索樹的時間復雜度為O(log2N)

到此這篇關於C++深入細致探究二叉搜索樹的文章就介紹到這瞭,更多相關C++二叉搜索樹內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：