数据结构入门：时间复杂度、数组、二分、哈希、链表、树

这是数据结构课的第一天。核心只有一句话：数据结构解决的是"数据量大了以后，操作还快不快"的问题。而这节课给出的衡量工具，叫时间复杂度。

这一篇覆盖的内容比较多，按顺序是：

1. 为什么需要数据结构

2. 时间复杂度到底在衡量什么

3. 数组：为什么下标访问是 O(1)

4. 二分查找：从 O(n) 到 O(log n)

5. 哈希表：用"算位置"绕过排序

6. 链表：插入快、查找慢的另一种取舍

7. 树：从链表继续演进

8. 学习路线和刷题建议

一、先明确：数据结构到底解决什么问题

1.1 一个生活类比

图书馆管理和计算机文件管理其实是一个道理。

当书或文件太多时，分类存储是提高效率的关键：

• 图书馆把文学类放 1 楼、理工类放 2 楼；

• 计算机文件按类型分区存放（C 盘装系统、D 盘存文档）。

无序堆砌会导致查找困难，必须建立分类体系。就像在图书馆找书要先看导航图，用电脑找文件也要靠清晰的目录结构，这样才能避免"大海捞针"式的低效搜索。

一句话：分类即效率。

1.2 数据结构的作用

对数据进行整理，以提高操作（如查找、修改）的效率。

注意关键词是"操作效率"，不是"存储省空间"。数据结构首先是为操作服务的。

1.3 什么时候需要考虑数据结构

老师给了一个很重要的边界：

数据结构主要解决大规模数据的处理效率问题。当数据量很小时（比如 10 个 8 个），用什么结构存储差别不大。

所以：

• 存 10 条配置，用数组还是链表，无所谓；

• 存 1000 万条订单，结构选错就是灾难。

这也解释了为什么后面分析复杂度时，小规模数据可以直接忽略。

1.4 不同场景用不同结构

课上给了几个典型对应关系：

没有"最好的数据结构"，只有"最适合这个场景的结构"。这句话后面还会反复出现。

二、时间复杂度：不看跑多久，看"跑多少次"

2.1 为什么不能用执行时间衡量算法

直觉上，A 算法跑 10ms、B 算法跑 20ms，那 A 更好。但这个标准不可靠，因为有多个不可控变量：

所以时间复杂度不直接看执行时间，而是数操作次数。

2.2 时间复杂度衡量的是"增长趋势"

时间复杂度本质上衡量的是算法执行次数随数据量变化的规律。

不能脱离数据量谈执行次数——处理 10 万条数据和 1 条数据的执行次数天差地别。

在大规模数据场景下，我们关注的是执行次数 y 与数据总量 x 的数学关系：

• 线性关系：y = ax + b

• 二次关系：y = ax² + bx + c

• 常数关系：y与x无关

执行次数越少，算法效率越高。比如y = 10x的算法就比y = x²更高效。

关键点：

时间复杂度反映的是数据增长时执行次数的变化趋势，而非具体的执行数字。

2.3 只保留主导项

当数据量 X 足够大时，其他小项都可以忽略。

比如执行次数是11000万零十，那个"十"完全可以忽略，我们只看量级的变化。

再比如：

y = 3x² + 100x + 5000

当 x = 100 万时：

• 3x²= 3×10¹²

• 100x= 10⁸

• 5000= 5×10³

后两项连第一项的零头都算不上。所以时间复杂度记作O(n²)，前面的系数 3、后面的 100x 和 5000 全部丢掉。

这就是大 O 记号的含义：只保留增长最快的项，并去掉常数系数。

2.4 常见复杂度排序

从优到劣：

2.5 函数图像：为什么 log n 最平缓

老师用画图的方式对比了三种基本函数：

一个容易忽略的点：当底数 a = 1 时，指数函数无意义，因为 1 的任何次方都是 1，无法形成有效增长曲线。

另外，对数换底只差一个常数倍：

log₂n = log₁₀n / log₁₀2

所以在时间复杂度里，底数不影响量级，O(log₂n)和O(log₁₀n)都记作O(log n)。

2.6 一律按最坏情况算

算法复杂度是按最坏情况考虑的。

在无序数组里查找元素，必须逐个检查。运气好可能第一个就命中，但复杂度不能按运气算——最坏情况要查遍整个数组，所以是 O(n)。

平均情况呢？目标在任意位置的概率相同，平均要查n/2次，量级还是 O(n)。

