波仔
⌨️ 第三章 数值和数据的处理方法
📄 一句话概括

文件夹套文件夹、公司一层管一层——树是【一对多】的层次结构；二叉树每节点最多两个孩子，完全二叉树能直接装进数组，平衡树保证不歪成一根链——本章收官，也是第三章【理想的数据处理方式】的答案：结构选对，查找从百万次降到二十次。

📝 本节和前面几节的关系

数组（3-8）是【一对一排队】、树是【一对多分层】——数据结构的最后一块大拼图。回收三处旧地：文件系统（树莓派课 4-4 目录树）、面向对象继承（C++ 课第十一章的类层次也是树）、哈希（3-13 的另一条加速路线）。

一、树：一对多的层次结构

树由节点组成，最顶上叫根，往下每层分叉，最末梢叫叶子。生活原型全是它：文件夹（根目录往下套）、公司组织架构、族谱、HTML 标签嵌套。树的判定就一条：任何节点只能有一个上级（父节点）——两个上级的那不叫树，叫图（后面课程的事）。

二、二叉树与它的两种形态

二叉树：每个节点最多两个孩子（左孩子、右孩子）——结构最简单、规律最好用：

三、平衡树：别让树歪掉

二叉搜索树有个致命弱点：按顺序插入就歪成一根链（1、2、3、4 依次插入，全往右边挂）——查找退化回 O(n)，白搭。平衡树（AVL、红黑树）在插入删除时自动旋转整形，保证左右大致等高——查找稳定在 O(log n)。现实里数据库索引（B 树家族）、语言标准库的有序集合，底层全是平衡树。

四、动手 Demo：数组里的树

tree = [8, 3, 10, 1, 6, 14]          # 完全二叉树按层放进数组

def parent(i): return (i - 1) // 2   # 父节点下标
def left(i):   return 2 * i + 1
def right(i):  return 2 * i + 2

print(tree[parent(3)])   # tree[1] -> 3   （下标3 的爸爸）
print(tree[left(1)])     # tree[3] -> 1   （下标1 的左孩子）
print(tree[right(1)])    # tree[4] -> 6   （下标1 的右孩子）

看到什么算成功：3、1、6。

读结果：数组的 6 个元素画成分层图——根 8，第二层 3 和 10，第三层 1、6、14。同一份数据两种视图：数组给【O(1) 的上下级跳转】，树给【分层的直觉】。这条下标规律正是堆排序与优先队列的全部地基。

五、30 秒实验

跑 import heapq; h = [5, 1, 8]; heapq.heapify(h); print(h)——得 [1, 5, 8]。heapify 一步把普通列表整成二叉堆（最小值浮到下标 0）——完全二叉树的数组形态正在你电脑里天天干活。

六、常见误区

  1. 【树的根在上还是在下随便画】——习惯上根永远在最上面（倒着长的树）；【根节点】【父节点】【叶节点】都以【往根的方向是上】为准。
  2. 【二叉搜索树永远快】——错。不保证平衡就退化：顺序插入歪成链、查找 O(n)；要快必须平衡——所以现实中的 BST 基本都是平衡树变种。
  3. 【完全二叉树和满二叉树是一回事】——错。满二叉树每层都满；完全二叉树允许最后一层【从左排不满右边】——完全的约束更松，恰好够【装进数组不浪费】。
自测三问（点开对答案） 1. **下标 i 的节点，父与两孩子下标各是多少？** 答：父 (i-1)//2、左孩子 2i+1、右孩子 2i+2（下标从 0 起）——完全二叉树住数组的通行证。 2. **为什么平衡树查找是 O(log n)？** 答：每下一层候选砍一半（左右子树有序分开）——100 万节点约 20 层就锁定，与哈希的 O(1) 相比还多送【有序遍历】。 3. **数据库索引为什么用 B 树家族不用普通二叉搜索树？** 答：数据量巨大时树高决定磁盘读取次数——B 树一个节点多叉、树更矮，磁盘 I/O 次数大幅减少。

相关笔记