树结构算法动画实验室

Tree-Lab 是一个查找树（BST、AVL、红黑树、B树、B+树）模型交互式动画演示前端项目，可高度自定义插入、删除和查询，并逐帧观察旋转、染色、分裂、合并等调整过程，并可两个模型同时比较。

运行方式

直接用现代浏览器打开 index.html 即可。页面不依赖服务器、构建工具或外部资源，也可以通过任意静态 HTTP 服务器访问。

支持的树模型

• 二分查找判定树：操作后根据当前数据排序并重新构建，用于和动态树对比。
• 二叉排序树（BST）。
• AVL 树：展示平衡因子、失衡子树、辅助编号和旋转过程。
• 红黑树：展示染色、旋转、回溯、双黑节点和黑高。
• B树：可配置阶数，展示节点分裂、借键与合并。
• B+树：可配置阶数，展示局部叶分裂、索引更新、叶链、借键与合并。

基本操作

1. 在顶部输入框输入一个或多个用空格分隔的整数，例如 30 20 10。
2. 点击“插入”“删除”或“查询”。每个整数会拆分为一条独立操作加入队列。
3. 选择一个树模型；启用“对比”后可同时选择两个模型，并让它们执行相同操作队列。调整阶数仅适用于B树和B+树。
4. 点击“播放”，或使用时间轴按钮逐帧查看结构与说明。
5. 点击队列中的操作或动画帧可直接跳转。

键盘快捷键：

• ↑：上一帧。
• ↓：下一帧。
• 空格：播放或暂停。

操作队列字符串

输入框也支持直接载入紧凑格式的操作队列：

i1 i-1 q-1 d-1

前缀含义：

• i：插入（insert）。
• q：查询（query）。
• d：删除（delete）。

“复制保存”会将当前操作队列复制成这种格式，可批量快速编辑后重新载入。

绘制选项

• 外部节点：显示查找失败节点；带辅助标签的临时空节点不受此开关限制。
• 显示 ASL：显示当前结构的平均查找长度。
• 层分界线：显示各层的水平辅助线。
• BF / 黑高：AVL 树显示平衡因子；红黑树在叶节点和已显示的外部节点上显示根路径黑高。
• 自动播放：播放时自动前进。
• 适配宽度：按绘图区宽度缩放完整树形。
• 阶数：供B树和B+树使用，允许设置为 3 至 8，默认值为 4。

阶数约定

• 上述查找树模型定义和操作参考严蔚敏《数据结构》。
• m 阶B树的节点最多有 m 棵子树和 m-1 个关键字；出现第 m 个关键字时分裂。非根节点最少有 ceil(m/2)-1 个关键字。
• m 阶B+树的叶节点最多保存 m 个关键字，内部节点最多对应 m 棵子树。叶节点溢出时只分裂当前叶，不重新分配其他叶节点数据，非叶节点的每个索引保存对应子树的最大值。

动画标记

• 橙色路径和箭头：当前查找或插入路径。
• 虚线边框：待删除节点或中序后继删除替身。
• cur 箭头：当前正在回溯或调整的节点。
• 辅助标签与虚线框：旋转、染色或结构调整涉及的节点和局部子树。
• 双层黑圈：红黑树删除调整中的双黑节点。
• 蓝色直线箭头：B+树叶节点链表。

注意事项

• 输入必须是整数，重复插入会被忽略。
• 页面完全运行在浏览器内，不会上传或持久化操作数据；需要保留队列时请使用“复制保存”。