二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树数据结构，对树中的每个节点都有以下性质：

1. 节点结构：每个节点包含三个属性：键（或值）、左子节点和右子节点。有些实现中，每个节点还会包含指向其父节点的指针。

2. 左子树性质：对于每个节点，其左子树的所有节点的键值都小于该节点的键值。

3. 右子树性质：对于每个节点，其右子树的所有节点的键值都大于该节点的键值。

4. 递归性质：左子树和右子树也都是二叉搜索树。

基本操作

下面是一些关键的操作及其简单描述：

1. 插入（Insert）：

   • 从根节点开始，比较要插入的值与当前节点的值。
   • 如果要插入的值小于当前节点的值，移动到左子节点；如果大于当前节点值，移动到右子节点。
   • 在找到的空位置插入新的节点。

2. 查找（Search）：

   • 从根节点开始，比较要查找的值与当前节点的值。
   • 如果值等于当前节点的值，表示查找成功。
   • 如果值小于当前节点的值，递归地查找左子树；如果大于，查找右子树。

3. 删除（Delete）：

   • 删除节点时需要考虑三种情况：
     1. 要删除的节点是叶节点：直接删除。
     2. 要删除的节点只有一个子节点：将其子节点替代被删除节点的位置。
     3. 要删除的节点有两个子节点：找到节点的中序后继（即右子树中的最小节点），用中序后继节点的值替换要删除的节点，然后删除中序后继节点。

4. 遍历（Traversal）：

   • 中序遍历（In-order Traversal）：左-根-右，得到递增顺序的节点值。
   • 先序遍历（Pre-order Traversal）：根-左-右。
   • 后序遍历（Post-order Traversal）：左-右-根。

代码示例

下面的示例代码演示了C++中如何实现一个简单的二叉搜索树，以及基本操作：

#include <iostream>  
struct TreeNode {  
    int value;  
    TreeNode *left, *right;  
    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}  
};  
class BST {  
public:  
    TreeNode* insert(TreeNode* root, int val) {  
        if (!root) return new TreeNode(val);  
        if (val < root->value)  
            root->left = insert(root->left, val);  
        else if (val > root->value)  
            root->right = insert(root->right, val);  
        return root;  
    }  
    bool search(TreeNode* root, int val) {  
        if (!root) return false;  
        if (val == root->value)  
            return true;  
        else if (val < root->value)  
            return search(root->left, val);  
        else  
            return search(root->right, val);  
    }  
    TreeNode* findMin(TreeNode* root) {  
        while (root->left) root = root->left;  
        return root;  
    }  
    TreeNode* deleteNode(TreeNode* root, int val) {  
        if (!root) return root;  
        if (val < root->value)  
            root->left = deleteNode(root->left, val);  
        else if (val > root->value)  
            root->right = deleteNode(root->right, val);  
        else {  
            if (!root->left) {  
                TreeNode* temp = root->right;  
                delete root;  
                return temp;  
            } else if (!root->right) {  
                TreeNode* temp = root->left;  
                delete root;  
                return temp;  
            }  
            TreeNode* temp = findMin(root->right);  
            root->value = temp->value;  
            root->right = deleteNode(root->right, temp->value);  
        }  
        return root;  
    }  
    void inorderTraversal(TreeNode* root) {  
        if (!root) return;  
        inorderTraversal(root->left);  
        std::cout << root->value << " ";  
        inorderTraversal(root->right);  
    }  
};  
int main() {  
    BST tree;  
    TreeNode* root = nullptr;  
    root = tree.insert(root, 50);  
    root = tree.insert(root, 30);  
    root = tree.insert(root, 70);  
    root = tree.insert(root, 20);  
    root = tree.insert(root, 40);  
    root = tree.insert(root, 60);  
    root = tree.insert(root, 80);  
    std::cout << "Inorder traversal: ";  
    tree.inorderTraversal(root);  
    std::cout << std::endl;  
    std::cout << "Search 40: " << (tree.search(root, 40) ? "Found" : "Not Found") << std::endl;  
    root = tree.deleteNode(root, 30);  
    std::cout << "Inorder traversal after deleting 30: ";  
    tree.inorderTraversal(root);  
    std::cout << std::endl;  
    return 0;  
}  

性能

1. 时间复杂度：

   • 平均情况下，查找、插入和删除的时间复杂度为O(log n)，其中n是树中的节点数。
   • 在最坏情况下（当树退化成链表），时间复杂度变为O(n)。

2. 空间复杂度：

   • 空间复杂度主要是存储树的节点，通常为O(n)。

通过自平衡二叉搜索树（例如AVL树、红黑树），可以避免最坏情况下的性能退化，确保时间复杂度保持在O(log n)。