1.  Treaps

• keys {1,...,n}
• priority p(k) Î [0,1] . if k ¹ l then p(k) ¹ p(l)
• T a tree with a key at each node.
• T in heap order = "x,y Î T: x = parent(y) p(x) < p(y)

proof: keys must satisfy in order constraint and heap ordering constraint. $a smallest (heap order) element. This must be the root. Every smaller (by key order) element must be to the left of the root and larger (by key order) elements must be to the right. Now induct ont he left and right subtrees.

2.  Random Treap

A random treap has priorities of each of its elements assigned randomly.

2.1  insert(k)

1. insert k as a leaf
2. pick p(k) randomly
3. rotate k up till you are in heap order

2.2  delete(k)

1. rotate k down to a leaf
2. remove k

2.3  Search(k)

Search(k) is implemented in the same way as for other binary search trees.

2.4  Search Timing analyses

Let:

• C = total number of comparisons
• C⁺ = total number of m>k comparisons
• C^- = total number of m<k comparisons

Break the expected cost of a search is:

E_C(m) = E_C⁺(m)+E_C^-(m)

Consider searching for m+.5 . Then C⁺ will contain elements only from {1,...,m} . and C^- will contain elements only from {m+1,...,n} . The probability that k in C⁺ is chosen will be [1/( m-k+1)] . å_{i = 1}^m[1/( m-i+1)] = Q(ln(m)) . Calculate the contribution from C^- in the same way, then add them together to get E_C(m) = Q(ln(n)) .

2.5  Deletion timing analyses

In order to delete, elements must be rotated to the leaves before removal. The expected number of rotations is less than 2. This can be seen by noting that rotations will follow the left most branch of the right child or the right most branch of the left child, then calculating the odds of a long left most or right most chain. Essentially, the tree is probabilistically ``fat'' in that almost all nodes are near to a leaf.