二叉搜索树

基本概念

二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，它满足：对于任意节点，其左子树中所有节点的值都小于该节点的值，右子树中所有节点的值都大于该节点的值。左右子树也分别为二叉搜索树。中序遍历 BST 可以得到一个递增的有序序列。

数据结构的三要素

  • 逻辑结构
    • 树形结构，但节点之间具有“左小右大”的约束关系，本质上是一种动态有序表。
  • 存储结构
    • 链式存储：每个节点包含数据域、左孩子指针、右孩子指针。也可使用数组顺序存储（需按完全二叉树编号，但会浪费空间）。
  • 数据的运算
    • 查找（search）、插入（insert）、删除（delete）、求最大值/最小值、求前驱/后继、范围查询（range query）等。

费曼理解

想象你有一本按字母顺序排列的英语词典。你打开中间一页，看到单词 “M”。如果要查 “Apple”，你会往左翻（因为 A < M）；如果要查 “Zoo”，你会往右翻（Z > M）。每次翻页后，你只关注剩下的一半区域，就像二分查找。二叉搜索树就是这种思想在树结构上的体现：每个节点就像一个“分界点”，左子树是它左边那一半，右子树是右边那一半。插入新单词时，同样通过比较大小决定往左还是往右，直到找到空位置放进去。

内部实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = self.insertIntoBST(root.left, val)
    elif val > root.val:
        root.right = self.insertIntoBST(root.right, val)
    return root     
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    if  not root or root.val==val:
        return root
    if root.val>val:
        return self.searchBST(root.left,val)
    else :
        return self.searchBST(root.right,val)

复杂度分析：

操作 平均时间复杂度 最坏时间复杂度（链状树） 空间复杂度（递归栈）
查找 O(log n) O(n) O(log n) / O(n)
插入 O(log n) O(n) O(log n) / O(n)
删除 O(log n) O(n) O(log n) / O(n)
中序遍历 O(n) O(n) O(log n) / O(n)

优化方法：使用平衡二叉搜索树（如 AVL 树、红黑树）可将最坏情况时间复杂度降至 O(log n)。

应用场景：

  • 经典问题：符号表（Symbol Table）、动态集合的快速查找与有序遍历。例如 C++ 的 std::set / std::map、Java 的 TreeSet / TreeMap 通常基于红黑树（平衡 BST）实现。
  • 数据库索引：虽然大型数据库多用 B 树 / B+ 树（多路平衡搜索树），但其核心思想来源于 BST，通过降低树高来减少磁盘 I/O。
  • 文件系统：某些文件系统的目录项管理使用树形结构（如 ext4 的 HTree 基于哈希和树）。
  • 与经典结构对比：
    • LRU 缓存（HashMap + DoublyLinkedList）解决的是访问顺序淘汰，而 BST 解决的是有序存储与对数时间查找，两者侧重点不同。
    • Redis 有序集合（跳表）与平衡 BST 功能相似（有序、对数时间），但跳表实现更简单且支持范围查询，Redis 因此选用跳表而非红黑树。
  • 微机原理相关：递归实现查找/插入时，每层递归都会在栈上分配帧（保存参数、局部变量、返回地址）。当树严重不平衡（退化为链表）时，递归深度达到 O(n)，可能导致栈溢出。理解内存布局有助于预估递归调用对栈空间的需求，并在必要时改为迭代实现。

相关

1
2
3
4
TABLE without id file.link AS "题目名称", 数据结构,date
FROM #LeetCode 
WHERE contains(数据结构, "二叉搜索树")
SORT file.mtime DESC