BST
二叉搜索树
树与堆核心时间 平均 O(log n)空间 O(n)
左子树都更小、右子树都更大。中序遍历即有序序列。平衡时查找像二分。
动画
插入 8：小于当前走左，大于走右。
1 / 7
- 当前
讲解
有序动态集合：查找、前驱后继、范围查询。AVL / 红黑树是它的平衡形态。
- 01插入：从根比较，小走左、大走右，落到空位挂上。
- 02查找同理，命中或走到空。
- 03删除分三种：叶子直接摘；单子用孩子顶替；双子取中序后继。
- 04不平衡会退化成链表，实际工程用红黑树。
易错点
- 有序插入会得到一条斜链，退化为 O(n)。
- 递归插入别忘了把子树接回去。
代码
function insert(node, v) {
if (!node) return { v, l: null, r: null };
if (v < node.v) node.l = insert(node.l, v);
else if (v > node.v) node.r = insert(node.r, v);
return node;
}
function search(node, v) {
if (!node || node.v === v) return node;
return v < node.v ? search(node.l, v) : search(node.r, v);
}