1 二叉搜索樹的概念

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

1 若它的左?樹不為空，則左?樹上所有結點的值都?于等于根結點的值

2 若它的右?樹不為空，則右?樹上所有結點的值都?于等于根結點的值

3 它的左右?樹也分別為?叉搜索樹

4 ?叉搜索樹中可以?持插?相等的值，也可以不?持插?相等的值，具體看使?場景定義

2 二叉搜索樹的性能分析?

最優情況下，?叉搜索樹為完全?叉樹(或者接近完全?叉樹)，其?度為： logN

最差情況下，?叉搜索樹退化為單?樹(或者類似單?)，其?度為： N

所以綜合???叉搜索樹增刪查改時間復雜度為： O(N)

那么這樣的效率顯然是?法滿?我們需求的，我們后續課程需要繼續講解?叉搜索樹的變形，平衡?叉搜索樹AVL樹和紅?樹，才能適?于我們在內存中存儲和搜索數據。

另外需要說明的是，?分查找也可以實現 O(logN) 2 級別的查找效率，但是?分查找有兩?缺陷：

1. 需要存儲在?持下標隨機訪問的結構中，并且有序。

2. 插?和刪除數據效率很低，因為存儲在下標隨機訪問的結構中，插?和刪除數據?般需要挪動數據。

這?也就體現出了平衡?叉搜索樹的價值

?3 二叉搜索樹的插入

?插?的具體過程如下：

1. 樹為空，則直接新增結點，賦值給root指針

2. 樹不空，按?叉搜索樹性質，插?值?當前結點?往右?，插?值?當前結點?往左?，找到空位 置，插?新結點。

3. 如果?持插?相等的值，插?值跟當前結點相等的值可以往右?，也可以往左?，找到空位置，插?新結點。（要注意的是要保持邏輯?致性，插?相等的值不要?會往右?，?會往左?）

????????代碼實現：

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 (key > parent->_key){parent->_right = cur;}else{parent->_left = cur;}return true;
}

4 二叉搜索樹的查找?

1.從根開始?較，查找x，x?根的值?則往右邊?查找，x?根值?則往左邊?查找。

2. 最多查找?度次，?到到空，還沒找到，這個值不存在。

3. 如果不?持插?相等的值，找到x即可返回

4. 如果?持插?相等的值，意味著有多個x存在，?般要求查找中序的第?個x。如下圖，查找3，要 找到1的右孩?的那個3返回

????????代碼實現：

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

5 二叉搜索樹的刪除?

??先查找元素是否在?叉搜索樹中，如果不存在，則返回false。

如果查找元素存在則分以下四種情況分別處理：（假設要刪除的結點為N）

1. 要刪除結點N左右孩?均為空

2. 要刪除的結點N左孩?位空，右孩?結點不為空

3. 要刪除的結點N右孩?位空，左孩?結點不為空

4. 要刪除的結點N左右孩?結點均不為空

對應以上四種情況的解決?案：

1. 把N結點的?親對應孩?指針指向空，直接刪除N結點（情況1可以當成2或者3處理，效果是?樣 的）

2. 把N結點的?親對應孩?指針指向N的右孩?，直接刪除N結點

3. 把N結點的?親對應孩?指針指向N的左孩?，直接刪除N結點

4. ?法直接刪除N結點，因為N的兩個孩??處安放，只能?替換法刪除。找N左?樹的值最?結點 R(最右結點)或者N右?樹的值最?結點R(最左結點)替代N，因為這兩個結點中任意?個，放到N的 位置，都滿??叉搜索樹的規則。替代N的意思就是N和R的兩個結點的值交換，轉?變成刪除R結 點，R結點符合情況2或情況3，可以直接刪除。

代碼實現：

bool Erase(const K& key)
{Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{//準備刪除if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){if (cur == _root){_root = _root->_left;}else{if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}swap(cur->_key, replace->_key);if (replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_right = replace->_right;delete replace;}return true;}}return false;
}

?二叉樹的遍歷

那么上面寫完了我們總得是要測試一下的，那么為了輸出的結果好看，二叉搜索樹的中序遍歷就可以將輸出的結果按照升序的樣式打印出來。

????????代碼實現：?

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

在這里是因為，在外部調用InOrder的話，root并不作為public對象對外可以進行訪問的，因此單純的寫一個InOrder函數達不到打印的效果，但是可以在創建一個無參的InOrder來進行調用，這樣內部的函數進行調用就不會出現那種情況了，那么就可以達到我們想要的效果了。

?到這里關于二叉搜索樹的介紹就到這里了，感謝你的觀看！