目錄

二叉搜索樹的概念

二叉樹的實現

結點類?

函數接口總覽

實現二叉樹

二叉搜索樹的應用

K模型

KV模型

二叉搜索樹的性能分析

二叉搜索樹的概念

? ? 二叉搜索樹（Binary Search Tree，簡稱BST）是一種特殊的二叉樹，其具有以下幾個性質：

1. 每個節點至多有兩個子節點：分別稱為左子節點和右子節點。
2. 左子樹上的所有節點的值都小于根節點的值。
3. 右子樹上的所有節點的值都大于根節點的值。
4. 每個節點的左右子樹也都是二叉搜索樹。

這些性質確保了在二叉搜索樹中進行查找、插入和刪除操作具有良好的性能。具體地，這些操作在平均情況下的時間復雜度為 O(logn)，其中 n 是樹中節點的數量。不過，在最壞情況下（樹退化成鏈表），時間復雜度可能會降為 O(n)。

下面是一個二叉搜索樹的示例：

在這個二叉搜索樹中：

• 根節點是 8。
• 根節點的左子樹包含節點 3、1、6、4 和 7，這些節點的值都小于 8。
• 根節點的右子樹包含節點 10、14 和 13，這些節點的值都大于 8。

二叉樹的實現

結點類?

要實現二叉搜索樹，我們首先需要實現一個結點類：

• 結點類當中包含三個成員變量：結點值、左指針、右指針。
• 結點類當中只需實現一個構造函數即可，用于構造指定結點值的結點。

template<class K>
struct BSTreeNode
{K _key;                 // 結點值BSTreeNode<K>* _left;   // 左指針BSTreeNode<K>* _right;  // 右指針// 構造函數BSTreeNode(const K& key = K()): _key(key), _left(nullptr), _right(nullptr){}
};

函數接口總覽

//二叉搜索樹
template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public://構造函數BSTree();//拷貝構造函數BSTree(const BSTree<K>& t);//賦值運算符重載函數BSTree<K>& operator=(BSTree<K> t);//析構函數~BSTree();//插入函數bool Insert(const K& key);//刪除函數bool Erase(const K& key);//查找函數Node* Find(const K& key);//中序遍歷void InOrder();
private:Node* _root; //指向二叉搜索樹的根結點
};

? ? 為了在實現其他接口的過程中方便隨時檢查，最好實現一個二叉搜索樹的中序遍歷接口，當我們對二叉搜索樹進行一次操作后，可以調用中序遍歷接口對二叉搜索樹進行遍歷，若二叉搜索樹進行操作后的遍歷結果仍為升序，則可以初步判斷所實現的接口是正確。

//中序遍歷的子函數
void _InOrder(Node* root)
{if (root == nullptr)return;_InOrder(root->_left); //遍歷左子樹cout << root->_key << " "; //遍歷根結點_InOrder(root->_right); //遍歷右子樹
}
//中序遍歷
void InOrder()
{_InOrder(_root);cout << endl;
}

實現二叉樹

代碼如下:

