Project: Audit Adaptive Search and Cache History

Acceptance trace

Insert case IDs 47, 19, 83, and 61. Their in-order list must remain 19, 47, 61, 83 after each splay. A hit on 19 makes 19 root; a miss on 55 returns false while bringing the last comparison node, 61, to root. Remove 47 and verify the remaining ordered list and every child-to-parent link. For a three-slot K=2 cache, insert 47, 19, 61, then read 47 and 61. Inserting 83 evicts 19. A missing read raises KeyError without advancing the clock. A duplicate case insertion returns false but may reshape the tree.

Expected review record

ordered-before=[19, 47, 61, 83]
miss-55=False; root=61
ordered-after-remove=[19, 61, 83]
cache-victim=19
resident-ids=[47, 61, 83]

Failure and cost review

Generate randomized insert, find, and remove operations against a Python set, checking sorted membership and parent links after every step. Repeat the cache trace against a small explicit history ledger, including capacity one, repeated writes, cold ties, and a read of a missing key. Record the maximum search depth and the number of cache candidates examined on each full insertion. Explain why a long splay path does not disprove its amortized bound and why the resident-history scan is still linear in capacity. Decide whether strict per-request latency or ghost history is needed before adopting either model in a production service.

Common Mistakes

• Do not compare only the splay return value; also check its in-order and parent invariants.
• Do not count a failed cache read as a reference under this policy.
• Do not infer a per-operation latency bound from amortized tree cost.
• Do not retain an evicted resident's history in the resident-only model.

Connected lessons

• Splay Trees: Access Rotations and Join Invariants
• Resident LRU-K: Evict by the Kth Recent Reference
• Projects
• Quizzes
• Data Structures