Data Structures19 sections · 729 units
Open in Course

Access: Step by Step

Understanding the process

Access(v) does three things:

1.1. Splay v to make it root of its auxiliary tree.

2.2. Detach right subtree of v (nodes deeper than v on the old preferred path). These become their own auxiliary tree.

3.3. Climb path-parent pointers: for each ancestor auxiliary tree:

  • Splay the connection point
  • Detach its old preferred child
  • Attach v's auxiliary tree as new preferred child
  • Splay v again

The loop continues until you reach the root (no more path-parent). Each iteration processes one preferred path. Total work is O(logn)O(\log n) amortized.