Advanced Data Structures · Visualization Lab
用 可交互图形 理解高级数据结构的内部运转
本实验室覆盖 8 种经典高级数据结构，从 B+ 树的节点分裂到斐波那契堆的级联剪切，再到后缀数组的 LCP 构造。每一次操作都会实时渲染结构形态，并在日志区解释发生了什么。
Module 01
01 B+ 树 节点分裂 / 合并
所有数据存于叶子节点并通过链表相连，内部节点仅用于索引路由。插入触发叶子分裂并向上传递分隔键，删除触发借位或合并。
B+ Tree · order=4
绿色=叶子 · 紫色=根 · 虚线=叶子链
键总数0
节点数0
高度0
叶链0
Module 02
02 红黑树 旋转 · 重着色
自平衡二叉搜索树，通过红黑性质与旋转/重着色维护近似平衡，保证最坏路径长度不超过最短路径的两倍。
Red-Black Tree
红=Red · 黑=Black · 黑高保持一致
节点数0
黑高0
红节点0
高度0
Module 03
03 跳表 Skip List 概率平衡
多层链表结构，以概率 p=0.5 决定节点提升层数，期望 O(log n) 的查找/插入/删除，是实现有序集合的简洁方案。
Skip List · p=0.5
顶层=快速通道 · 高亮=搜索路径
元素数0
最高层0
总指针0
平均层0
Module 04
04 区间树 Interval Tree 重叠检测
以区间低端排序的增强红黑树，每个节点额外维护子树最大右端点 max，可在 O(log n) 时间内查找与给定区间/点重叠的所有区间。
Interval Tree · [low, high]
节点=[lo,hi] max · 高亮=命中重叠
区间数0
根 max0
命中数0
高度0
Module 05
05 Van Emde Boas u² 递归
固定全域 U 的整数优先队列，递归划分为 √U 个规模 √U 的簇与一个 summary，支持 O(log log U) 的插入/后继查询。
vEB · U=16 (√U=4)
簇=低位 ÷4 · summary=簇存在性
元素数0
非空簇0
min—
max—
Module 06
06 斐波那契堆 级联剪切
支持 O(1) 摊还 Decrease-Key 的可合并堆。子节点被切断后提升至根链表，第二次断子触发级联剪切（标记 → 切断 → 上传）。
Fibonacci Heap · 根链表 + 子树
点击节点选中 · 黄圈=已标记 · 虚框=选中
节点数0
根数0
已标记0
最小值—
Module 07
07 后缀数组 / LCP 字符串索引
将字符串所有后缀按字典序排序得到后缀数组 SA，相邻后缀的最长公共前缀构成 LCP 数组，是构建后缀树与高效字符串匹配的核心。
Suffix Array + LCP
下排=排序后后缀 · 柱=LCP · 紫峰=最大重复
长度 n0
最大 LCP0
最长重复子串—
Σ LCP0
Module 08
08 并查集进阶 路径压缩 · 按秩合并
不相交集合森林。Find 沿路径压缩将节点直连根，Union 按秩（秩小挂秩大）合并，使摊还复杂度近 O(α(n))。
Disjoint Set Union · forest
高亮=Find 路径 · 根节点带秩
集合数0
规模0
最大集合0
路径长度0