交互演示（数据结构）

本页承载排序、串与 KMP与查找（AVL、红黑树、B 树）章的配套交互动画。章节正文中的"分步静态表 + 文字推演"可先手推，再回到本页逐步对照验证。

快速排序一趟划分（洛穆托法）

序列 6，枢轴取最右元素。橙色列 = 枢轴，蓝色列 = 扫描指针 j，紫色列 = "小于区"边界 i，绿色 = 一趟结束后枢轴的最终归位。可单步推进或自动播放，注意观察每一步"比较 → 决定是否交换 → 指针推进"的完整决策链。

8(p)

取枢轴 pivot = a[R] = 6，i = -1（小于区边界），j 从 0 起扫描

第 1 / 11 步 · 橙=枢轴蓝=扫描指针 j 紫=小于区边界 i 绿=归位

KMP 模式匹配

主串 ABABDABACDABABCABAB，模式串 ABABCABAB（ $next$ = 0 1 1 2 3 1 2 3 4，1 起）。绿格 = 已匹配前缀，蓝格 = 当前比较且相等，红格 = 当前失配位置，紫格 = 模式串待比较部分。可切换"KMP / 朴素"两种模式对照：朴素匹配失配时主串指针 $i$ 回退、 $j$ 重置重比；KMP 失配时 $i$ 不动， $j \leftarrow next[j]$ ，回溯只发生在模式串上。 $next$ 表中高亮列为当前 $j$ 所指位置。

主串 ABABDABACDABABCABAB

j	1	2	3	4	5	6	7	8	9
T[j]	A	B	A	B	C	A	B	A	B
next[j]	0	1	1	2	3	1	2	3	4

第 1 次比较：S[1]=A vs T[1]=A → 相等，i、j 同步前进

第 1 / 31 步 · KMP 共比较 23 次 vs 朴素共比较 29 次 · 绿=已匹配前缀蓝=相等红=失配紫=待比较

AVL 树旋转

预置三个插入序列：综合序列（依次触发 RR、LR、LL 型失衡）、LR 型教材例、RL 型最小例。每个结点圆圈下方实时显示平衡因子 BF（左子树高 − 右子树高，408 约定）。单步推进时每轮插入先看到失衡判定（红圈 = 最小不平衡子树的根，状态说明标明 LL/RR/LR/RL 型与旋转方向），再看旋转后的结果（绿圈 = 旋转涉及的结点）。

插入序列：{15, 20, 24, 10, 13, 7, 30, 36, 25}

建树插入 15（第 1 个）：作为根结点

第 1 / 14 步 · 红=最小不平衡子树根蓝=平衡结点绿=旋转涉及 · BF = 左子树高 − 右子树高

B 树插入与分裂

预置插入序列 2（3 阶，最小度 $t = 2$ ：每个结点最多 $2t-1 = 3$ 个关键字）。结点渲染为多关键字矩形：绿色格 = 当前插入的关键字，红色格 = 分裂时上移的关键字，红框 = 分裂产生的新结点。单步推进时注意三件事：新关键字总落在最底层终端结点并保持结点内有序；关键字数超上限 3 时，第 2 个（ $\lceil 4/2 \rceil$ 个）关键字上移、原结点一分为二（左 1 右 2），上移可能使父结点连锁溢出；根分裂时上移关键字独居新根、树高加 1——序列末尾插入 2 恰好触发根分裂，可重点观察"B 树自根向上长高"。

初始为空树，将依次插入 5、8、1、9、6、3、12、7、10、13、4、11、2（t = 2，结点关键字上限 2t-1 = 3）

第 1 / 20 步 · 绿格=新插入关键字红格=上移关键字红框=分裂出的结点

红黑树插入

预置序列 1，依次触发 RR 型旋转（插 30）、父红叔红变色（插 15）、LL 型旋转（插 1）三种修复情形。每轮插入分三阶段独立成步：先按 BST 规则落下新红结点（绿圈，先想"为什么着红不着黑"）；再按"父 P、叔 U、祖 G"关系修复（橙圈，状态说明注明触发情形：父红叔红变色 / 父红叔黑 + LL / LR / RR / RL 旋转）；最后完成态给出黑高一致性校验说明（蓝圈）。变色可能连续上溯（如插 15 时 G 变红后又是根，需再改黑），旋转则一步终结——对照"父叔双红 → 变色上移；父红叔黑 → 旋转终结"口径逐步核对。

