Treap

In computer science , a treap (formed from binary search tree , binary search tree + heap , literally heap, heap) is a binary search tree . Each node x consists of two elements:

x.key (element)
x.priority (priority)

Treaps were invented in 1989 by Cecilia R. Aragon and Raimund G. Seidel ( Saarland University ). An alternative name is Balde (formed from tree and heap).

elements

They fulfill the characteristics of the binary search tree. That means:

The elements y in the left subtree of x satisfy: key (y) <key (x)
The elements y in the right subtree of x fulfill: key (y)> key (x)

priorities

Priorities fulfill the properties of the heap . That means:

All priorities are different (random numbers)
The root has the lowest priority (top element)
If y is a child of x, then: prio (y)> prio (x)

Search for an item

The search is carried out as in a binary search tree. The value k to be searched for is compared with the value of the root. If k is larger, the value is compared with the next node in the right subtree, if smaller, then in the left. Expected term : ${\ displaystyle {\ mathcal {O}} (\ log n)}$

Inserting an element

To insert an element e into a treap, create a new node x , save the element e in x.key and choose a random priority for x.priority . Now insert the node into the Treap using x.key according to the properties of the binary search tree. Since the heap property could be violated by the new node, the node is now rotated up until the heap condition is met again.

Expected maturity: . The expected depth is logarithmic. The number of rotations to be expected is 2. ${\ displaystyle {\ mathcal {O}} (\ log n)}$

Remove an element

One looks for the position of the node x to be removed in the tree
You change the priority to + ∞ (infinite)
The node to be removed is rotated to the side where the higher priority is until the heap condition is met, in particular until the element to be deleted is a leaf.
The element is now a sheet and can be deleted

Expected maturity: . The expected depth is logarithmic. The number of rotations to be expected is 2. ${\ displaystyle {\ mathcal {O}} (\ log n)}$

Find the smallest / largest element

Since the elements in a Treap are stored in the order of a normal binary search tree, the smallest element can be found at the bottom left and the largest element at the bottom right. Thus, to find the smallest element, you always have to descend to the left subtree, and to find the largest element always descend to the right subtree.

Expected running time: because the expected depth is logarithmic. ${\ displaystyle {\ mathcal {O}} (\ log n)}$

List all items

Outputs all elements in ascending order
Is carried out by the in-order pass (between the two subtrees)

Term is . ${\ displaystyle {\ mathcal {O}} (n)}$

literature

Thomas H Cormen, Charles E. Leiserson , Ronald L. Rivest , Clifford Stein: Algorithms - An Introduction . Oldenbourg, Munich, Vienna 2004, ISBN 3-486-27515-1 (Original title: Introduction to algorithms . Translated by Karen Lippert, Micaela Krieger-Hauwede).