Not Frequent
 0/3

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 Θ(logn)\mathcal{\Theta}(\log n). However, regular binary search trees suffer from imbalancing, which causes the tree to have up to an O(n)\mathcal{O}(n) depth and blows up the time complexity.

Unbalanced Binary Search Tree

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).

Treap

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 root\texttt{root} and a value xx, and returns two treaps denoted as left\texttt{left} and right\texttt{right}. Like the name suggests, it splits the tree such that all nodes in left\texttt{left} have keys less than or equal to xx and all nodes in right\texttt{right} have keys greater than xx.

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

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

Merging

The merge method inverts the split method by taking in two treaps left\texttt{left} and right\texttt{right} and returns a single treap that has the nodes of both treaps. It works under the assuption that all keys xleftx \in \texttt{left} are strictly smaller than all keys yrighty \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 respectively
int 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 xx at position ii
  • Delete the element at position ii
  • 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 O(n)\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 key
if (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 cur_size\texttt{cur\_size} to val\texttt{val}, we can simply eliminate the add\texttt{add} parameter by subtracting from val\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 size\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)[1, a), [a,b][a, b], and (b,n](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)[1, a) (b,n](b, n] [a,b][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

StatusSourceProblem NameDifficultyTags
POINormal

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.
  • 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!