二叉搜索树(BST)

定义

二叉搜索树（Binary Search Tree）是一种有序二叉树：对任意节点，其左子树所有节点值都小于它，右子树所有节点值都大于它。因此中序遍历可得到升序序列。

原理

查找时从根开始，比目标小则走右、比目标大则走左，直到找到或到达空节点。插入沿同样路径找到空位挂上新节点。删除分三种情况：叶子直接删除；只有一个子节点用其子节点顶替；有两个子节点则用中序后继（右子树最小值）替换再删除后继。性能取决于树高，最坏会退化成链表。

复杂度

• 查找/插入/删除（平均）：O(log n)
• 查找/插入/删除（最坏，退化）：O(n)
• 空间复杂度：O(n)

应用场景

• 有序集合与映射
• 范围查询与排名查询
• 作为 AVL 树、红黑树等平衡树的基础模型