ABSTRACT

Strengths: Splay trees provide excellent access time when there is high locality of reference, meaning that elements accessed recently are likely to be accessed again soon. To provide this support, splay trees use rotations to move the most recently accessed element to the root, and in the process create fairly balanced trees without keeping any additional information in the nodes. It can be shown that insert, remove, min, max, successor, and predecessor have logarithmic amortized cost. This means that any sequence of m of these operations has worst-case O(m log n) time complexity.