二叉搜索树

模板:Note

二叉搜索树简介[编辑 | 编辑源代码]

二叉搜索树（Binary Search Tree, BST）是一种基于二叉树的数据结构，满足以下性质：

任意节点的左子树仅包含小于该节点键值的元素
任意节点的右子树仅包含大于该节点键值的元素
左右子树也必须各自是二叉搜索树

这种结构使得查找、插入、删除操作的平均时间复杂度为 $O (\log n)$ ，最坏情况下（树退化为链表）为 $O (n)$ 。

基本操作[编辑 | 编辑源代码]

查找[编辑 | 编辑源代码]

从根节点开始递归比较：

若目标值等于当前节点值 → 找到
若目标值较小 → 进入左子树
若目标值较大 → 进入右子树

def search(root, key):
    if root is None or root.val == key:
        return root
    if key < root.val:
        return search(root.left, key)
    return search(root.right, key)

插入[编辑 | 编辑源代码]

遵循查找逻辑找到合适位置插入新节点，保持BST性质：

TreeNode insert(TreeNode root, int key) {
    if (root == null) return new TreeNode(key);
    if (key < root.val) 
        root.left = insert(root.left, key);
    else if (key > root.val)
        root.right = insert(root.right, key);
    return root;
}

删除[编辑 | 编辑源代码]

分三种情况处理：

无子节点：直接删除
有一个子节点：用子节点替代
有两个子节点：用右子树的最小节点替代

TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return nullptr;
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        if (!root->left) return root->right;
        if (!root->right) return root->left;
        TreeNode* minNode = findMin(root->right);
        root->val = minNode->val;
        root->right = deleteNode(root->right, minNode->val);
    }
    return root;
}