深入解析二叉查找树

二叉查找树（Binary Search Tree，简称BST）是一种常用的数据结构，由于其高效的查找和删除操作，在计算机科学领域得到了广泛应用。它是一棵二叉树，其每个节点都含有一条关键字，且节点的左子树所有节点的关键字小于该节点，右子树所有节点的关键字大于该节点。

一、BST的基本操作

BST的基本操作包括插入、查找和删除操作。

1. 插入操作

/**
 * 插入操作
 * @param root 根节点
 * @param key 要插入的节点值
 * @return 插入后的根节点
 */
Node* insert(Node* root, int key) {
    if (root == nullptr) {
        return new Node(key);
    }
    if (key val) {
        root->left = insert(root->left, key);
    } else if (key > root->val) {
        root->right = insert(root->right, key);
    }
    return root;
}

在插入一个节点时，从根节点开始，比较要插入的节点值与该节点值的大小，若小于该节点则递归到左子树插入，否则递归到右子树插入，如果为空则新建该节点。

2. 查找操作

/**
 * 查找操作
 * @param root 根节点
 * @param key 要查找的节点值
 * @return 是否存在该节点
 */
bool search(Node* root, int key) {
    if (root == nullptr) {
        return false;
    }
    if (root->val == key) {
        return true;
    } else if (root->val right, key);
    } else {
        return search(root->left, key);
    }
}

在查找一个节点时，从根节点开始，比较要查找的节点值与该节点值的大小，若小于该节点则递归到左子树查找，否则递归到右子树查找，如果为空则该节点不存在。

3. 删除操作

/**
 * 查找以node为根节点的最小节点
 * @param node 根节点
 * @return 最小节点
 */
Node* getMinNode(Node* node) {
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}

/**
 * 删除节点操作
 * @param root 根节点
 * @param key 要删除的节点值
 * @return 删除后的根节点
 */
Node* remove(Node* root, int key) {
    if (root == nullptr) {
        return nullptr;
    }
    if (key val) {
        root->left = remove(root->left, key);
    } else if (key > root->val) {
        root->right = remove(root->right, key);
    } else {
        if (root->left == nullptr) {
            Node* rightNode = root->right;
            delete root;
            return rightNode;
        }
        if (root->right == nullptr) {
            Node* leftNode = root->left;
            delete root;
            return leftNode;
        }
        Node* successor = getMinNode(root->right);
        successor->right = remove(root->right, successor->val);
        successor->left = root->left;
        delete root;
        return successor;
    }
    return root;
}

在删除一个节点时，需要考虑其左子树或右子树为空、左右子树都存在的情况，其中左右子树都存在时，需要找到该节点右子树的最小值作为该节点的后继，将其删除，再用该后继替换该节点。

二、BST的实现

1. 递归实现

最常见的BST实现方式是递归实现，代码比较简单易懂：

class BST {
private:
    struct Node {
        int val;
        Node* left;
        Node* right;
        Node(int value) : val(value), left(nullptr), right(nullptr) {}
    };
    Node* root;
    // 插入节点
    Node* insertNode(Node* node, int key) {
        if (node == nullptr) {
            return new Node(key);
        }
        if (key val) {
            node->left = insertNode(node->left, key);
        } else if (key > node->val) {
            node->right = insertNode(node->right, key);
        }
        return node;
    }
    // 查找节点
    bool searchNode(Node* node, int key) {
        if (node == nullptr) {
            return false;
        }
        if (node->val == key) {
            return true;
        } else if (node->val right, key);
        } else {
            return searchNode(node->left, key);
        }
    }
    // 删除节点
    Node* removeNode(Node* node, int key) {
        if (node == nullptr) {
            return nullptr;
        }
        if (key val) {
            node->left = removeNode(node->left, key);
        } else if (key > node->val) {
            node->right = removeNode(node->right, key);
        } else {
            if (node->left == nullptr) {
                Node* rightNode = node->right;
                delete node;
                return rightNode;
            }
            if (node->right == nullptr) {
                Node* leftNode = node->left;
                delete node;
                return leftNode;
            }
            Node* successor = getMinNode(node->right);
            successor->right = removeNode(node->right, successor->val);
            successor->left = node->left;
            delete node;
            return successor;
        }
        return node;
    }
    // 查找最小节点
    Node* getMinNode(Node* node) {
        while (node->left != nullptr) {
            node = node->left;
        }
        return node;
    }
public:
    BST() : root(nullptr) {}
    // 插入节点
    void insert(int key) {
        root = insertNode(root, key);
    }
    // 查找节点
    bool search(int key) {
        return searchNode(root, key);
    }
    // 删除节点
    void remove(int key) {
        root = removeNode(root, key);
    }
};