// 定義二叉搜索樹模板類
template<class K>
class BSTree
{
private:BSTreeNode<K>* _root;  // 樹的根結點// 輔助函數：遞歸拷貝樹BSTreeNode<K>* CopyTree(BSTreeNode<K>* root){if (root == nullptr)return nullptr;BSTreeNode<K>* newNode = new BSTreeNode<K>(root->_key);newNode->_left = CopyTree(root->_left);newNode->_right = CopyTree(root->_right);return newNode;}// 輔助函數：遞歸銷毀樹void DestroyTree(BSTreeNode<K>* root){if (root != nullptr){DestroyTree(root->_left);   // 遞歸銷毀左子樹DestroyTree(root->_right);  // 遞歸銷毀右子樹delete root;                // 刪除當前結點}}// 輔助函數：遞歸插入BSTreeNode<K>* InsertRecursive(BSTreeNode<K>* root, const K& key){if (root == nullptr){return new BSTreeNode<K>(key);  // 找到插入位置后創建新結點}if (key < root->_key){root->_left = InsertRecursive(root->_left, key);  // 遞歸插入左子樹}else if (key > root->_key){root->_right = InsertRecursive(root->_right, key); // 遞歸插入右子樹}return root;}// 輔助函數：遞歸刪除BSTreeNode<K>* DeleteRecursive(BSTreeNode<K>* root, const K& key){if (root == nullptr)return root;if (key < root->_key){root->_left = DeleteRecursive(root->_left, key);  // 在左子樹中刪除}else if (key > root->_key){root->_right = DeleteRecursive(root->_right, key); // 在右子樹中刪除}else{if (root->_left == nullptr){BSTreeNode<K>* temp = root->_right;delete root;  // 刪除當前結點return temp;}else if (root->_right == nullptr){BSTreeNode<K>* temp = root->_left;delete root;  // 刪除當前結點return temp;}BSTreeNode<K>* temp = MinValueNode(root->_right);  // 找到右子樹中最小值結點root->_key = temp->_key;  // 用右子樹中最小值替換當前結點root->_right = DeleteRecursive(root->_right, temp->_key);  // 刪除右子樹中的最小值結點}return root;}// 輔助函數：找到最小值結點BSTreeNode<K>* MinValueNode(BSTreeNode<K>* node){BSTreeNode<K>* current = node;while (current && current->_left != nullptr){current = current->_left;  // 找到最左端的結點即為最小值結點}return current;}// 輔助函數：遞歸查找BSTreeNode<K>* SearchRecursive(BSTreeNode<K>* root, const K& key) const{if (root == nullptr || root->_key == key)return root;if (key < root->_key)return SearchRecursive(root->_left, key);  // 在左子樹中查找return SearchRecursive(root->_right, key); // 在右子樹中查找}public:// 構造函數，初始化空樹BSTree(): _root(nullptr){}// 拷貝構造函數BSTree(const BSTree<K>& other): _root(nullptr){_root = CopyTree(other._root);  // 深拷貝另一棵樹}// 賦值運算符重載函數BSTree<K>& operator=(const BSTree<K>& other){if (this != &other){DestroyTree(_root);  // 銷毀當前樹_root = CopyTree(other._root);  // 深拷貝另一棵樹}return *this;}// 析構函數，銷毀樹~BSTree(){DestroyTree(_root);  // 遞歸銷毀樹中所有結點}// 插入函數（非遞歸）void InsertIterative(const K& key){if (_root == nullptr){_root = new BSTreeNode<K>(key);  // 插入根結點return;}BSTreeNode<K>* parent = nullptr;BSTreeNode<K>* current = _root;while (current != nullptr){parent = current;if (key < current->_key){current = current->_left;  // 移動到左子結點}else if (key > current->_key){current = current->_right; // 移動到右子結點}else{return;  // 不插入重復值}}if (key < parent->_key){parent->_left = new BSTreeNode<K>(key);  // 插入左子結點}else{parent->_right = new BSTreeNode<K>(key); // 插入右子結點}}// 插入函數（遞歸）void Insert(const K& key){_root = InsertRecursive(_root, key);  // 調用遞歸插入函數}// 刪除函數（非遞歸）void DeleteIterative(const K& key){BSTreeNode<K>* parent = nullptr;BSTreeNode<K>* current = _root;while (current != nullptr && current->_key != key){parent = current;if (key < current->_key){current = current->_left;  // 移動到左子結點}else{current = current->_right; // 移動到右子結點}}if (current == nullptr)return;if (current->_left == nullptr || current->_right == nullptr){BSTreeNode<K>* newCurrent;if (current->_left == nullptr){newCurrent = current->_right;}else{newCurrent = current->_left;}if (parent == nullptr){_root = newCurrent;  // 刪除根結點}else if (current == parent->_left){parent->_left = newCurrent;  // 刪除左子結點}else{parent->_right = newCurrent; // 刪除右子結點}delete current;}else{BSTreeNode<K>* p = nullptr;BSTreeNode<K>* temp;temp = current->_right;while (temp->_left != nullptr){p = temp;temp = temp->_left;}if (p != nullptr){p->_left = temp->_right;}else{current->_right = temp->_right;}current->_key = temp->_key;delete temp;}}// 刪除函數（遞歸）void Delete(const K& key){_root = DeleteRecursive(_root, key);  // 調用遞歸刪除函數}// 查找函數（非遞歸）BSTreeNode<K>* SearchIterative(const K& key) const{BSTreeNode<K>* current = _root;while (current != nullptr && current->_key != key){if (key < current->_key){current = current->_left;  // 移動到左子結點}else{current = current->_right; // 移動到右子結點}}return current;  // 返回找到的結點或 nullptr}// 查找函數（遞歸）BSTreeNode<K>* Search(const K& key) const{return SearchRecursive(_root, key);  // 調用遞歸查找函數}
};

用法和預期效果:

1. 構造函數

   • 用法：BSTree<int> tree;
   • 預期效果：創建一個空的二叉搜索樹。

2. 拷貝構造函數

   • 用法：BSTree<int> tree2 = tree1;
   • 預期效果：深拷貝tree1，創建一個新的二叉搜索樹tree2，其結構和tree1相同。

3. 賦值運算符重載函數

   • 用法：tree2 = tree1;
   • 預期效果：深拷貝tree1到tree2，覆蓋tree2原來的內容。

