二叉搜索树
2026-01-03
Intro
BST(二叉搜索树)通常有以下性质:
- 一颗二叉树
- 每个节点都存在一个数值(关键码),这个节点关键码不小于的左子树任意节点关键码,不大于右子树任意节点关键码。
Operations
Build
为了避免边界条件,一般会额外新建正无穷和负无穷两个节点。
Query
容易发现,由于二叉搜索树的性质,我们可以很方便的进行查找。
设 p=root,有以下过程:
- 若 p 关键码等于 u,则已经找到。
- 若 p 关键码大于 u,则向左找(左子树为空则不存在)。
- 若 p 关键码小于 u,则向右找(右子树为空则不存在)。
Insert
插入也很简单,与查找相似,依旧假设插入新值 val。
在查找过程中,若发现走向的 p 为空,直接建立新值 val 即可。
Find Predecessor/Successor
我们以前驱为例,令当前节点为 v,父节点为 u。
- 若 v 存在左子树,则 v 的前驱为左子树中的最大值。
- 若 v 不存在左子树,则分两种情况:
- v 是 u 的右子节点,u 即为 v 的前驱。
- v 是 u 的左子节点,则一直向右找父亲直到父亲为父节点的右儿子,这个节点即为所求。
Find Max/Min
很明显,从根节点向左向右一直走即可。
警告
尽管二叉搜索树操作期望复杂度为 O(logn),但在实际题目中只需构造一条有序序列插入便会让复杂度跌到 O(n),所以不讨论其他操作。