2. 非递归实现

递归实现虽然简单，但是过多的函数调用会导致性能下降。因此，BST也可以用非递归方式实现。

class BST {
private:
    struct Node {
        int val;
        Node* left;
        Node* right;
        Node(int value) : val(value), left(nullptr), right(nullptr) {}
    };
    Node* root;
public:
    BST() : root(nullptr) {}
    // 插入节点
    void insert(int key) {
        Node* curr = root, *prev = nullptr;
        while (curr != nullptr) {
            prev = curr;
            if (key val) {
                curr = curr->left;
            } else if (key > curr->val) {
                curr = curr->right;
            } else {
                return;
            }
        }
        if (prev == nullptr) {
            root = new Node(key);
            return;
        }
        if (key val) {
            prev->left = new Node(key);
        } else {
            prev->right = new Node(key);
        }
    }
    // 查找节点
    bool search(int key) {
        Node* curr = root;
        while (curr != nullptr) {
            if (curr->val == key) {
                return true;
            } else if (curr->val right;
            } else {
                curr = curr->left;
            }
        }
        return false;
    }
    // 删除节点
    void remove(int key) {
        Node* curr = root, *prev = nullptr;
        while (curr != nullptr && curr->val != key) {
            prev = curr;
            if (curr->val right;
            } else {
                curr = curr->left;
            }
        }
        if (curr == nullptr) {
            return;
        }
        if (curr->left == nullptr) {
            if (prev == nullptr) {
                root = curr->right;
            } else if (prev->left == curr) {
                prev->left = curr->right;
            } else {
                prev->right = curr->right;
            }
            delete curr;
        } else if (curr->right == nullptr) {
            if (prev == nullptr) {
                root = curr->left;
            } else if (prev->left == curr) {
                prev->left = curr->left;
            } else {
                prev->right = curr->left;
            }
            delete curr;
        } else {
            Node* prev2 = curr, *curr2 = curr->right;
            while (curr2->left != nullptr) {
                prev2 = curr2;
                curr2 = curr2->left;
            }
            if (prev2->left == curr2) {
                prev2->left = curr2->right;
            } else {
                prev2->right = curr2->right;
            }
            curr->val = curr2->val;
            delete curr2;
        }
    }
};

三、BST的应用

1. 排序

BST的中序遍历得到的元素就是排好序的。

/**
 * BST中序遍历
 * @param root 根节点
 * @return 排序后的数组
 */
vector inorderTraversal(Node* root) {
    vector res;
    inorder(root, res);
    return res;
}
void inorder(Node* root, vector& res) {
    if (root == nullptr) {
        return;
    }
    inorder(root->left, res);
    res.push_back(root->val);
    inorder(root->right, res);
}

2. 前缀匹配

给定一个字符串集合，使用BST可以实现前缀匹配功能，即查找所有以某个字符串为前缀的字符串。

class Trie {
private:
    struct TrieNode {
        bool isEnd;
        unordered_map children;
        TrieNode() : isEnd(false) {}
    };
    TrieNode* root;
    void dfs(TrieNode* node, string& word, vector& res) {
        if (node->isEnd) {
            res.push_back(word);
        }
        for (auto& p : node->children) {
            word.push_back(p.first);
            dfs(p.second, word, res);
            word.pop_back();
        }
    }
public:
    Trie() : root(new TrieNode()) {}
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children.count(c)) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->isEnd = true;
    }
    vector searchByPrefix(string prefix) {
        vector res;
        TrieNode* node = root;
        for (char c : prefix) {
            if (!node->children.count(c)) {
                return res;
            }
            node = node->children[c];
        }
        dfs(node, prefix, res);
        return res;
    }
};

在Trie树中，用BST作为每个节点的子节点存储字符，查找所有以某个字符串为前缀的字符串时，只需要查找该前缀的所有子节点并进行DFS即可。

四、BST的优化与扩展

1. 平衡二叉树

由于BST可能退化成链表，因此需要保证其平衡，即左右子树高度差不超过1。常见的平衡二叉树包括AVL树、红黑树等。

2. B树和B+树

与平衡二叉树类似，B树和B+树是一种使用平衡的数据结构，用于存储大量的数据，通常被应用于文件系统、数据库系统等领域。

3. 可持久化BST

可持久化BST是一种可以支持历史版本查询的数据结构，每次修改节点时都会创建一个新版本。常使用函数式编程或复制-on-write等技术实现。

五、总结

原创文章，作者：GJKEC，如若转载，请注明出处：https://www.506064.com/n/372364.html