4. 析構函數

   • 用法：當樹對象生命周期結束時自動調用。
   • 預期效果：遞歸銷毀樹中所有結點，釋放內存。

5. 插入函數（非遞歸）

   • 用法：tree.InsertIterative(10);
   • 預期效果：在樹中插入值為10的結點。

6. 插入函數（遞歸）

   • 用法：tree.Insert(10);
   • 預期效果：在樹中插入值為10的結點。

7. 刪除函數（非遞歸）

   • 用法：tree.DeleteIterative(10);
   • 預期效果：在樹中刪除值為10的結點。

8. 刪除函數（遞歸）

   • 用法：tree.Delete(10);
   • 預期效果：在樹中刪除值為10的結點。

9. 查找函數（非遞歸）

   • 用法：BSTreeNode<int>* node = tree.SearchIterative(10);
   • 預期效果：在樹中查找值為10的結點，返回指向該結點的指針，如果未找到則返回nullptr。

10. 查找函數（遞歸）

    • 用法：BSTreeNode<int>* node = tree.Search(10);
    • 預期效果：在樹中查找值為10的結點，返回指向該結點的指針，如果未找到則返回nullptr。

二叉搜索樹的應用

二叉搜索樹（BST）是一種重要的數據結構，廣泛應用于各種算法和系統中。以下是一些常見的應用：

1. 符號表：在編譯器中，二叉搜索樹可以用來實現符號表，用于存儲變量和函數的名稱及其屬性。
2. 字典：二叉搜索樹可以用來實現字典（例如鍵值對存儲），支持高效的插入、刪除和查找操作。
3. 優先隊列：可以使用二叉搜索樹來實現優先隊列，其中元素按照優先級排列，支持快速的插入和刪除操作。
4. 數據庫索引：在數據庫系統中，二叉搜索樹可以用作索引結構，以加速查詢操作。
5. 排序和搜索：二叉搜索樹天然地支持中序遍歷，從而可以對元素進行排序和高效搜索。

K模型

? ? K模型是基于二叉搜索樹的一種簡化形式，主要用于處理單個鍵（key）的存儲和查詢。每個結點只包含一個鍵，不涉及值（value）。?

比如：給定一個單詞，判斷該單詞是否拼寫正確。具體方式如下：

1. 以單詞集合中的每個單詞作為key，構建一棵二叉搜索樹。
2. 在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯誤。

KV模型

? ? KV模型是二叉搜索樹的擴展形式，用于處理鍵值對（key-value）的存儲和查詢。每個結點包含一個鍵和一個值。?

比如：英漢詞典就是英文與中文的對應關系，即<word, Chinese>就構成一種鍵值對。具體方式如下：

以<單詞, 中文含義>為鍵值對，構建一棵二叉搜索樹。注意：二叉搜索樹需要進行比較，鍵值對比較時只比較key。
查詢英文單詞時，只需給出英文單詞就可以快速找到與其對應的中文含義。

二叉搜索樹的性能分析

時間復雜度

1. 查找、插入和刪除

   • 最優情況：當樹是平衡的（完全平衡二叉樹），時間復雜度為O(log n)。
   • 最壞情況：當樹退化成鏈表（每個結點只有一個子結點），時間復雜度為O(n)。

2. 遍歷

   • 中序遍歷、先序遍歷、后序遍歷的時間復雜度均為O(n)，因為需要訪問每個結點。

空間復雜度

1. 空間使用

   • 空間復雜度為O(n)，n為樹中的結點數。

2. 遞歸調用棧

   • 在最壞情況下（樹退化成鏈表），遞歸調用棧的空間復雜度為O(n)。

平衡性

1. 平衡二叉樹：如AVL樹、紅黑樹等，保證在最壞情況下也能達到O(log n)的時間復雜度。
2. 普通二叉搜索樹：如果輸入數據是隨機的，樹大概率接近平衡。但如果輸入數據是有序的（或接近有序），樹可能退化為鏈表，導致性能下降。

性能優化

1. 自平衡二叉搜索樹：如AVL樹、紅黑樹、Splay樹等，通過自動調整樹的結構，保證樹的平衡，從而提升性能。
2. B樹和B+樹：特別適用于數據庫索引，支持高效的磁盤存取操作。
3. 散列：對于一些應用，哈希表（Hash Table）可以提供更快的查找、插入和刪除操作，但不適用于需要排序的場景。

總結

二叉搜索樹（BST）是一種基礎而重要的數據結構，廣泛應用于符號表、字典、優先隊列和數據庫索引等場景。K模型和KV模型分別處理集合和字典的需求。BST的性能在很大程度上取決于樹的平衡性，使用自平衡樹可以保證最壞情況下的性能。此外，對于特定應用場景，選擇合適的數據結構（如B樹或哈希表）也非常重要。