树与堆
引入
词汇
| English | 释义 | 拼音 |
|---|---|---|
| binary search tree/ˈbaɪnəri sɜːtʃ triː/ | 二叉搜索树 | èr chā sōu suǒ shù |
| heap/hiːp/ | 堆 | duī |
| min-heap | 小顶堆 | xiǎo dǐng duī |
顺序不变量，完全形状
- 二叉搜索树 binary search tree 保证左子树小于节点小于右子树：插入 $50, 30, 70, 20, 40, 60, 80$ 得到高 $2$ 的满树，中序遍历读出 $20, 30, 40, 50, 60, 70, 80$——构造即有序。
- 堆 heap 是存进数组的完全树：索引 $i$ 的孩子在 $2i+1$ 和 $2i+2$。小顶堆 min-heap 保证每个父节点不超过其孩子，最小值就在索引 $0$。
{exercise:uni-cs0504-shapes}
练习
数组堆中下标 i 的孩子位于——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
完全形状定死映射：左孩子 2i+1、右孩子 2i+2。
高度即代价
- 高 $h$ 的满树有 $2^{h+1} - 1$ 个节点：$h=2$ 时 $7$ 个，$h=3$ 时 $15$，$h=4$ 时 $31$——平衡的 $n$ 只需高 $\lfloor \log_2 n \rfloor$，每条根到叶的路径都按它付费。
- 斜树毁约：顺序插入 $1, 2, 3, 4$ 得到高 $3 = n-1$ 的链，查找 $O(n)$——AVL、红黑树靠旋转保持对数高度的理由。
{exercise:uni-cs0504-height}
练习
高 3 的满树有——个节点。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
2 的 h+1 次方减一：16 减 1 等于 15。
遍历与上筛
- BST 查 $40$：比 $50$（向左）、比 $30$（向右）、$40$——$7$ 个节点 $3$ 次比较。插入 $35$ 挂在 $40$ 左侧；中序仍然有序。
- 依次插入 $5, 3, 8, 1$ 建小顶堆：$3$ 上筛越过 $5$；$1$ 越过 $5$ 再越过 $3$；数组读作 $[1, 3, 8, 5]$——处处父不超过子。
heapq.heapify从中点向下筛，整体 $O(n)$ 建堆。
{exercise:uni-cs0504-sift}
练习
向空小顶堆依次插入 5、3、8、1 后数组为——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
3 越过 5；1 越过 5 再越过 3——父恒不超过子。