Treap
Cecilia Aragon and Raimund Seidel, 1989
Background
› A treap is a randomly built binary search tree
› The expected time complexity to insert and remove an item from the treap is O(log n)
› Inspired as a combination of a binary search tree and a binary heap (hence, treap)
Review
› Property of a binary search tree T
For each node p in T, all values in the
1. left subtree of p are less than the value at p.
2. right subtree of p are greater than the value at p.
› Property of a binary heap T
For each node p in T (except the root), the priority at p is less than or equal to the priority of its parent.
Data structure
› Like a binary search tree except each node also contains a random priority
public class Node
{
private static Random R = new Random();
public T Item { get; set; } public int Priority { get; set; } public Node
}
class Treap
{
private Node
… }
Key methods
› void Add (T item)
– inserts item into the treap (duplicate items are not permitted)
› bool Contains (T item)
– Returns true if item is found; false otherwise – Same as the binary search tree
› void Remove (T item)
– Removes (if possible) item from the treap
Support methods
Node
root
X
temp
root
temp
Y
T1 Y X T3 T2 T3 T1 T2
Support methods
Node
temp
X
root
temp
root
Y
T1 Y X T3 T2 T3 T1 T2
Add
› Basic strategy
– Create a node that contains an item and a random priority.
– Add the node to the treap as you would a binary search tree using its item to determine ordering.
– Now, using its random priority, rotate the node (either left or right) up the treap until the parent node has a higher priority or the root is reached.
Consider the following treap
50 0.83
20 0.47
60 Item 0.25 Priority
The treap satisfies the property of a 1. binary search tree using Item
2. binary heap using Priority
10 0.34
40 0.42
30 0.14
Add 15 with priority 0.68
50 0.83
20 0.47
60 0.25
10 0.34
15 0.68
40 0.42
30 0.14
Add 15 with priority 0.68
50 0.83
20 0.47
60 0.25
10
0.34
15
0.68
40 0.42
30 0.14
Add 15 with priority 0.68
50 0.83
20
0.47
60 0.25
15
0.68
40 0.42
10 0.34
30 0.14
Add 15 with priority 0.68
50
0.83
15 Stop!
60 0.25
0.68
10 0.34
20 0.47
The treap still satisfies the property of a 1. binary search tree using Item
2. binary heap using Priority
40 0.42
30 0.14
Add 25 with priority 0.99
50 0.83
15 0.68
60 0.25
10 0.34
20 0.47
40 0.42
30 0.14
25
0.99
Add 25 with priority 0.99
50 0.83
15 0.68
60 0.25
10 0.34
20 0.47
40 0.42
25
0.99
30 0.14
Add 25 with priority 0.99
50 0.83
15 0.68
60 0.25
10 0.34
20 0.47
25
0.99
40 0.42
30 0.14
Add 25 with priority 0.99
50 0.83
15 0.68
60 0.25
10 0.34
25
0.99
20 0.47
40 0.42
30 0.14
Add 25 with priority 0.99
50 0.83
25
0.99
60 0.25
15 0.68
40 0.42
10 2030 0.34 0.47 0.14
Add 25 with priority 0.99 (Final Treap)
25
0.99
15 0.68
50 0.83
0.34 0.47
Yes, the treap still satisfies the property of a 1. binary search tree using Item
2. binary heap using Priority
0.42 0.25
10 20 40 60
30 0.14
Exercises
› Give a sequence n items/priorities that yields a treap with a worst-case depth of n-1.
› Can any sequence of n items yield a treap of depth n-1 for some sequence of random priorities? Argue why or why not.
› Add (35, 0.75) to the final treap.
Remove
› Basic strategy
– Find the node that contains the item to remove.
– Rotate the node with its child with the higher priority. If the left child has the higher priority, rotate right. If the right child has the higher priority, rotate left. Assume that an empty child has an arbitrarily small priority.
– Continue to rotate the node downward in this manner until it is a leaf node. Then simply remove the node (and item).
Remove 50
25 0.99
15 0.68
50
0.83
10 20 40 60
0.34 0.47
0.42 0.25
30 0.14
Remove 50
25 0.99
15 0.68
40 0.42
10 20 30 50 0.34 0.47 0.14 0.83
60
0.25
Remove 50
25 0.99
15 0.68
40 0.42
10 20 30 60
0.34 0.47 0.14
“Snip off” the leaf node
0.25
50
0.83
Remove 50
25 0.99
15 0.68
40 0.42
10 20 30 60 0.34 0.47 0.14 0.25
Remove 25
25
0.99
15
0.68
40 0.42
10 20 30 60 0.34 0.47 0.14 0.25
Remove 25
15 0.68
10 0.34
25
0.99
20
0.47
40 0.42
30 0.14
60 0.25
Remove 25
10 0.34
15 0.68
20 0.47
25
0.99
40
0.42
30 0.14
60 0.25
Remove 25
10 0.34
15 0.68
20 0.47
40 0.42
25
0.99
60 0.25
30
0.14
Remove 25
10 20 0.34 0.47
15 0.68
40 0.42
“Snip off” the leaf node
25
0.99
30 0.14
60 0.25
Final treap
And the treap still satisfies the property of a 1. binary search tree using Item
2. binary heap using Priority
Hooray!
15 0.68
10 0.34
20 0.47
40 0.42
30 0.14
60 0.25
Exercises
› Remove 15 from the final treap.
› Could you use the traditional way of removing a value from a binary search tree and apply it to a treap? Show how.
› Re-implement the Remove method without recursion.
› * Given a treap of height h, provide an example that requires 2h rotations to bring the root of the treap to a leaf position?
Expected time complexity
› The time complexity to Add or Remove an item is O(h) where h is the height of the treap.
– The Add method rotates the inserted item (node) up one level at a time until it reaches the root in the worst case.
– The Remove method may carry out 2h rotations in the worst case to bring the root item (node) to a leaf position (see Exercise).
› Because the treap builds a random binary search tree, the expected height of the tree is O(log n) and therefore, the expected time complexity of Add and Remove is O(log n).