MIT算法导论作业：Binder书签数据库实现疑问

1. 什么情况下(a1,a2)或(b1,b2)会变得相邻？

(a1,a2)或(b1,b2)相邻，本质是两段之间的预留空位被完全占用，触发场景分两类：

• 针对(a1,a2)：
  • 当P1持续扩容，比如多次执行move_page(A)（将B后的页面移至A前），或者往P1中插入新页面，P1的有效页面不断延伸，最终填满A与P2之间的预留空位，导致a1 + 1 = a2。
  • 多次执行shift_mark(A, +d)（将书签A向后移动d位），每次操作会把P1的最后d个页面划入P2，这会同步减少a1和a2的值，当累计移动的d等于预留空位长度时，两者就会相邻。
• 针对(b1,b2)：
  • 当P2持续扩容，比如往A、B之间大量插入页面，填满B与P3之间的预留空位，最终b1 + 1 = b2。
  • 多次执行shift_mark(B, -d)（将书签B向前移动d位），每次操作会把P3的前d个页面划入P2，同步增大b1和b2的值，当累计移动的d等于预留空位长度时，两者相邻。

2. 当书签B后没有页面时该如何处理？

当B后无页面（P3为空）时，无需调整核心结构，只需在操作逻辑中做简单判断：

• 索引维护：b2保持指向P3段的起始位置（比如数组的2n索引处，假设P3对应S[2n..3n-1]），此时b2到3n-1的位置均为空闲状态。
• 操作适配：
  • 执行shift_mark(B, d)时：若d为负（试图从P3取页面移动B），因P3为空直接跳过；若d为正（向后移动B），正常调整b1和b2以扩展预留空位。
  • 执行move_page(B)时：因B后无页面，操作无实际效果，直接返回。
  • 执行read_page(i)时：判断i是否落在P3的有效页面范围内，若P3为空则返回无对应页面。

内容的提问来源于stack exchange，提问作者monopoly