Treap

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

• X.KEY ( element )
• X.priority (priority)

Treaps were invented by Cecilia R. Aragon and Raimund G. Seidel ( Saarland University ) in 1996. Alternative names are (formed from tree and heap ) and Baufen ( of tree and heap ) Balde.

Elements

They fulfill the properties of the binary search tree (binary search tree). This means:

• Meet the elements y in the left subtree of x: key (y) < key (x )
• Meet the elements y in the right subtree of x: key (y) > key (x )

Priorities

Priorities fulfill the properties of the heap. This means:

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

Search for an item

The search is as in a binary search tree. To search for the value k is compared with the value of the root. If k is larger, it compares the value to the next node in the right subtree, if smaller, then the left. Anticipated maturity:

Inserting an element

To insert an element e into a treap, to create a new node x, stores the element e in X.KEY and selects a random priority for x.priority. Now one adds the nodes by means of a X.KEY according to the properties of the binary search tree in the treap. As directed by the new node is now the heap property may be violated, one rotates the node now remain up until the heap condition is satisfied again.

Anticipated maturity: . The expected depth is logarithmic. The expected number of rotations is 2

Removing an element

• One seeks the position of the node to remove x in the tree
• You change the priority to ∞ (infinity)
• It rotates to the node being removed towards the side where the smaller priority until the heap condition is satisfied
• The element is now a sheet, and can be deleted

Anticipated maturity: . The expected depth is logarithmic. The number of expected rotations is 2

Find smallest / largest element

Because the elements are stored in a treap in the order of a normal binary search tree, the smallest element is the lower left corner, and to find the largest element in the bottom right. Thus one has to find the smallest element, always descend into the left subtree, and to find the largest element always stay in the right subtree

Anticipated maturity: as the expected depth is logarithmic.

List all items

• Returns all elements into ascending order
• If by the in - order traversal performed (between the two subtrees )

Running time is.