二叉搜索树（Binary Search Tree, BST）
定义
二叉搜索树（BST）是一种特殊的二叉树，满足以下性质：
左子树所有节点值 < 当前节点值 < 右子树所有节点值（左小右大）
核心性质
1. 中序遍历有序性
这是 BST 最重要的性质：对 BST 进行中序遍历，得到的结果是有序的（升序）。
// BST 的中序遍历结果是有序的
void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
// 访问节点时，值按升序排列
System.out.println(root.val);
inorder(root.right);
}
2. 高效查找
由于左小右大的特性，在 BST 中查找某个值的时间复杂度为 O(h)，其中 h 是树的高度。
- 平衡 BST：h = O(log N)，查找效率 O(log N)
- 最坏情况（退化成链表）：h = O(N)，查找效率 O(N)
3. 范围查询优势
BST 结构天然支持范围查询（如查找某个区间内的所有值），比哈希表更高效。
与其他二叉树的关系
| 类型 | 与 BST 的关系 |
|---|---|
| 普通二叉树 | BST 是普通二叉树的特例，增加了有序性约束 |
| 高度平衡二叉树 | 平衡 BST（如 AVL 树、红黑树）保持树高 O(log N)，确保查找效率 |
| 自平衡二叉树 | 红黑树是典型的自平衡 BST，增删节点时自动调整结构 |
常见操作
- 查找：从根节点开始，比较目标值与当前节点值，决定往左还是往右
- 插入：找到合适位置插入新节点，保持 BST 性质
- 删除：较复杂，需考虑三种情况（无子节点/一个子节点/两个子节点）
应用场景
- 动态数据结构，需要频繁插入、删除、查找
- 需要有序遍历的场景
- 范围查询（如查找 [a, b] 区间内的所有元素）
- 实现有序映射（如 Java 的 TreeMap）