C++深入細緻探究二元搜尋樹

2022-05-24 14:01:52

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