二叉搜索树 (Binary Search Tree)

lwy
算法
2025-10-29
120热度
0评论

一、什么是二叉搜索树？

二叉搜索树，也称为二叉排序树或二叉查找树，是一种特殊的二叉树。它或者是一棵空树，或者是具有下列性质的二叉树：

左子树上所有节点的值均小于它的根节点的值。
右子树上所有节点的值均大于它的根节点的值。
左、右子树也分别为二叉搜索树。

这个定义是递归的，它确保了整个树具有一个关键的属性：中序遍历二叉搜索树，可以得到一个升序排列的有序序列。

二、核心性质与优点

有序性：结构本身隐含了数据的顺序，使得查找、插入、删除等操作可以基于比较快速定位。
高效性：对于一棵左右子树相对"平衡"的二叉搜索树，搜索、插入、删除等操作的时间复杂度平均为 O(log n)，其中 n是树中节点的数量。这是因为每次操作都能排除大约一半的搜索空间。
动态性：它支持高效地动态插入和删除节点，而无需像静态数组那样需要移动大量元素

三、基本操作

3.1 树节点定义(c++为例)

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
};

3.2 插入

目标：将一个新值插入树中，并保持二叉搜索树的性质。

步骤：

树为空，则创建一个新节点作为根节点。
如果新值小于当前节点的值，递归地插入到左子树。
如果新值大于当前节点的值，递归地插入到右子树。
关键：如果新值等于当前节点的值，根据具体实现决定（通常不允许重复值，或可以插入到左/右子树）。这里我们假设不允许重复，则不插入或进行其他处理（或用计数来计算）。

代码：

// 插入
TreeNode* InsertBSTNode(TreeNode* root, int value){
    if (root == nullptr)
        return new TreeNode(value);

    if (root -> value < value)
        root -> right = InsertBSTNode(root -> right, value);
    else
        root -> left = InsertBSTNode(root -> left, value);

    return root;
}

3.3 查找

目标：在树中查找一个数是否存在

步骤：

从根节点开始比较，如果根节点不存在或根节点的值等于目标值则返回
如果目标值大于根节点的值，则递归地向右节点查找
如果目标值小于根节点的值，则递归的向左节点查找

代码：

TreeNode* SearchBSTNode(TreeNode* root, int value){
    if (root == nullptr || root -> value == value)
        return root;

    if (value > root -> value) return SearchBSTNode(root -> right, value);
    else return SearchBSTNode(root -> left, value);
}

3.4 删除

目标：在树中查找一个数，并将其删除

步骤：

找到要删除的节点，并删除
情况一：该节点为叶节点，直接删除该节点即可
情况二：该节点有只有一个子节点，则将其对应的子节点代替即可

情况三：该节点有两个子节点（最复杂情况）

找到对应的该节点中序遍历最小（大）的值
让最小（大）值替换该值
然后递归删除那个最值节点

代码：

// 查找最小值
TreeNode* FindMinNode(TreeNode root){
   while (root -> left != nullptr){
       root = root -> left; 
   }
   return root;
}

// 删除节点
TreeNode* DeleteBSTNode(TreeNode* root, int value) {
   if (root == nullptr) return root;
   if (value < root -> value) root -> left = DeleteBSTNode(root -> left, value);
   else if (value > root -> value) root -> right = DeleteBSTNode(root -> right, value);
   else {
       if (root -> left == nullptr) {
           TreeNode* temp = root -> left;
           root -> value = temp -> value;
           delete temp;
           return root;
       }
       else if (root -> right == nullptr) {
           TreeNode* temp = root -> right;
           root -> value = temp -> value;
           delete temp;
           return root;
       }

       TreeNode* minNode = FindMinNode(root);
       root -> value = minNode -> value;
       root -> right = DeleteBSTNode(root -> right, mindNode -> value);
   }
   return root;
}

3.5 示例代码

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
};

class BST{

private:
    TreeNode* root;

    // 插入
    TreeNode* InsertBSTNode(TreeNode* root, int value){
        if (root == nullptr)
            return new TreeNode(value);

        if (root -> value < value)
            root -> right = InsertBSTNode(root -> right, value);
        else
            root -> left = InsertBSTNode(root -> left, value);

        return root;
    }

    // 查找 
    TreeNode* SearchBSTNode(TreeNode* root, int target){
        if (root == nullptr || root -> value == target)
            return root;

        if (root -> value < target) SearchBSTNode(root -> right, target);
        else SearchBSTNode(root -> left, target); 
        // return root;
    }

