Define a treap and its characteristics.

A treap is a hybrid data structure that combines the properties of a binary search tree and a binary heap.

A treap, also known as a tree heap, is a type of data structure that efficiently supports the operations of both a binary search tree and a binary heap. It is called a 'treap' because it is a combination of a TREE and a HEAP. This data structure is unique because it maintains the in-order traversal property of a binary search tree and the heap property simultaneously.

In a treap, each node carries two values: a key, which follows the binary search tree property, and a priority, which follows the heap property. The key property ensures that for every node, all the keys in its left subtree are smaller, and all the keys in its right subtree are larger. The priority property ensures that each node has a higher priority than its children. The priority values are usually assigned randomly, which helps to maintain the balance of the tree.

The main operations of a treap include search, insertion, and deletion. The search operation in a treap is similar to that in a binary search tree. The insertion operation involves two steps: first, a new node is inserted according to the binary search tree property; then, the tree is restructured based on the heap property using rotations. The deletion operation also involves two steps: first, the node to be deleted is moved down to a leaf position by rotations preserving the heap property; then, the node is removed.

One of the main advantages of a treap is its efficiency. The expected height of a treap with n nodes is logarithmic in n, which makes the search, insertion, and deletion operations run in O(log n) expected time. This makes treaps a good choice for maintaining ordered lists or priority queues. Another advantage is that treaps are relatively easy to implement compared to other balanced binary search trees, such as red-black trees or AVL trees.