This module implements splay trees, which are self-adjusting binary search trees invented by Daniel Sleator and Robert Tarjan in 1985. Splay trees maintain balance through a self-adjusting mechanism called "splaying" rather than explicit balance information like AVL or Red-Black trees.

A key property of splay trees is that most operations move the accessed element to the root, an operation called "splaying". This operation usually splits into 3 different kinds of steps~:

  • Zig: Single rotation when target is child of root
  • Zig-Zig: Double rotation when target and parent are both left or both right children
  • Zig-Zag: Double rotation when target and parent are on opposite sides

The results of a splaying modifies the splay tree but keeps the same elements inside, bringing a particular value to the node. This ensures a locality property, meaning that the values accessed most-often remain not too far from the root.

This data structure support insertion, removal, search, min and max operations. Its operations take amortized O(log n) time and O(n) space.

Note : most of this data structure has been written by an LLM.

Index

Variables

Functions