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.
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~:
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.