二叉查找树（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 < root->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 < key) {
return search(root->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 < root->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 < node->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 < key) {
return searchNode(node->right, key);
} else {
return searchNode(node->left, key);
}
}
// 删除节点
Node* removeNode(Node* node, int key) {
if (node == nullptr) {
return nullptr;
}
if (key < node->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 < curr->val) {
curr = curr->left;
} else if (key > curr->val) {
curr = curr->right;
} else {
return;
}
}
if (prev == nullptr) {
root = new Node(key);
return;
}
if (key < prev->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 < key) {
curr = curr->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 < key) {
curr = curr->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 排序后的数组 */ vectorinorderTraversal(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等技术实现。
