Treap - Algorithms for Competitive Programming

Last update: October 26, 2026 Translated From: e-maxx.ru Treap (Cartesian tree)¶ A treap is a data structure which combines binary tree and binary heap (hence the name: tree + heap $\Rightarrow$ Treap). More specifically, treap is a data structure that stores pairs $(X, Y)$ in a binary tree in such a way that it is a binary search tree by $X$ and a binary heap by $Y$. If some node of the tree contains values $(X_0, Y_0)$, all nodes in the left subtree have $X \leq X_0$, all nodes in the right subtree have $X_0 \leq X$, and all nodes in both left and right subtrees have $Y \leq Y_0$. A treap is also often referred to as a "cartesian tree", as it is easy to embed it in a Cartesian plane: Treaps have been proposed by Raimund Siedel and Cecilia Aragon in 1989. Advantages of such data organisation¶ In such implementation, $X$ values are the keys (and at same time the values stored in the treap), and $Y$ values are called priorities. Without priorities, the treap would be a regular binary search tree by $X$, and one set of $X$ values could correspond to a lot of different trees, some of them degenerate (for example, in the form of a linked list), and therefore extremely slow (the main operations would have $O(N)$ complexity). At the same time, priorities (when they're unique) allow to uniquely specify the tree that will be constructed (of course, it does not depend on the order in which values are added), which can be proven using corresponding theorem. Obviously, if you choose the priorities randomly, you will get non-degenerate trees on average, which will ensure $O(\log N)$ complexity for the main operations. Hence another name of this data structure - randomized binary search tree. Operations¶ A treap provides the following operations: Insert (X,Y) in $O(\log N)$. Adds a new node to the tree. One possible variant is to pass only $X$ and generate $Y$ randomly inside the operation. Search (X) in $O(\log N)$. Looks for a node with the specified key value $X$. The implementation is the same as for an ordinary binary search tree. Erase (X) in $O(\log N)$. Looks for a node with the specified key value $X$ and removes it from the tree. Build ($X_1$, ..., $X_N$) in $O(N)$. Builds a tree from a list of values. This can be done in linear time (assuming that $X_1, ..., X_N$ are sorted). Union ($T_1$, $T_2$) in $O(M \log (N/M))$. Merges two trees, assuming that all the elements are different. It is possible to achieve the same complexity if duplicate elements should be removed during merge. Intersect ($T_1$, $T_2$) in $O(M \log (N/M))$. Finds the intersection of two trees (i.e. their common elements). We will not consider the implementation of this operation here. In addition, due to the fact that a treap is a binary search tree, it can implement other operations, such as finding the $K$-th largest element or finding the index of an element. Implementation Description¶ In terms of implementation, each node contains $X$, $Y$ and pointers to the left ($L$) and right ($R$) children. We will implement all the required operations using just two auxiliary operations: Split and Merge. Split¶ Split ($T$, $X$) separates tree $T$ in 2 subtrees $L$ and $R$ trees (which are the return values of split) so that $L$ contains all elements with key $X_L \le X$, and $R$ contains all elements with key $X_R > X$. This operation has $O (\log N)$ complexity and is implemented using a clean recursion: If the value of the root node (R) is $\le X$, then L would at least consist of R->L and R. We then call split on R->R, and note its split result as L' and R'. Finally, L would also contain L', whereas R = R'. If the value of the root node (R) is $> X$, then R would at least consist of R and R->R. We then call split on R->L, and note its split result as L' and R'. Finally, L=L', whereas R would also contain R'. Thus, the split algorithm is: decide which subtree the root node would belong to (left or right) recursively call split on one of its children create the final result by reusing the recursive split call. Merge¶ Merge ($T_1$, $T_2$) combines two subtrees $T_1$ and $T_2$ and returns the new tree. This operation also has $O (\log N)$ complexity. It works under the assumption that $T_1$ and $T_2$ are ordered (all keys $X$ in $T_1$ are smaller than keys in $T_2$). Thus, we need to combine these trees without violating the order of priorities $Y$. To do this, we choose as the root the tree which has higher priority $Y$ in the root node, and recursively call Merge for the other tree and the corresponding subtree of the selected root node. Insert¶ Now implementation of Insert ($X$, $Y$) becomes obvious. First we descend in the tree (as in a regular binary search tree by X), and stop at the first node in which the priority value is less than $Y$. We have found the place where we will insert the new element. Next, we call Split (T, X) on the subtree starting at the found node, and use returned subtrees $L$ and $R$ as left and right children of the new node. Alternatively, insert can be done by splitting the initial treap on $X$ and doing $2$ merges with the new node (see the picture). Erase¶ Implementation of Erase ($X$) is also clear. First we descend in the tree (as in a regular binary search tree by $X$), looking for the element we want to delete. Once the node is found, we call Merge on its children and put the return value of the operation in the place of the element we're deleting. Alternatively, we can factor out the subtree holding $X$ with $2$ split operations and merge the remaining treaps (see the picture). Build¶ We implement Build operation with $O (N \log N)$ complexity using $N$ Insert calls. Union¶ Union ($T_1$, $T_2$) has theoretical complexity $O (M \log (N / M))$, but in practice it works very well, probably with a very small hidden constant. Let's assume without loss of generality that $T_1 \rightarrow Y > T_2 \rightarrow Y$, i.

e.

root of $T_1$ will be the root of the result. To get the result, we need to merge trees $T_1 \rightarrow L$, $T_1 \rightarrow R$ and $T_2$ in two trees which could be children of $T_1$ root. To do this, we call Split ($T_2$, $T_1\rightarrow X$), thus splitting $T_2$ in two parts L and R, which we then recursively combine with children of $T_1$: Union ($T_1 \rightarrow L$, $L$) and Union ($T_1 \rightarrow R$, $R$), thus getting left and right subtrees of the result. Implementation¶ struct item { int key, prior; item *l, *r; item () { } item (int key) : key(key), prior(rand()), l(NULL), r(NULL) { } item (int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { } }; typedef item* pitem; This is our item definition. Note there are two child pointers, and an integer key (for the BST) and an integer priority (for the heap). The priority is assigned using a random number generator. void split (pitem t, int key, pitem & l, pitem & r) { if (!t) l = r = NULL; else if (t->key <= key) split (t->r, key, t->r, r), l = t; else split (t->l, key, l, t->l), r = t; } t is the treap to split, and key is the BST value by which to split. Note that we do not return the result values anywhere; instead, the output treaps are written through l and r, for example: pitem l = nullptr, r = nullptr; split(t, 5, l, r); This split function can be tricky to understand, as it has both pointers (pitem) as well as reference to those pointers (pitem &l). Let us understand in words what the function call split(t, k, l, r) intends: "split treap t by value k into two treaps, and store the left treaps in l and right treap in r".

Great!