初始为空树，将依次插入 10、20、30、15、25、5、1（新结点一律先着红）

第 1 / 24 步 · 红/黑底色=结点颜色绿圈=新插入橙圈=修复涉及蓝圈=完成校验

哈夫曼树构造

频率表 a:45、b:13、c:12、d:16、e:89、f:55（经典算例）。黄色圈与红色圈 = 当前步被选中合并的两棵根权值最小树，绿色圈 = 合并生成的新结点。单步推进时注意：每步选的是"根权值最小的两棵树"，不是"频率最小的两个字符"；完成后对照编码表验证"高频短码"——频率 89 的 e 编码仅 1 位，频率 12 的 c 需 5 位；WPL 逐项手算后与表格合计核对。

频率表：a:45 b:13 c:12 d:16 e:89 f:55（经典算例） · 第 1 / 7 步

初始森林：6 个字符各成一棵单结点树（a:45 b:13 c:12 d:16 e:89 f:55）。哈夫曼算法每一步选根权值最小的两棵树合并，共需 5 步。

并查集与路径压缩

预置操作序列 union(1,2)、union(3,4)、union(3,5)、union(1,3) 后执行 find(4)，可切换"朴素 find / 路径压缩 find"两种模式对照。黄色圈 = 当前操作涉及的结点，蓝色圈 = find 沿途所在位置；下方 parent 数组实时联动（黄色格 = 本步涉及的下标）。切换到压缩模式观察最后一步：沿途结点全部直挂根，树高降低——再切回朴素模式对比同一序列下的树形，体会均摊复杂度的来源。

预置操作序列：union(1,2)、union(3,4)、union(3,5)、union(1,3)，最后 find(4) · 第 1 / 8 步

parent 数组（1 起，parent[i] = i 表示根）：

i	1	2	3	4	5	6
parent[i]	1	2	3	4	5	6

初始：6 个元素各自成集合，parent[i] = i（自己就是根）。union(x, y) 先各自找根，再把一个根挂到另一个根下。

使用建议

先在排序章的手推表上独立完成一趟划分，再与本页逐步核对
重点关注：j 扫描到小于枢轴的元素时 i 与 j 是否重合——重合时不发生实际交换，但 i 仍前进
一趟结束后自查：枢轴左侧是否全部严格小于枢轴、右侧是否全部不小于枢轴
KMP：对照"朴素"模式数一数主串指针 i 的移动轨迹——KMP 模式下 i 从头到尾不回退，回退只发生在 j 上；失配跳转前先在 $next$ 表里口算 $next[j]$ ，再点"下一步"验证
AVL：每轮失衡判定步先自己判断"插入点在失衡结点的哪一侧的哪一侧"，得出 LL/RR/LR/RL 后再点"下一步"核对；双旋用"三者中关键字居中者提为新根"速算复核
B 树：每个触发分裂的插入步先口算"上移哪个关键字、左右各剩几个"，再点"下一步"核对；看到根分裂步时提醒自己——B 树长高是根向上裂开，不是叶向下长
红黑树：每个修复步先自判情形（父红叔红 / 父红叔黑 + LL/RR/LR/RL），再点"下一步"核对；完成态的黑高数值沿任一根-叶路径手数黑结点验证
哈夫曼：每步先口算"当前森林中根权值最小的两棵是谁、新结点权值是多少"再点"下一步"核对；完成态先手算 WPL 再看表格合计
并查集：每个 union 步先分别找两个元素的根再挂接（注意挂的是根、不是元素本身）；压缩模式最后一步切回朴素模式，对比同一操作序列下的树高差异

#交互演示（数据结构）

#快速排序一趟划分（洛穆托法）

#KMP 模式匹配

#AVL 树旋转

#B 树插入与分裂

#红黑树插入

#哈夫曼树构造

#并查集与路径压缩

#使用建议