    // 删除 
    TreeNode* DeleteBSTNode(TreeNode* root, int key){
        if (root == nullptr)
            return nullptr;

        if (key < root -> value)
            root -> left = DeleteBSTNode(root -> left, key);
        else if (key > root -> value)
            root -> right = DeleteBSTNode(root -> right, key);
        else{
            // 如果左子树为空, 替换右边节点 
            if (root -> left == nullptr){
                TreeNode* temp = root -> right;
                delete root;
                return temp;
            }
            // 如果右子树为空，直接替换左边节点 
            else if (root -> right == nullptr){
                TreeNode* temp = root -> left;
                delete root;
                return temp;
            }

            // 找到最小的节点 
            TreeNode* minNode = FindMinBSTNode(root -> right);
            // 替换 
            root -> value = minNode -> value;
            // 删除之前最小的节点 
            root -> right = DeleteBSTNode(root -> right, minNode -> value);
        }
        return root;
    }

    // 查找最小数值 
    TreeNode* FindMinBSTNode(TreeNode* root){
        while (root -> left != nullptr){
            root = root -> left;
        }
        return root;
    }

    // 中序遍历 
    void InorderRecursive(TreeNode* root, vector<int> &res) {
        if (root == nullptr) return;

        InorderRecursive(root -> left, res);
        res.push_back(root -> value);
        InorderRecursive(root -> right, res);
    }

    // 清空树
    void clear() {
        clearRecursive(root);
        root = nullptr;
    }

    void clearRecursive(TreeNode* node) {
        if (node == nullptr) return;
        clearRecursive(node -> left);
        clearRecursive(node -> right);
        delete node;
    }

public:
    // 构造函数 
    BST(): root(nullptr) {}

    ~BST(){
        clear(); 
    }

    // 插入操作 
    void Insert(int value){
        root = InsertBSTNode(root, value);
    }

    // 查询操作 
    bool Search(int value){
        return SearchBSTNode(root, value) != nullptr;
    }

    // 移除操作 
    void Remove(int value){
        DeleteBSTNode(root, value);
    } 

    // 中序遍历（升序）
    vector<int> Inorder() {
        vector<int> result;
        InorderRecursive(root, result);
        return result;
    }
}; 
int main() {
    BST bst;

    cout << "=== 二叉搜索树测试 ===" << endl;

    // 插入测试
    vector<int> values = {50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45};

    for (int val : values) {
        cout << "插入数值: ";
        cout << val << " ";
        bst.Insert(val);

        // 遍历测试
        cout << "中序遍历 (升序): ";
        vector<int> inorder = bst.Inorder();
            for (int val : inorder) {
                cout << val << " ";
        } 
        cout << endl;
    }

    // 查找测试 
    vector<int> findValues = {80, 66, 20, 30};
    for (int val : findValues){
        cout << "搜索数值: ";
        cout << val << " ";

        bool isFind = bst.Search(val);
        cout << (isFind ? "查找到" : "未找到") << endl;
    }

    // 删除测试 
    vector<int> removeValues = {40, 60, 80, 66, 35, 45};

    for (int val : removeValues) {
        cout << "删除数值: ";
        cout << val << " ";
        bst.Remove(val);

        // 遍历测试
        cout << "中序遍历 (升序): ";
        vector<int> inorder = bst.Inorder();
            for (int val : inorder) {
                cout << val << " ";
        } 
        cout << endl;
    }
    return 0;
}

四、二叉搜索树的缺陷：不平衡问题

二叉搜索树的性能严重依赖于树的高度。如果树是平衡的（例如 AVL 树、红黑树），高度约为 log₂n，操作效率很高。

但是，如果按照特定顺序插入节点（例如依次插入 1, 2, 3, 4, 5），树会退化成一条链表，高度变为 n。此时，所有操作的时间复杂度都退化为 O(n)，效率极低。

解决方案：使用自平衡二叉搜索树，如AVL 树、红黑树等。它们在插入和删除时会通过旋转等操作自动调整树的结构，保持树的平衡。

五、总结

特性/操作	描述	平均/最好时间复杂度	最坏时间复杂度（退化成链表）
查找	根据值的大小在左/右子树中搜索	O(log n)	O(n)
插入	在适当位置创建新叶子节点	O(log n)	O(n)
删除	分三种情况处理	O(log n)	O(n)
中序遍历	按升序输出所有节点	O(n)	O(n)
空间复杂度		O(n)	O(n)

二叉搜索树是理解更高级树结构（如 AVL 树、红黑树、B 树）的基础。

二叉搜索树 (Binary Search Tree)

一、什么是二叉搜索树？

二、 核心性质与优点

三、基本操作

3.1 树节点定义(c++为例)

3.2 插入

3.3 查找

3.4 删除

3.5 示例代码

四、 二叉搜索树的缺陷：不平衡问题

五、 总结

二、核心性质与优点

四、二叉搜索树的缺陷：不平衡问题

五、总结