What Is a Treap Data Structure?


Angela Bailey

A treap is a data structure that combines the properties of a binary search tree and a heap. It is an efficient and versatile data structure that provides fast insertion, deletion, and search operations.

Basic Structure

The treap consists of nodes that contain two values: a key and a priority. The key is used to maintain the binary search tree property, while the priority ensures that the tree maintains the heap property.

Each node has two child pointers: left and right. The left child has a key value less than or equal to its parent’s key, while the right child has a key value greater than its parent’s key. This ordering allows for efficient searching within the treap.

The priorities of nodes in the treap are assigned randomly during insertion and maintained such that each node’s priority is greater than or equal to its children’s priorities. This randomization ensures that the treap remains balanced on average.



To insert a new element into the treap, we start by performing a standard binary search tree insertion based on the element’s key. Once we find the appropriate position for insertion, we assign a random priority to the new node and perform rotations if necessary to maintain the heap property.


Deleting an element from the treap involves finding its position based on its key using standard binary search tree deletion. Once found, we remove it from the tree and perform rotations if necessary to restore the heap property.


The treap supports efficient searching operations similar to those of a binary search tree. We compare the Target key with each node’s key starting from the root and move left or right accordingly until we find an exact match or reach a null node.


  • Efficiency: The treap provides fast average-case time complexity for insertion, deletion, and search operations. Its randomization ensures a relatively balanced tree structure.
  • Versatility: The treap can be used in various applications where both ordered and priority-based operations are required. It combines the benefits of binary search trees and heaps.


The treap data structure is a powerful tool that combines the properties of binary search trees and heaps. It offers efficient operations for insertion, deletion, and searching, making it suitable for a wide range of applications. By incorporating both ordered and priority-based operations, the treap provides a versatile solution to many data manipulation problems.

Discord Server - Web Server - Private Server - DNS Server - Object-Oriented Programming - Scripting - Data Types - Data Structures

Privacy Policy