Concepts3

A splay tree is a self-adjusting binary search tree that moves the most recently accessed node to the root with rotations.

An implicit treap is a randomized balanced binary tree that treats array positions as keys without storing them explicitly.

A treap is a binary search tree on keys combined with a heap on random priorities, which keeps the tree balanced in expectation.