三、数组：连续内存带来的 O(1)

3.1 核心特征：内存连续分配

数组元素在物理内存中是紧密相邻的，就像排队时人与人之间没有空隙。

根据数据类型不同，每个元素占用的内存大小会变化：

但整体保持连续存储的特性不变。

3.2 地址计算公式

这是整节课最关键的公式：

元素地址 = 数组首地址 + 下标 × 每个元素占用的字节数

举例：int[] arr = {5, 7, 9, 11}，假设首地址是 1000，int 占 4 字节：

注意两个细节：

1. 数组变量名实际存储的是首个元素的内存地址。比如定义数组 array，它的值就是第一个元素的地址。

2. 内存寻址的最小单位是字节（8 比特），所以地址计算都按字节进行。

所以访问arr[2]，系统只需计算"起始地址 + 2 × 元素大小"就能定位，不需要遍历，一步跳到目标位置，这就是 O(1) 随机访问的底层原因。

运行时验证（ArraySearch.java）：

int[] arr = {5, 7, 9, 11}; System.out.println("数组首地址假设为 1000，int 占 4 字节"); for (int i = 0; i < arr.length; i++) { System.out.printf("arr[%d] 的地址 = 1000 + %d × 4 = %d，值 = %d%n", i, i, 1000 + i * 4, arr[i]); }

输出：

arr[0] 的地址 = 1000 + 0 × 4 = 1000，值 = 5 arr[1] 的地址 = 1000 + 1 × 4 = 1004，值 = 7 arr[2] 的地址 = 1000 + 2 × 4 = 1008，值 = 9 arr[3] 的地址 = 1000 + 3 × 4 = 1012，值 = 11

3.3 无序数组的查找：O(n)

如果没有下标，只知道"要找值等于 10 的元素"，那就只能从头遍历：

static int linearSearch(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) return i; } return -1; }

• 最坏情况：查 n 次

• 平均情况：查 n/2 次

• 复杂度：O(n)

这种无规划的存储方式虽然实现简单（直接在数组末尾追加数据），但查找效率低下。

3.4 同一个问题的两种解法：O(n) vs O(1)

求 1 到 X 的累加和：

解法一：for 循环

long sum = 0; for (int i = 1; i <= n; i++) sum += i; // 执行 n 次加法 → O(n)

解法二：等差数列公式

long sum = (long) (n + 1) * n / 2; // 执行 1 次乘除 → O(1)

实测（n = 1 亿）：

for 循环累加 1..100000000：27 ms，结果 5000000050000000（O(n)） 等差数列公式 (n+1)*n/2：0 ms，结果 5000000050000000（O(1)） 结果一致：true

这就是算法优化的意义：同一个问题，不同解法可能差一个数量级。

3.5 数组的局限

数组并不是万能的：

1. 长度固定（Java 数组），扩容要新建数组 + 复制；

2. 中间插入/删除要搬移后续元素，O(n)；

3. 需要连续内存，内存碎片多时可能分配失败。

这些局限正好由链表来解决。

四、二分查找：每次砍掉一半

4.1 前提：数组必须有序

无序数组不能二分，因为"砍一半"的前提是：如果目标比中间值大，那它一定在右半边。这个推理只在有序时成立。

4.2 核心逻辑

用两个指针left和right圈定查找范围：

1. 计算中间位置mid = (left + right) / 2

2. 比较arr[mid]和target

3. 相等 → 找到，返回

4. arr[mid] < target→ 目标在右半边，left = mid + 1

5. arr[mid] > target→ 目标在左半边，right = mid - 1

6. 重复，直到left > right—— 此时说明目标不存在

代码：

