splaytre

A splay tree is a self-adjusting binary search tree with the property that whenever a node is accessed, it is brought to the root of the tree through a series of rotations. This operation is called splaying. The goal of splaying is to improve the performance of subsequent accesses to the same or nearby nodes by placing them closer to the root.

Splay trees maintain the binary search tree property: for any given node, all keys in its left subtree are less than the node's key, and all keys in its right subtree are greater than the node's key. The splay operation rearranges the tree structure. When a node is accessed, it is moved to the root using a sequence of zig, zig-zig, and zig-zag rotations. The specific sequence of rotations depends on the position of the accessed node relative to its parent and grandparent.

While splay trees do not offer guaranteed logarithmic time complexity for every operation in the worst case, they do provide amortized logarithmic time complexity. This means that over a sequence of operations, the average time complexity per operation is logarithmic. This makes splay trees efficient for applications where certain keys are accessed frequently.

Splaying a node to the root effectively makes it the most accessible element. This property can be beneficial in various scenarios, such as implementing caches or priority queues where recently accessed items should be prioritized. The performance advantage of splay trees is particularly noticeable when there are locality of reference patterns in data access. They are a dynamic data structure, adapting to access patterns.