--- title: "Treap: The Easiest Search Tree (Explained)" slug: "treap-algorithm-explained" date: "2022-04-25T04:00:00.000Z" description: "Binary search trees are mostly hard. Writing red-black tree is a nightmare. Here, I'm going to explain one of the easiest, yet efficient and powerful balanced binary tree — treap or cartesian tree" --- # Treap: The Easiest Search Tree (Explained) **Cartesian tree or treap** (binary search tree + binary heap) is a fast yet simple data structure. It conforms to a core search binary tree property and binary heap property at the same time. Despite its simplicity, treap self-balances, resulting in `O(logn)` complexity on average for all common operations. Amazing, right? 💥 The algorithm uses random values. Therefore, `O(logn)` complexity is ****on average****. However, with a lot of items `O(logn)` is almost always true. So, later in this article, I will use just `O(logn)` without "on average" addition. Moreover, there is a modification (implicit treap, treap with implicit key) that lets you use treap as a usual array with `O(logn)` **random insertions and** **random deletions**. Isn't it cool? In this article I'll explain how to create one and provide the implementation in Swift. Also, I will compare treap to the general `set` from standard library. Let's start! 💡 In a binary search tree, for each node, all items' values in the left subtree are less than the node's value, and all items in the right subtree are greater ## Core algorithm As I said earlier, treap combines heaps and binary search trees. Therefore, we are going to store at least two properties: `key` (or value) and `priority`. Key is a value for which tree is a search tree and for the priority, it is a binary heap. 💡 A binary heap is a binary tree where each node child's value is less than the node's value ![](https://alexdremov.me/content/images/2022/04/treap.png) Treap example On the image above, you may notice that for every node, all child's priorities are less. On the other side, all children on the left have a key less than that in the node, and all children on the right have a larger key. 💡 It's also called a ****cartesian tree**** as it can be displayed on a regular 2D grid with (key, priority) coordinate for each node. Just like in the image above. To create a fully-functioning search tree, we need to implement: * find * insert * remove More exotic operations like `lower bound` and `upper bound` are also pretty simple and does not differ from those in the other search trees. And all these operations can be implemented using **just two helper operations**! How to do that? 💥 ****Split**** Splits the tree into two trees by given `value`. All values in the left tree are ****less**** than the `value` while in the right tree are ****greater****. And both resulting trees are correct treaps. We will use a special flag that decides whether to send values that are equal to the left tree or to the right tree. ![Example of split function result. The equal value sent to the right](https://alexdremov.me/content/images/2022/04/split-image-1.png) Example of split function result. The equal value sent to the right 💥 ****Merge**** Merges two treaps into one big treap. ****Prerequisite:**** all items in the first tree are less than items in the right tree. ![Treap merge example](https://alexdremov.me/content/images/2022/04/merge-example.png) Merge example So, if we implement these two methods, implementing all other three operations would be trivial. ## Split Let's start thinking about code at this stage. I'm going to explain this in `C++`. Rewriting the following code in `Swift` is actually really easy. Leave a comment bellow if you need a help. ```cpp template struct Node { T key; size_t prior; Node* left = nullptr, *right = nullptr; Node(T key, size_t prior) : key(std::move(key)), prior(prior) { } }; ``` Structure of treap's node For split, we have a `head` node and a `key` for which split needs to be done. This method is extremely simple using recursion. ### Algorithm Let the current head be `p`. * If `p->key` is **less than** the `key`, then we need to go **right** and split `p->right` further. Also, splitting `right` will bring two trees as well, and the first one will have nodes with keys **less** than the `key`. Yet, they are greater than the `p->key` (as they are in the second tree of the first split). So, we set `p->right` to the **first** tree of splitting `right` result. **Result:** `p`, split right's second tree * If the `p->key` is **greater or equal** to the `key`, then we need to go **left** and split `p->left` further. Similarly to the case above, we set `p->left` to the **second** tree of split left. **Result:** split left's first tree, `p` The algorithm above leaves a node that is equal to the split value in the second tree. Symmetrically, we will use the `equalOnTheLeft` flag to leave the node in the left tree. So, the final code: ```cpp pair split (Node *p, const T& key, bool equalOnTheLeft=false) { if (!p) // reached leaf return {nullptr, nullptr}; if (p->key < key || (equalOnTheLeft && p->key == key)) { // splitting right auto q = split(p->right, key, equalOnTheLeft); // q.first has nodes of the right // subtree that are less than key p->right = q.first; return {p, q.second}; } else { // splitting left auto q = split(p->left, key, equalOnTheLeft); // q.second has nodes of the left // subtree that are greater or equal // to the key p->left = q.second; return {q.first, p}; } } ``` 💡 Priorities are not used and not changed during the split procedure. The resulting trees have the right order of priorities as the initial tree had it right Subscribe and don't miss posts! ## Merge Merge is similar to split, but it uses **priorities** to do the work. As I mentioned before, there is a **prerequisite**: all items in the first merged tree must be less than items in the second tree. If this is not true, another algorithm must be used. ### Algorithm Similarly to `split`, `merge` is also recursive. Let us have two trees to merge: `l` and `r`. * We need to choose which tree will represent the new head. That's simple — the head must have the greatest priority, so we choose `l` or `r` based on that. 💡 Notice that the head node in `l` has the highest priority in the whole `l` tree as its a property of correct treap. The same applies to `r`. * If `l` has greater priority, then `l->left` subtree will remain intact as left subtree for sure less than `r` and it has nothing to do with it. Then, `l->right` subtree must be merged with `r` and it's going to be the new `l->right` subtree. * If `r` has greater priority, then, similar to the example above, `r->right` will remain intact and `r->left` must be merged with `l` ```cpp Node* merge (Node *l, Node *r) { if (!l) // left is empty return r; if (!r) // right is empty return l; if (l->prior > r->prior) { // l has the new head. l->right = merge(l->right, r); return l; } else { // r has the new head. r->left = merge(l, r->left); return r; } } ``` Why is it correct? It seems like nothing stops us from breaking the search tree structure where all items' values in the left subtree are less than the node's value, and all items in the right subtree are greater. 💡 ****Prerequisite**** saves binary search tree property as items are never reordered and `l < r` property is always kept the same ## Implementing search tree methods You believed me that all methods are easy to implement through `split` and `merge`. Time to prove that. ### Find Find is implemented just like for the general search tree. We use the fact that keys in the left subtree are greater than the value in the node. ```swift Node* find(Node* node, const T& key) { if (node == nullptr) return nullptr; if (node->key == key) return node; return find(key >= node->key ? node->right : node->left, key); } ``` ### Insert Let's think about insert in terms of split and merge. We have one big tree and we need to insert a new `key`. * Split the tree by `key` to new trees: `first` and `second`. Then, we will have two trees: the first (which has values lower than the `key`) and the second (which has values greater or equal to the `key`). We can check that node already exists: try to find it in the right tree. 💥 Implementation requires that each item is met only ****once****. If you need to insert multiple copies of the same item, you can store an item and it's count to achieve that * Create a new node that will store the new `key` — `newNode`. Ta-da this node is a correct treap that has only one node. For the new node, you need to set **a random priority** 💥 ****Random priorities**** are key to the complexity. This makes the cartesian tree balance itself, making `O(logn)` complexity for all operations * New head will be `merge(first, merge(newNode, second))` See? It's that simple. ![Insert example](https://alexdremov.me/content/images/2022/04/merge-example-specific.png) Insert example ```cpp Node* insert(Node* head, T key) { auto split = split(head, key); if (find(split.second, key) != nullptr) { // Key exists already // Merge back return merge(split.first, split.second); } auto newNode = new Node(std::move(key), rand()); return merge(split.first, merge(newNode, splitsplitted.second)); } ``` ### Remove It's very similar to `insert`. However, that's where the `equalOnTheLeft` flag is used. 💡 Remember that the `second` tree produced by `split` contains items greater or ****equal**** to the selected key Therefore, the `second` tree will contain the value that needs to be removed. But how to remove it from the tree? Split again. We can split the `second` tree by key, setting the `equalOnTheLeft` flag to `true`. Thus, the node will be separated from the `second` tree to the new tree. 💡 After conducting two splits and separating deleted node, unneded node is easely removed everything else is merged. ![Remove example](https://alexdremov.me/content/images/2022/04/remove-example.png) Remove example ```cpp Node *remove(Node *head, const T &key) { auto split = split(head, key); if (split.second) { auto secondSplit = split(split.second, key, /*equalOnTheLeft=*/true); // Key exists, so delete it and merge auto everythingElse = secondSplit.second; if (secondSplit.first == nullptr) { // There's no element equal to key. Merge back. return merge(split.first, everythingElse); } // We got node with key value in // secondSplit.first delete secondSplit.first; size--; return merge(split.first, everythingElse); } // Key is not presented. Merge back. return merge(split.first, split.second); } ``` ## Full code You can download C++ code of a little bit optimized Treap here: [ Treap C++ code allocations-optimised treap.h 5 KB download-circle ](https://alexdremov.me/content/files/2022/04/treap.h "Download") ## Comparing to `std::set` First of all, the implemented version of treap utilizes `split` and `merge` methods. Note that there is more efficient implementation that uses rotations. However, the true power of treap is in `split` and `merge` methods as other search trees can't do it easily. ### Find tests ![Find operation test](https://alexdremov.me/content/images/2022/04/find-3.svg) Find operation test It's visible that asymptotics is similar. Though, treap always has the greater overhead. Still, it's a good result! We're competing with an utterly optimized standard library data structure. ### Inserts ![](https://alexdremov.me/content/images/2022/04/insert.svg) Insert operation test Insertion has even bigger overhead. And it was expected: recursive calls of merge and split do not improve performance ;) [ TreapProject Comparisons tests. Outputs CSV of time measurments TreapProject.zip 7 KB download-circle ](https://alexdremov.me/content/files/2022/04/TreapProject-1.zip "Download") ### Comparison conclusion ![Height of treap evaluation](https://alexdremov.me/content/images/2022/04/height50m-1.svg) As you see, treap has higher nodes' height on average than that of very well-balanced AVL tree. Yes, treap has worse performance than that of `std::set`. Yet, the results are comparable, and with a large data size, treap gets closer and closer to `std::set` which in fact is a red and black tree. Believe me, **you don't want to write your own RB tree**. It's a nightmare. ## Use cases and modifications We developed this data structure not just to lose `std::set`. There are several useful applications. ### Sum of numbers in the interval We need to modify `Node` structure, adding `sum` field. It will store sum of all its children and itself. ```cpp template struct Node { T key; size_t prior; long long sum; Node* left = nullptr, *right = nullptr; Node(T key, size_t prior) : key(std::move(key)), prior(prior) { } }; ``` It's extremely easy to update the `sum`. Every time childs are changed, `sum = left->sum + right->sum`. So, you can implement some kind of `update` function and call it in split and merge right before returning value. That's it. How to answer on request? We receive interval `[l, r]`. To calculate the sum of numbers on this interval, we can split the tree by `l`, then split the second tree of the result by `r+1` (or by `r`, leaving equal elements on the left). In the end, we will have a tree containing all added numbers in the interval `[l, r]`. **Complexity:** `O(logn)` versus `O(n)` naive. ### Using a hash of value in place of priority You can use a hash of value as a priority as a good hash function is pretty random. What benefits does it bring? If keys and priorities are fixed, then no matter how you construct the treap or add elements, it's always going to have the same structure. 💡 You may think about it this way: keys fix x axis and priorities fix y axis of treap Therefore, you can compare two sets in `O(n)` as treaps containing the same values will have **absolutely the same structure.** ## Implicit treap What if we use **the size of the left subtree** as a key? Then, we can use this key as an index. Wow. That means that we can represent a regular ordered array as a treap! By doing this, we can: * make insertions by random index `O(logn)` versus `O(n)` naive * make deletions by random index `O(logn)` versus `O(n)` naive With great power, comes great responsibility. 😡 Access by random index downgrades to `O(logn)` versus `O(1)` in the standard array. If your algorithm requires a lot of array modifications and very few accesses/outputs, then it's the right choice. Moreover, you can convert treap into an array and back with `O(n)` complexity. 💥 I have implicit treap implemented in ****Swift****. It behaves just like the general array and implements a lot of optimisations. Check it out! [ swift-collections/Sources/OrderedCollections/TreeArray at main · AlexRoar/swift-collections Commonly used data structures for Swift. Contribute to AlexRoar/swift-collections development by creating an account on GitHub. ![](https://github.com/fluidicon.png)GitHubAlexRoar ![](https://opengraph.githubassets.com/49005a356ceb6b3993976514f19972ef42448ba48f43e8a30af9ce7834af1d0a/AlexRoar/swift-collections) ](https://github.com/AlexRoar/swift-collections/tree/main/Sources/OrderedCollections/TreeArray) ### Cut-paste problem Imagine that you have a big string and you recieve requests to cut some part and to insert it somwhere. This problem can be solved using treaps with implicit key. You can use splits to cut needed part and merge to insert it. ### Union algorithm We can define **Union** algo as a method that merges two treaps when relation between elements in trees is not known. The Union algorithm relies on a divide-and-conquer approach. It compares the roots of the two treaps, selects the node with the higher priority to be the new root, and uses a `split` operation on the second treap based on the new root's key. It then recursively unites the left and right subtrees. This recursive method is significantly more efficient than the naive `O(M log(N))` approach of inserting elements one by one, and it elegantly degrades to an expected `O(n)` time when both treaps are of roughly equal size. So, step by step: * **Handle Base Cases.** If either treap is empty, return the other treap. If both are empty, return null. * **Determine the New Root.** Compare the heap priority values of the roots of both treaps. Let `T1` be the treap whose root has the higher priority, and `T2` be the other treap. The root of `T1` (let's call it `R1`) will become the root of the new united treap to preserve the heap property. * **Split the Second Treap.** Perform a standard `split` operation on `T2` using the key of `R1` as the splitting threshold. This divides `T2` into two distinct sub-treaps: * `**L2**`: Contains all nodes from `T2` with keys less than `R1`'s key. * `**R2**`: Contains all nodes from `T2` with keys greater than `R1`'s key. * **Recursively Unite Subtrees.** Recursively call the Union algorithm to construct the new left and right subtrees for `R1`: * Set `R1`'s left child to be the result of `Union(T1.left, L2)`. * Set `R1`'s right child to be the result of `Union(T1.right, R2)`. * **Return the United Treap.** Return `R1`. The resulting structure guarantees both the Binary Search Tree property (enforced by the `split` boundary) and the Heap property (enforced by the priority comparison). ## FAQ > Cartesian trees are most suitable for what? Treap is useful when you need to collect some kind of characteristic on an interval (for example, sum) or apply some modification to the interval. Treap with implicit key is also useful when you need to apply a lot of random tree insertions/deletions with few accesses. > Why don't we use array indices as keys for an implicit treap? Because in case of insertion we would need to recalculate all indeces that are higher than inserted index. Therefore, it downgrades complexity to `O(n)`. > Is treap a randomized tree? Yes, it is. But it can also use hash value in place of a random value. > I know about implementation without split and merge. It utilizes left and right turns. Is it better? For example, GeeksforGeeks use such implementation, I know. But I believe that the true value of treap is in seampless splits and merges. You've already seen by examples how it is really usefull. Why implementing treap with turns when you can build AVL that's probably going to be faster? > If merge **prerequisite** that "all items in the first merged tree must be less than items in the second tree" breaks, what is the complexity of merging two treaps? If this condition is violated, merge can no longer be used as it will lead to an invalid tree. Therefore, a **Union** operation must be used. The expected time complexity of the Union operation is `O(M log(N/M + 1))`, where `M` is the number of nodes in the smaller treap and `N` is the number of nodes in the larger one. > What is complexity of merging N treaps? If the `N` treaps have strictly ordered keys, you can apply the standard merge operation. Let `V` represent the total number of nodes across all `N` treaps. Because a single merge takes `O(log V)`, sequentially merging all `N` treaps will take `O(N log V)` expected time overall. If the keys across the `N` treaps overlap or interleave, the standard merge is invalid and you must use a **Union** approach. By placing all treaps into a queue and repeatedly uniting pairs until only one remains, you do `O(V)` work at each of the `log N` levels of the union tree. This results in an expected time complexity of `O(V log N)` to combine all `N` overlapping treaps. ## Love data structures? Check out my article on the amazing Skip List! While a lot of people never heard about it, Skip List is **beautiful** and can solve, for example, the problem of finding the n-th maximum or the rolling median problem in the most efficient way. [ Skip List Indexation and kth Maximum | Alex Dremov Skip List is a nice structure that lets you to perform insertions, searches, and finding n-th maximum. In this post I fokus on skip list indexation ![](https://alexdremov.me/assets/icons/apple-touch-icon.png)Alex DremovAlex Dremov ![](https://alexdremov.me/content/images/2022/04/--------------2020-11-06---01.51.30.png) ](https://alexdremov.me/skip-list-indexation-and-kth-maximum/) Also, you can check the whole algorithms section of my blog [ Alex Dremov | Algorithms Those are hard! In this section I discuss algorithms that I encountered during work or my college assignments ![](https://alexdremov.me/assets/icons/apple-touch-icon.png)Alex Dremov ![](https://images.unsplash.com/photo-1580777361964-27e9cdd2f838?crop=entropy&cs=tinysrgb&fit=max&fm=jpg&ixid=MnwxMTc3M3wwfDF8c2VhcmNofDZ8fGFsZ29yaXRobXxlbnwwfHx8fDE2NDk1MDYwMDM&ixlib=rb-1.2.1&q=80&w=2000) ](https://alexdremov.me/tag/algorithms/) ## References [ Introduction To Algorithms The first edition won the award for Best 1990 Professional and Scholarly Book in Computer Science and Data Processing by the Association of American Publishers.There are books on algorithms that are rigorous but incomplete and others that cover masses of material but lack rigor. Introduction to Algo… Google Books ![](https://books.google.de/books/content?id=NLngYyWFl_YC&printsec=frontcover&img=1&zoom=1&edge=curl&imgtk=AFLRE73PtOLetmXuVivAcv-TRLkC8fjpuL48GXZzQ576K23NJLUElL93yxbTDC9ES8rz_-HbjeVd9GkteTzhsSnzKtt9jLIQ-vYsdZyiETYa-lk1uLKXz-jXTl2sR8t2kpHJy_777gys) ](https://books.google.de/books?id=NLngYyWFl_YC&pg=PA298&lpg=PA298&dq=treap+algorithm&source=bl&ots=BASmGA8mBd&sig=ACfU3U17YFycVO2ztnR-zjL5yLbhEfv3VQ&hl=en&sa=X&ved=2ahUKEwjxqr_r0qf3AhXD0qQKHcWWDjcQ6AF6BAgyEAM#v=onepage&q=treap%20algorithm&f=false) [ Декартово дерево - Алгоритмика ![](data:image/x-icon;base64,iVBORw0KGgoAAAANSUhEUgAAACAAAAAgCAQAAADZc7J/AAAABGdBTUEAALGPC/xhBQAAACBjSFJNAAB6JgAAgIQAAPoAAACA6AAAdTAAAOpgAAA6mAAAF3CculE8AAAAAmJLR0QA/4ePzL8AAAAJcEhZcwAACxMAAAsTAQCanBgAAAAHdElNRQfjBggQFxAS4ilBAAACgElEQVRIx52VS0iUYRSGn/8fzbxMIYoRKSZKi2wGwo2FxRQZIlGbaGUF0b52LWbTLlx0W7VyEZiBWkE5mraRRrJFRUwolQw6zQTeuoiU423eFuk0M//nhJ7dd+Z7n/8932HOscgIgU0lR/Cxn3LKgGlijDJIkAgJiywhZMujVo0qrsyIa1St8shWFnmp/IooW0TkV6mMYuRVQCv6X6woIK+QQ16vkPP2M/WZICHVpyGEvCb5vE7olH6bEV6l1R4w3RpQkYoVNJcSWHsLIUt+rTpvLOuSELqihAmwKr8sgZBHE2aX5UKoRmNmDxPyCBtoodLU1m5yaADC9Jr7XkkLoCqNmPAx1eqqnqhAqEHfzB5GVGXTQLUJ/5xZznGcOuAtQbOHahpsfOQ5f5mng8McZAdnsVigkyUTIA8fGjZ561OpuiRJY6oR2qU35iKGbSqc4GU6qObYmstmYIrH5iIq0JIT+17lupU8BVUsVKsvJgdLtgnbxXZOJ091HAU+0W+0YCnGnvRUlCa+42OdbRHiA3CSbtyZ+q85RDMBfcxxjZKUf5uPO4wwzGsaMwFR1JZe1Jx8uuB4mBtC6LJzXLTZDLKYihziM+fJzfjQGfYC/XxMTy8yaDNEOLWBDznAIcdT7aMRiPI0PR1myGacnn+Zd7ygiUIHwEUjuUAnsdR0D+M20E7k7/knt5ki39guN9uAEPeIr6citIPrOsxQiC9hveIuLylkkgXyKUsR/2CAB8yyEzdhJiliN3aCmzwCCwSl3FfzDL9wYZFAuClJAcSZJoELALFKAWVYvVxkdm3NbDRUs0TqUM021jeU15s2w9YXSxKy9dWWRGx6uVpOyObW+x/B+LEV0hF3cAAAACV0RVh0ZGF0ZTpjcmVhdGUAMjAxOS0wNi0wOFQxNjoyMzoxNiswMjowMLEfSBUAAAAldEVYdGRhdGU6bW9kaWZ5ADIwMTktMDYtMDhUMTY6MjM6MTYrMDI6MDDAQvCpAAAAV3pUWHRSYXcgcHJvZmlsZSB0eXBlIGlwdGMAAHic4/IMCHFWKCjKT8vMSeVSAAMjCy5jCxMjE0uTFAMTIESANMNkAyOzVCDL2NTIxMzEHMQHy4BIoEouAOoXEXTyQjWVAAAAAElFTkSuQmCC)Алгоритмика ![](https://hsto.org/storage/habraeffect/a1/0a/a10a744def8f325a1019502ecc175ef6.png) ](https://algorithmica.org/ru/treap) [https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdf](https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdf)