1、二叉搜索樹的概念

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

??①若根節(jié)點的左子樹不為空，則左子樹上的所有節(jié)點的值域都小于根節(jié)點的值

??②若根節(jié)點的右子樹不為空，則右子樹上的所有節(jié)點的值域都大于根節(jié)點的值

??③根節(jié)點的左右子樹分別也是一顆二叉搜索樹

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

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

2、二叉搜索樹的操作

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

二叉搜索樹的查找

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

例如：查找下圖中的紅色方框中的節(jié)點

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

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

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

??①6與根節(jié)點6比較，6 == 6,此時查找成功！

總結基本步驟：

若根節(jié)點不為空：

??如果根節(jié)點的key == 查找的key----->返回true

??如果根節(jié)點的key > 查找的key----->轉到根節(jié)點的右子樹查找

??如果根節(jié)點的key < 查找的key----->轉到根節(jié)點的左子樹查找

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

二叉搜索樹的插入

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

1、樹為空，直接插入

如下圖所示：

2、樹不空

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

②插入新的節(jié)點

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

第一步，查找插入位置：

?注意：要標記當前訪問的節(jié)點的雙親，否則，就算找到了插入位置，由于無法訪問其雙親，也是無法進行插入的。這里使用parent來標記當前訪問節(jié)點的雙親節(jié)點。

具體過程如下圖：

第二步，插入新節(jié)點

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

if(node->value < parent->value)//新節(jié)點作為parent的左孩子
{
	parent->left = node;
}
else//新節(jié)點作為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;
	}
}

上述代碼執(zhí)行完畢后，delNode有兩種情況，delNode == nullptr || delNode!=nullptr

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

2、刪除該節(jié)點

Ⅰ、nullptr == delNode

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

Ⅱ、delNode != nullptr;

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

刪除時，對于待刪除結點要根據(jù)其孩子節(jié)點分情況討論：

??①待刪除結點是葉子結點

??②待刪除結點只有左孩子

??③待刪除結點只有有孩子

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

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

情況一：待刪除結點時葉子節(jié)點

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

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

在此前提下，有兩類情形

1、delNode的雙親存在 ?

2、delNode的雙親不存在

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

1、delNode的雙親存在

刪除過程見下圖：

2、delNode的雙親不存在

與上述僅存在葉子節(jié)點時存在的問題一樣，需要在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;

我們結合刪除節(jié)點是葉子節(jié)點 && 刪除節(jié)點僅有左子樹兩種情況來看，發(fā)現(xiàn)這兩種情況可以進行合并。合并后的代碼如下圖：

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

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

1、delNode的雙親存在 ?

2、delNode的雙親不存在

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

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

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

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

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

3、將替代節(jié)點刪除掉

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

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

具體過程見下圖：

ok,下面給出實現(xiàn)的代碼：

3、二叉搜索樹的實現(xiàn)

數(shù)據(jù)結構：

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

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

采用模板的方式實現(xiàn)，具體代碼見 BinarySearchTree

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

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

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

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

最優(yōu)情況下：二叉搜索樹為完全二叉樹，其平均比較次數(shù)為log2N

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

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