Pipapo

Observations:

  • A splay tree moves accessed nodes to the root of the tree, this is very costly

  • there was some success by randomizing splay trees in http://www.informatik.uni-freiburg.de/~salbers/ipl02.ps.gz

  • They splay top-down (which is considered more efficent)

  • the splay decision is done probabilistically once for the whole lookup

Ideas:

  1. splaying bottom up can be done on a per splay operation base

  2. deeper elements shall have a higher chance to splay up, elements near the root can have a small chance

  3. the zig case happens only when we are next to the root

  4. the zig-zig mirrors the symetrie of a subtree but doesn’t contribute to the whole tree balancing

  5. the zig-zag case decreases the tree depth, which might be of global benefit

How it got Implemented:

  1. optimized bottom up splaying, nodes are still 2 pointers only, recursing into the tree keeps a temporary trail

  2. probabilistic splay function which adjusts the splaying chance depending on the depth of the node

  3. ignore the zig case, the node is one level under the root, any improvement would be mariginal

  4. zig-zig has a normal chance of splaying

  5. zig-zag has a higher chance of splaying