cs61A-study-lecture5

· 2714 字 · 7 分钟

0 次浏览 / 0 条评论

#python#cs
目录

Tree

0. 核心术语与物理性质

  1. 深度 (Depth) vs 高度 (Height)：记住，深度是从上往下看，高度是从下往上看。

  • 度 (Degree)：节点拥有的子树个数。

  • 层序关系：父子、兄弟、祖先、后代。

  1. 遍历算法（算法的基础功）

  • 深度优先 (DFS)：

    前序 (Pre-order)：根 -> 左 -> 右。（用于：复制树、表达式前缀化）。

    中序 (In-order)：左 -> 根 -> 右。（核心性质：对 BST 中序遍历得到的是升序序列）。

    后序 (Post-order)：左 -> 右 -> 根。（用于：计算文件夹大小、销毁树节点、求逆波兰表达式）。

  • 广度优先 (BFS)：一层一层扫过去。（用于：寻找无权图的最短路径）。

1. 基础形态类：树的“生理结构”

  1. 二叉树 (Binary Tree)：每个节点最多两个子节点。

  2. 满二叉树 (Full Binary Tree)：每个节点要么有 0 个子节点，要么有 2 个。

  3. 完全二叉树 (Complete Binary Tree)：除了最后一层，其他层全满，且最后一层节点靠左排列（堆的物理基础）。

  4. 完美二叉树 (Perfect Binary Tree)：所有层全满，所有叶子都在同一深度。

  5. 退化树 (Degenerated Tree)：每个节点只有一个子节点，实际上退化成了链表。

2. 搜索优化类：内存中的“性能怪兽”

这类树存在的唯一目的，就是将查询、插入、删除的时间复杂度维持在 O(log⁡n)O(\log n)。

  1. 二叉搜索树 (BST)：左小右大。简单但容易在数据倾斜时退化。

  2. AVL 树：最早的自平衡二叉搜索树。严格平衡，查找极快，但插入和删除时的“旋转”开销较大。

  3. 红黑树 (Red-Black Tree)：

    地位：工业级标准。C++ std::map/set、Linux 内核 CFS 调度、Java HashMap 的底层。

    特性：通过红黑染色和弱平衡规则，在查找效率和增删开销之间取得了完美平衡。

  4. 伸展树 (Splay Tree)：刚访问过的节点会通过旋转移动到根部。利用了局部性原理（刚用过的数据大概率还会用）。

  5. Treap (树堆)：结合了二叉搜索树和堆的特性。通过随机优先级防止树退化。

  6. 替罪羊树 (Scapegoat Tree)：不通过旋转，而是通过“重构”来保持平衡，非常暴力但也有效。

3. 多路搜索类：海量数据的“存储基石”

当数据量大到内存装不下，需要存放在磁盘或数据库中时，为了减少 I/O 次数（降低树的高度），我们需要“胖”一点的树。

  1. B 树 (B-Tree)：多路平衡搜索树，一个节点可以存成百上千个键值对。

  2. B+ 树：

地位：数据库索引之王（MySQL InnoDB）。

进化：数据全在叶子节点，且叶子节点用双向链表连接。极大地优化了范围查询。

  1. B 树*：在 B+ 树的基础上，非叶子节点也增加了指向兄弟的指针，进一步提高空间利用率。

4. 空间与几何类：机器人算法的“主战场”

这是你作为 RoboMaster 算法组长最需要精通的部分。

  1. KD-Tree (K-Dimensional Tree)： KD 树（K 维树）：

    应用：激光雷达点云的最近邻搜索 (NN)、FLANN 匹配。

    原理：在 K 维空间中交替切分。

  2. 四叉树 (Quadtree) / 八叉树 (Octree)：

    应用：SLAM 里的占据栅格地图 (Occupancy Map)、渲染引擎的空间剔除。

    威力：将空间进行递归划分，极大节省了存储空白区域的内存。

  3. R 树 (R-Tree)：处理“矩形”和“多边形”的范围搜索。导航软件找“附近的人”常用。

  4. BVH (Bounding Volume Hierarchy)： BVH（包围体层级）：

    应用：碰撞检测、光线追踪。把复杂的物理模型包在层层嵌套的包围盒中。

  5. BSP 树 (Binary Space Partitioning)：通过平面切割空间。FPS 游戏早期处理遮挡剔除的核心。

5. 字符串与序列类：高效匹配与路由

处理前缀、模式匹配和数据压缩。

  1. 字典树 (Trie)：

应用：自动补全、路由表查找。利用字符串的公共前缀减少存储。

  1. 基数树 (Radix Tree)：压缩版的 Trie，节省空间。Linux 内核内存管理常用。

  2. 后缀树 (Suffix Tree)：用于复杂的字符串模式匹配（比如寻找重复最长的子串）。

  3. AC 自动机 (Aho-Corasick)：虽然它是自动机，但逻辑基础是 Trie。

6. 堆与优先队列类：任务调度利器

逻辑上是树，物理上通常是数组。

  1. 二叉堆 (Binary Heap)：最大堆/最小堆。用于 A* 算法维护待探索点集。

  2. 斐波那契堆 (Fibonacci Heap)：理论上合并和降低键值的速度极快，常用于优化 Dijkstra。

  3. 索引堆 (Indexed Heap)：允许高效地修改堆中指定索引的元素，工程中非常实用。

7. 逻辑决策与控制类：机器人的“大脑”

  1. 行为树 (Behavior Tree)：

    地位：机器人和游戏 AI 的标配。相比 FSM（有限状态机），更易于模块化和嵌套。

  2. 决策树 (Decision Tree)：机器学习算法的基础，通过特征分裂进行分类或回归。

  3. 博弈树 (Game Tree)：Minimax 算法的基础。用于五子棋、象棋等 AI 的博弈计算。

8. 数据完整性与安全类

  1. 默克尔树 (Merkle Tree)：

    应用：区块链、Git 版本控制。叶子是数据的 Hash，父节点是子节点的 Hash 组合。

    价值：极速验证海量数据的篡改情况。

9. 高阶统计与范围查询类

竞赛算法和高性能系统常用。

  1. 线段树 (Segment Tree)：处理区间更新、区间查询（求和、最大值）。

  2. 树状数组 (Fenwick Tree / Binary Indexed Tree)：比线段树更省空间，适合处理前缀和。