Implicit treaps don't store explicit keys. Instead, the "key" is the position in the in-order traversal, computed on the fly from subtree sizes.
Each node stores = number of nodes in its subtree. The position of a node is the count of nodes before it in in-order.
This approach enables array-like operations:
- Insert at position
- Delete at position
- Reverse a range
- Cyclic shift
All in expected time. Implicit treaps are like super-powered dynamic arrays.