# Treaps

Authors: Benjamin Qi, Dustin Miao

A randomized binary search tree

Resources | ||||
---|---|---|---|---|

GCP | Splitting and merging with code | |||

cp-algo | Description and code | |||

Algorithm Tutorial | Code and diagrams | |||

Benq | Description of Split and Merge | |||

CF | Proof of time complexity for merging treaps |

## Treaps

Like a regular binary search tree, treaps contain keys that can be inserted, erased, and searched for in $\mathcal{\Theta}(\log n)$. However, regular binary search trees suffer from imbalancing, which causes the tree to have up to an $\mathcal{O}(n)$ depth and blows up the time complexity.

A treap is a randomized binary search tree that stores two numbers in its nodes: a value and a priority. The values of a treap will satisfy the binary search tree property (where all the nodes in the left subtree are strictly smaller than the current node and all the nodes in the right subtree are strictly greater than the current node), and the priorities will satisfy the heap property (where all descendants of a node will have smaller or equal priorities).

Treaps have two main operations: splitting and merging. Other operations like insert, erase, and searching can be implemented in terms of these operations.

### Splitting

The `split`

method takes in a pointer to the root of a treap $\texttt{root}$ and
a value $x$, and returns two treaps denoted as $\texttt{left}$ and
$\texttt{right}$. Like the name suggests, it splits the tree such that all nodes
in $\texttt{left}$ have keys less than or equal to $x$ and all nodes in
$\texttt{right}$ have keys greater than $x$.

We can now implement it recursively. Let the left child of a node $n$ be denoted as $n.\texttt{left}$ and the right child as $n.\texttt{right}$.

- If $\texttt{root} \leq x$, then both the root and the left subtree belong to $\texttt{left}$. We now consider a call to
`split`

on $\texttt{root.right}$ and note its results as $\texttt{left'}$ and $\texttt{right'}$. Finally, $\texttt{left}$ contains $\texttt{left'}$ and $\texttt{right} = \texttt{right'}$. - If $\texttt{root} > x$, then both the root and the right subtree belong to $\texttt{right}$. We now consider a call to
`split`

on $\texttt{root.left}$ and note its results as $\texttt{left'}$ and $\texttt{right'}$. Finally, $\texttt{right}$ contains $\texttt{right'}$ and $\texttt{left} = \texttt{left'}$.

### Merging

The `merge`

method inverts the `split`

method by taking in two treaps
$\texttt{left}$ and $\texttt{right}$ and returns a single treap that has the
nodes of both treaps. It works under the assuption that all keys
$x \in \texttt{left}$ are strictly smaller than all keys $y \in \texttt{right}$.
Furthermore, we need to merge these two treaps such that the resultant treap
still satisfies the max heap property.

We root the resultant treap at the root node that has the higher priority, and
recursively call `merge`

on the other tree and the corresponding subtree of the
chosen tree.

### Implementation

C++

#include <stdlib.h>struct Node {// the value and priority of the node respectivelyint val, pri;// pointer to left and right child (NULL means no child)Node *left, *right;Node(int val) : val(val), pri(rand()), left(NULL), right(NULL) { };} *root;

### Optional

For speed / memory, use arrays of fixed size rather than pointers.

## Implicit Treaps

Focus Problem – read through this problem before continuing!

In their most basic form, treaps are not very useful (languages like C++ and Java already have a built-in self-balancing binary tree that is much more efficient than treaps). However, with implicit treaps, we can efficiently perform operations on a regular array in fashion similar to segment trees and fenwick trees. The following operations are supported by implicit treaps:

- Insert an element $x$ at position $i$
- Delete the element at position $i$
- Performing interval queries (sum, min, max, etc.)
- Perform interval updates (add, set, reverse, etc.)

The key behind implicit treaps lies in their name. We will use the index of the node to be its key. Because maintaining this value explicitely will result in up to $\mathcal{O}(n)$ values to be updated per insertion/deletion, we will keep this value implicitly.

The index of a node is equal to the number of nodes less than it. It is important to note that these nodes can occur both in the left subtree of the current node as well as the node's ancestors and the left subtree of its ancestors.

Note that in an implicit treap, the merge function is largely unchanged because it does not depend on the key. In the split operation we go from the root down, so we simply maintain a running count of the size left subtree.

An implementation of the split operation may look something like:

C++

void split(Node *treap, Node *&left, Node *&right, int val, int add = 0) {if (!treap) {left = right = NULL;return;}int cur_size = add + size(treap->left); //implicit keyif (cur_size < val) {split(treap->right, treap->right, right, key, add + 1 + size(treap->left));left = treap;

In the split operation, because we are always comparing $\texttt{cur\_size}$ to $\texttt{val}$, we can simply eliminate the $\texttt{add}$ parameter by subtracting from $\texttt{val}$ each time. Our new code looks like:

C++

void split(Node *treap, Node *&left, Node *&right, int val) {if (!treap) {left = right = NULL;return;}if (size(treap->left) < val) {split(treap->right, treap->right, right, val - size(treap->left) - 1);left = treap;} else {split(treap->left, left, treap->left, val);right = treap;}treap->size = 1 + size(treap->left) + size(treap->right);}

### Implementation

C++

struct Node {int val;int weight, size;Node *left, *right;Node(int c) : val(c), weight(rand()), size(1), left(NULL), right(NULL) {}} *root;int size(Node *treap) {return treap ? treap->size : 0;}

With split and merge, how do we implement the additional operations?

**Insert**can be done with one split and two merges: We split the array between the index we want to insert, create a new node with the corresponding value, and merge the three sections together.**Delete**can be done with two splits and one merge: We split the array into three parts before and after the index, and merge the two parts together.**Range queries**can be performed by maintaining additional data in each node. We update this data whenever we update $\texttt{size}$.**Range updates**can be performed by maintaining a lazy tag in each node (as in lazy propogation). When splitting or merging, we push these tags downwards and perform the corresponding operation.

### Cut and Paste - Solution

We will use implicit treaps to represent the array. For each operation, divide it into two phases: cut and paste. For the cut phase, we split the array into three parts: $[1, a)$, $[a, b]$, and $(b, n]$. This can be accomplished using two split operations. For the paste phase, we can rearrange the sections such that we merge them in the order $[1, a)$ $(b, n]$ $[a, b]$. This can be done using two merge operations.

C++

#include <bits/stdc++.h>using namespace std;struct Node {char val;int weight, size;Node *left, *right;Node(char c) : val(c), weight(rand()), size(1), left(NULL), right(NULL) {}} *root;

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

POI | Normal |

### This section is not complete.

- Add merging treaps
- Format problems

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!