static int binarySearch(int[] arr, int target) { int left = 0, right = arr.length - 1; while (left <= right) { int mid = (left + right) >>> 1; // 无符号右移，避免溢出 if (arr[mid] == target) return mid; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; }

4.3 把每一步打出来

对[1, 3, 5, 7, 8, 10, 12, 15]查找 6（BinarySearchTrace.java）：

查找目标 6，数组长度 8 步骤 left right mid arr[mid] 决策 -------------------------------------------------------- 1 0 7 3 7 偏大，丢弃右半 → right = 2 2 0 2 1 3 偏小，丢弃左半 → left = 2 3 2 2 2 5 偏小，丢弃左半 → left = 3 left = 3，right = 2，left > right，说明不存在

查找 10：

步骤 left right mid arr[mid] 决策 -------------------------------------------------------- 1 0 7 3 7 偏小，丢弃左半 → left = 4 2 4 7 5 10 命中，返回下标 5

两次比较就命中。数据量越大，优势越明显。

4.4 复杂度推导

第 1 次比较后剩 n/2，第 2 次剩 n/4，……，第 k 次剩n / 2^k。

当剩到 1 个元素时：

n / 2^k = 1 2^k = n k = log₂n

所以最多比较⌊log₂n⌋ + 1次，时间复杂度O(log n)。

实测对比（ArraySearch.java）：

数据量 n 线性查找(最坏) 二分查找(最坏) log2(n) -------------------------------------------------------------- 1000 1000 9 10 10000 10000 13 13 100000 100000 16 17 1000000 1000000 19 20

n 从 1000 涨到 100 万（1000 倍），线性查找次数涨 1000 倍，二分只从 9 次涨到 19 次。

4.5 三个必须记住的坑

坑 1：mid溢出

int mid = (left + right) / 2; // 错误：left + right 可能溢出 int mid = left + (right - left) / 2; // 正确 int mid = (left + right) >>> 1; // 正确：无符号右移

当left和right都接近Integer.MAX_VALUE时，相加会变成负数。

坑 2：循环条件写成left < right

会漏掉最后一个元素。必须是left <= right。

坑 3：忘记数组必须有序

对无序数组二分，结果完全随机。

4.6 排序的成本不能忽略

这是老师特别强调的一点：

无序数组直接使用有序数组的 O(log n) 算法是不可行的，因为排序本身需要额外时间。

现实数据往往是无序的。想用二分，必须先排序。而常见排序算法（冒泡、快速排序等）的时间复杂度通常是O(n log n)。

所以：

如果只查一次，排序反而更亏。这就是为什么要根据查询频率选方案。

五、哈希表：不算排序，直接算位置

5.1 核心思想

既然排序太贵，能不能设计一种算法，让给定任意数据时直接算出它在数组中的目标位置？

可以。用数据对数组长度取余：

下标 = key % 数组长度

比如数组长度 10：

查找时也遵循同样的规则：要查 12 就重新算12 % 10 = 2，直接看下标 2 的位置是否存在该数据。

存取时间复杂度都是 O(1)，因为不需要遍历，直接通过计算定位。

关键点：存取规则必须严格一致。存的时候怎么算，查的时候就得怎么算。

5.2 哈希冲突

问题来了：不同数据可能算出相同位置。

比如长度 10 的数组，12 和 22 都会落到下标 2。这就是哈希冲突。

如果直接覆盖写入，原数据就丢了——原本位置存了 12，新数据存入后 12 就彻底消失了。

5.3 解法一：线性探测法

遇到冲突就往后顺位存。

33 本该存 3 号位，但被占了 → 存 4 号位

缺点很明显：

1. 查找时需要一直向后遍历，直到遇到空位；

2. 数组空间有限，可能造成数据堆积；

3. 删除元素会留下"空洞"，处理起来很麻烦。

5.4 解法二：链地址法（拉链法）

每个数组位置挂一条链表，冲突的数据都挂到同一条链上。

结构就是：

数组（桶）+ 链表（解决冲突）

查找时：

1. 先算下标，定位到桶；

2. 遍历这个桶的链表。

复杂度分析：

• 链表较短时，遍历耗时可忽略，整体近似O(1)；

• 链表过长时，退化为O(n)。

这就是哈希表最坏情况是 O(n) 的原因。

5.5 链表太长怎么办：转红黑树

Java 的 HashMap 做了优化：

当链表较短时保持链表结构，数据量增多时会自动转为红黑树，时间复杂度降到O(log n)。

具体阈值（JDK 8）：

为什么是 8？因为链表长度达到 8 的概率已经极低（泊松分布），此时转树的收益才大于成本。

5.6 完整实现

HashTableChaining.java实现了一个带扩容的链地址哈希表：

static class Node { int key; Node next; Node(int key) { this.key = key; } } private Node[] buckets; private int size; private int collisions; private static final double LOAD_FACTOR = 0.75; /** 取余法算下标。长度取 2 的幂时，可以用 key & (len-1) 代替 %，更快 */ private int indexFor(int key) { return key & (buckets.length - 1); } public void put(int key) { int idx = indexFor(key); if (buckets[idx] == null) { buckets[idx] = new Node(key); } else { collisions++; Node cur = buckets[idx]; while (true) { if (cur.key == key) return; // 已存在，不重复插 if (cur.next == null) break; cur = cur.next; } cur.next = new Node(key); // 尾插 } size++; if (size > buckets.length * LOAD_FACTOR) resize(); }

实测：

put(9) → 下标 9 put(1010) → 下标 2 put(12) → 下标 12 put(33) → 下标 1 put(44) → 下标 12 put(25) → 下标 9 put(28) → 下标 12 插入后：容量 16，元素 7，占用桶 4，冲突 3 次，最长链 3 get(12)：桶 12，链表走了 1 步 → 命中 get(33)：桶 1，链表走了 1 步 → 命中 get(999)：桶 7，链表走了 0 步 → 未命中

极端冲突场景（所有 key 都是 8 的倍数，全部落到 0 号桶）：

全冲突场景：容量 8，元素 6，占用桶 1，冲突 5 次，最长链 6 get(40)：桶 0，链表走了 6 步 → 命中

6 个元素要走 6 步，退化成了 O(n)。

扩容过程：

[扩容] 4 → 8，重新散列 4 个元素 [扩容] 8 → 16，重新散列 7 个元素 插入 0..9 后：容量 16，元素 10，占用桶 10，冲突 0 次，最长链 1

5.7 五个关键细节

1. 哈希表牺牲了顺序性。它适合"按 key 找 value"，不适合"按范围查"。

2. 冲突不可避免，取余必然撞，链地址法是最常用的解法。

3. 链表太长会退化，所以 Java 8 转红黑树。

4. 扩容要重新散列全部元素，很贵——能预估容量就先指定初始大小。

5. 长度用 2 的幂，是为了把%换成更快的位运算& (len - 1)。

// 两者等价，但位运算更快 key % 16 key & 15

前提：长度必须是 2 的幂，否则不等价。

六、链表：内存不连续，靠"地址"串起来

6.1 结构

链表节点在物理空间上分散存储，每个节点包含两部分：

链表变量head存的是第一个节点的地址，是整条链的起点。

head → [5|·] → [7|·] → [9|·] → [11|null]

6.2 遍历

从 head 开始，顺着 next 一个个走：

for (Node cur = head; cur != null; cur = cur.next) { System.out.println(cur.value); }

当 next 为 null 时，说明到链表末尾了。

6.3 链表查找为什么是 O(n)

因为不能随机访问。

数组可以通过下标直接定位任意元素（O(1)），但链表要找到第 n 个节点，必须从头开始逐个遍历。

实测（LinkedListDemo.java）：

get(0) 走了 0 步，值 = 5 get(3) 走了 3 步，值 = 11

访问第 3 个元素要走 3 步，访问第 n 个要走 n 步。

6.4 为什么链表不能二分

二分查找每次要访问"中间节点"。在数组里，arr[mid]是 O(1)；在链表里，找到中间节点要遍历 n/2 个节点。

所以二分的"折半"优势完全消失，反而更慢。

链表的有序性并不能优化查找效率，这是链表和数组在访问机制上的本质区别。

6.5 插入和删除：只改指针

链表的优势在这里。

头部插入：

Node node = new Node(v); node.next = head; // 新节点指向原头 head = node; // head 指向新节点

只改 2 个指针，O(1)。

中间插入（在 index 位置）：

Node prev = head; for (int i = 0; i < index - 1; i++) prev = prev.next; // 找前驱，O(n) Node node = new Node(v); node.next = prev.next; // 先接后面 prev.next = node; // 再断前面

找位置是 O(n)，但改指针是 O(1)，不需要搬动任何元素。

对比数组：数组中间插入要把后面所有元素后移一位，O(n) 次内存拷贝。

6.6 一个必须记住的顺序

node.next = prev.next; // 先接后 prev.next = node; // 再断前

顺序反了会怎样？

如果先prev.next = node，那原来的prev.next就丢了，后面整条链断掉，再也找不回来。

6.7 双向链表

每个节点多存一个pre指针，指向前驱：

static class DoublyNode { int value; DoublyNode pre, next; }

好处：可以从任意节点向前或向后遍历。 代价：每个节点多存一个指针，插入删除时要多维护一个指针。

实测：

正向：1 2 3 反向：3 2 1

只要掌握了单向链表的增删改查，双向链表就很容易上手，主要区别是需要额外处理 pre 指针。

6.8 数组 vs 链表完整对比

最后一行是实际开发中很重要但课上没展开的点：数组在真实机器上往往比链表快得多，即使理论复杂度一样，因为 CPU 缓存喜欢连续内存。

七、树：从"一条链"到"分叉"

7.1 为什么需要树

链表查找是 O(n)，哈希表虽然 O(1) 但丢失了顺序。

有没有一种结构，既能保持有序，又能 O(log n) 查找？

有，就是树。

7.2 树的基本概念

树结构和现实中的树相反：根节点在最上方，向下分叉形成子节点。

分类：

• 二叉树：每个节点最多两个子节点；

• 多叉树：子节点数量较多，通常超过 100 个。

多叉树的优势在于存储大量数据时能保持较低的树高，从而提升效率——这就是后面 B 树的思路。

7.3 有序二叉树（二叉搜索树）

规则只有一条：

每个节点的左子节点值 < 父节点值 < 右子节点值。

构建过程：

1. 第一个值直接作为根节点；

2. 后续每个新值从根开始比较；

3. 比当前节点小就往左走，大就往右走；

4. 直到找到空位插入。

比如插入50, 30, 70, 20, 40, 60, 80：

50 / \ 30 70 / \ / \ 20 40 60 80

7.4 中序遍历一定有序

这是二叉搜索树最重要的性质：中序遍历（左 → 根 → 右）的结果一定是从小到大排列。

private void inorder(Node n, StringBuilder sb) { if (n == null) return; inorder(n.left, sb); sb.append(n.value).append(" "); inorder(n.right, sb); }

实测输出：

中序遍历（一定是从小到大）：20 30 35 40 45 50 60 65 70 80

7.5 查找：每次排除一半子树

从根开始比较：

• 目标等于当前节点 → 找到；

• 目标小于当前节点 → 去左子树找；

• 目标大于当前节点 → 去右子树找。

每比较一次，就排除掉一整棵子树。

7.6 树高的数学关系

二叉树第 k 层的节点数：

第 1 层：2⁰ = 1 第 2 层：2¹ = 2 第 3 层：2² = 4 第 k 层：2^(k-1)

总节点数（前 k 层）：

X = 2⁰ + 2¹ + 2² + ... + 2^(k-1) = 2^k - 1

反推树高：

2^k = X + 1 k ≈ log₂X

所以理想情况下，树高是 log₂X，查找复杂度O(log n)。

7.7 但 O(log n) 是有条件的

这是整节课最重要的"坑"：

普通二叉搜索树的 O(log n) 并不稳定。如果树不平衡（比如退化成链表），效率会下降到 O(n)。

构造一个最坏情况：按顺序插入 1, 2, 3, ..., 10。

1 \ 2 \ 3 \ ...

每个新节点都比上一个大，全部挂在右边，树变成一条向右的链。

实测（BinarySearchTree.java）：

=== 有序插入：退化成链表 === 节点数 10，树高 10 —— 已经完全退化成一条向右的链 查找 10：比较 10 次，命中 查找 11：比较 10 次，未命中

查找 10 要比较 10 次，和遍历链表没有区别。

数据量放大后的对比：

数据量 随机树高 有序树高 log2(n) ------------------------------------------------ 100 14 100 6.6 1000 22 1000 10.0 10000 33 10000 13.3

注意：即使是随机插入，树高（14/22/33）也比理论值 log₂n（6.6/10/13.3）高不少。因为随机二叉搜索树的平均高度约为3log₂n，不是 log₂n。

这就引出了下一节课的主题：平衡二叉树——插入后强制旋转，把树高压回 log n。

7.8 二叉搜索树的完整实现

static class Node { int value; Node left, right; Node(int value) { this.value = value; } } /** 插入：从根开始比，小往左、大往右，直到空位 */ void insert(int v) { if (root == null) { root = new Node(v); size++; return; } Node cur = root; while (true) { if (v == cur.value) return; // 不存重复值 if (v < cur.value) { if (cur.left == null) { cur.left = new Node(v); size++; return; } cur = cur.left; } else { if (cur.right == null) { cur.right = new Node(v); size++; return; } cur = cur.right; } } } /** 查找：返回比较次数 */ int search(int target) { Node cur = root; int compares = 0; while (cur != null) { compares++; if (target == cur.value) return compares; cur = (target < cur.value) ? cur.left : cur.right; } return -1; }

八、学习路线：老师给的几条实用建议

这部分不是技术，但很值钱。

8.1 关于力扣

• 必须注册力扣账号才能使用相关资源；

• 题目不是最终考核目标，而是往年面试真题——这些题目曾被面试官用于现场考察；

• 所有题目都能在力扣题库中找到；

• 题库题目没按顺序排列，但都是基础且规整的练习素材；

• 建议从数组、字符串、排序这些即将讲解的类型入手；

• 力扣第一题就曾出现在真实面试中。

8.2 关于基础

基础不牢，地动山摇。

• Java 入门很简单，用变量和函数就能开始操作，没学过 Java 也不影响学数据结构；

• 但前期基础不扎实，后续做项目会明显吃力，甚至跟不上；

• 很多同学后期调班或学习困难，根本原因是前期基础没打好；

• 随着课程节奏加快，需要自主搜索和写项目时，基础薄弱就会暴露。

8.3 关于课程节奏

• 前期以讲授为主，同时布置探索任务；

• 后期减少讲解，增加自主探索比重；

• 这不同于高中应试教育，不是所有考试内容都会在课堂直接教，需要培养主动探索能力；

• 实际求职中，大公司往往使用内部定制框架，而非 Spring Boot 等教学框架，需要培养适应能力。

8.4 关于 AI 工具

初期学习算法和项目时不要依赖 AI，必须等到能一眼识别代码错误的熟练程度后，才能将其作为辅助工具。

这条建议很实在。AI 能帮你写出能跑的代码，但不能替你建立"看到这段代码就知道哪里会错"的直觉。

8.5 关于刷题方法

• 不要死磕，想不出就参考 AI 提示或精选题解；

• 方法不唯一，哈希映射和暴力枚举效率明显不同；

• 平台会显示算法效率排名，这正是评判标准；

• 前期不必过分追求效率，先用暴力破解把代码写出来；

• 随着学习深入，重点转移到优化时间复杂度上。

一句话：先跑通，再跑快。

8.6 关于时间分配

• 有疑问随时提问，课上不懂可以立即打断；

• 高效学习避免重复听课，把省下的时间用来实践；

• 要么多写项目丰富简历，要么直接去实习。

九、这一篇的知识地图

数据结构 ├─ 目标：提高大规模数据的操作效率 ├─ 衡量工具：时间复杂度 │ ├─ 不看执行时间（硬件/数据/调度不可控） │ ├─ 看执行次数与 n 的函数关系 │ ├─ 只保留主导项，去掉系数和低阶项 │ └─ 常见量级：O(1) < O(log n) < O(n) < O(n log n) < O(n²) │ ├─ 数组 │ ├─ 内存连续 → 地址 = 首地址 + 下标 × 元素大小 → O(1) │ ├─ 无序查找 O(n)，有序二分 O(log n) │ └─ 中间插入/删除 O(n) │ ├─ 二分查找 │ ├─ 前提：有序 │ ├─ left / right / mid，left > right 终止 │ ├─ 每次砍一半 → O(log n) │ └─ 排序成本 O(n log n)，不能白拿 │ ├─ 哈希表 │ ├─ 下标 = key % 长度 → 存取 O(1) │ ├─ 冲突：线性探测 / 链地址法 │ ├─ 链表过长 → 红黑树 O(log n) │ └─ 用 2 的幂长度 + 位运算加速 │ ├─ 链表 │ ├─ 节点 = value + next │ ├─ 查找 O(n)，不能二分 │ ├─ 插入/删除改指针 O(1) │ └─ 双向链表多一个 pre │ └─ 树 ├─ 根/父子/叶子，二叉树/多叉树 ├─ 有序二叉树：左 < 父 < 右 ├─ 第 k 层 2^(k-1)，总数 2^k - 1 ├─ 理想树高 log₂n └─ 会退化：有序插入 → 链表 → O(n)

十、关键概念 & 公式速查

十一、这节课要掌握什么

三条主线：

1. 复杂度是选型工具。看到 O(n²) 就要想办法优化；看到 O(log n) 要知道它依赖"有序"或"平衡"这个前提。

2. 数组和链表是两种基本取舍。数组换随机访问，链表换插入删除，没有绝对优劣。

3. 哈希是"用计算换查找"。它把 O(n) 降到 O(1)，代价是丢失顺序、必须处理冲突。

下一节要解决的问题是：普通二叉搜索树会退化，怎么让它稳定在 O(log n)？

答案就是平衡二叉树和红黑树。

配套代码

编译运行：