User:Cdb273/Treap

Analysis Of Operations

The expected time for find, insert and delete operations on a treap is $O(\log n)$. In order to prove this, consider the following lemma:

For an element $x\in S$ of rank $k$, it holds that:

${\text{E}}[{\text{depth}}(x)]=H_{k}+H_{n-k+1}-1$

$H_{k}$ and $H_{n-k+1}$ can be thought of as the expected number of right and left turns, respectively in order to find $x$ starting at the root of the treap. This lemma has the implication that the depth of each element is $O(\log n)$. The proof of this lemma is as follows:

Define:

$S^{-}=\{y\in S\mid y\leq x\}\Rightarrow |S^{-}|=k$ (items less than or equal to x), and

$S^{+}=\{y\in S\mid y\geq x\}\Rightarrow |S^{+}|=n-k+1$ (items greater than or equal to x)

If $Q_{x}$ is the set of values that are ancestors of $x$, then:

$Q_{x}^{-}=S^{-}\cap Q_{x}$, and

$Q_{x}^{+}=S^{+}\cap Q_{x}$

Thus,

${\text{depth}}(x)=Q_{x}=Q_{x}^{+}+Q_{x}^{-}\Rightarrow {\text{E}}[{\text{depth}}(x)]={\text{E}}[Q_{x}^{+}]+{\text{E}}[Q_{x}^{-}]$

Aragon and Seidel make use of Mulmuley Games in order to show that ${\text{E}}[|Q_{x}^{-}|]=H_{k}$ and ${\text{E}}[|Q_{x}^{+}|]=H_{n}+k-1$.

Searching in a Treap

Consider searching for the key $k$, not already in the treap, whose rank in the set $S\cup \{k\}$ is $i$. Let $k_{j}$ be the key in the treap whose rank is $j\in \{S\cup \{k\}\}$, $j\neq i$. The probability that $k_{j}$ is on the search path for $k$ is ${\tfrac {1}{|i-j|}}$.

Expected length of the search path (for all $j$): $\sum _{j=1,2,\ldots ,i-1}{\tfrac {1}{|i-j|}}+\sum _{j=i+1,\ldots ,n}{\tfrac {1}{|i-j|}}\leq H_{n-i+1}+H_{i-1}$

It follows that the expected time to find elements in the treap is $O(\log n)$.

Insertions and Deletions in a Treap

The cost of finding where to insert must be paid, and once found, it must be removed by the use of tree rotations. For insertion, the element is inserted as a leaf, and rotated upward to the correct position in the treap. For delection, it is rotated down to a leaf position, and removed. The number of rotations is equal to:

$|R_{x}|+|L_{x}|$, where $R_{x}$ is the right spine of the left subtree of $x$, and $L_{x}$ is the left spine of the right subtree of $x$

Again, through the use of Mulmuley Games, Aragon and Seidel show that ${\text{E}}[|R_{x}|]=1-{\tfrac {1}{k}}$, ${\text{E}}[|L_{x}|]=1-{\tfrac {1}{n-k+1}}$.

Therefore, ${\text{E}}[|R_{x}|+|L_{x}|]={\text{E}}[|R_{x}|]+{\text{E}}[|L_{x}|]\leq 2$, and the total cost of an insertion or deletion is $O(\log n)$.

Splitting and Merging a Treap

These operations, as described above, involve a single insertion or deletion, and are thus expected to run in $O(\log n)$ time.