Splay Tree

overview

Summary

A splay_tree is a self-adjusting binary_search_tree. After every operation it performs splaying: move the accessed node to the root using rotations zig, zig_zig, and zig_zag. Common operations are search, insert, delete, join, and split. There is no explicit balancing structure. Recently used keys become near the root. Time is amortized O(log n) over a sequence, with worst-case O(n) for a single operation. Good for temporal_locality access patterns.