A Treap is a randomized BST that combines BST property (keys) with heap property (priorities). Each node has a key and a random priority.
The tree is a BST by keys and a max-heap by priorities. This combination ensures expected height. Why random priorities? They prevent worst-case linear depth.
No matter what order you insert keys, the random priorities shuffle the structure into a balanced tree with high probability. Treaps are simpler than AVL or Red-Black trees. No rotations to memorize, just split and merge operations.