Treap (A Randomized Binary Search Tree)

Last Updated : 15 Dec, 2022

Like Red-Black and AVL Trees, Treap is a Balanced Binary Search Tree, but not guaranteed to have height as O(Log n). The idea is to use Randomization and Binary Heap property to maintain balance with high probability. The expected time complexity of search, insert and delete is O(Log n).

Every node of Treap maintains two values.
1) Key Follows standard BST ordering (left is smaller and right is greater)
2) Priority Randomly assigned value that follows Max-Heap property.

Basic Operation on Treap:
Like other self-balancing Binary Search Trees, Treap uses rotations to maintain Max-Heap property during insertion and deletion.

T1, T2 and T3 are subtrees of the tree rooted with y (on left side) 
or x (on right side)           
                y                               x
               / \     Right Rotation          /  \
              x   T3   – – – – – – – >        T1   y 
             / \       < - - - - - - -            / \
            T1  T2     Left Rotation            T2  T3
Keys in both of the above trees follow the following order 
      keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)
So BST property is not violated anywhere.

search(x)
Perform standard BST Search to find x.

Insert(x):
1) Create new node with key equals to x and value equals to a random value.
2) Perform standard BST insert.
3) Use rotations to make sure that inserted node's priority follows max heap property.

Delete(x):
1) If node to be deleted is a leaf, delete it.
2) Else replace node's priority with minus infinite ( -INF ), and do appropriate rotations to bring the node down to a leaf.

Refer Implementation of Treap Search, Insert and Delete for more details.

References:
https://en.wikipedia.org/wiki/Treap
https://courses.cs.washington.edu/courses/cse326/00wi/handouts/lecture19/sld017.htm

GeeksforGeeks

Improve

Previous Article

ScapeGoat Tree | Set 1 (Introduction and Insertion)

Implementation of Search, Insert and Delete in Treap

Similar Reads

Implementation of Search, Insert and Delete in Treap

We strongly recommend to refer set 1 as a prerequisite of this post.Treap (A Randomized Binary Search Tree)In this post, implementations of search, insert and delete are discussed.Search: Same as standard BST search. Priority is not considered for search. C/C++ Code // C function to search a given key in a given BST TreapNode* search(TreapNode* roo

Count of array elements that can be found using Randomized Binary Search on every array element

Given an array arr[] of size N, the task is to find the minimum count of array elements found by applying the Randomized Binary Search for each array elements. Examples: Input: arr[] = { 5, 4, 9 } Output: 2 Explanation: Applying Randomized Binary Search for arr[0] in the array. Initially, search space is [0, 2] Suppose pivot = 1 and arr[pivot] <

Randomized Binary Search Algorithm

We are given a sorted array A[] of n elements. We need to find if x is present in A or not.In binary search we always used middle element, here we will randomly pick one element in given range.In Binary Search we had middle = (start + end)/2 In Randomized binary search we do following Generate a random number t Since range of number in which we wan

Complexity of different operations in Binary tree, Binary Search Tree and AVL tree

In this article, we will discuss the complexity of different operations in binary trees including BST and AVL trees. Before understanding this article, you should have a basic idea about Binary Tree, Binary Search Tree, and AVL Tree. The main operations in a binary tree are: search, insert and delete. We will see the worst-case time complexity of t

Binary Search Tree vs Ternary Search Tree

For effective searching, insertion, and deletion of items, two types of search trees are used: the binary search tree (BST) and the ternary search tree (TST). Although the two trees share a similar structure, they differ in some significant ways. FeatureBinary Search Tree (BST)Ternary Search Tree (TST)NodeHere, each node has at most two children. H

Binary Tree to Binary Search Tree Conversion using STL set

Given a Binary Tree, convert it to a Binary Search Tree. The conversion must be done in such a way that keeps the original structure of the Binary Tree.This solution will use Sets of C++ STL instead of array-based solution. Examples: Example 1 Input: 10 / \ 2 7 / \ 8 4 Output: 8 / \ 4 10 / \ 2 7 Example 2 Input: 10 / \ 30 15 / \ 20 5 Output: 15 / \

Minimum swap required to convert binary tree to binary search tree

Given the array representation of Complete Binary Tree i.e, if index i is the parent, index 2*i + 1 is the left child and index 2*i + 2 is the right child. The task is to find the minimum number of swap required to convert it into Binary Search Tree. Examples: Input : arr[] = { 5, 6, 7, 8, 9, 10, 11 } Output : 3 Binary tree of the given array: Swap

Difference between Binary Tree and Binary Search Tree

Binary Tree Data Structure:A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right children. Binary Search Tree Data Structure (BST):A binary search tree is a hierarchical data structure where each node has at most two children, w

Binary Tree to Binary Search Tree Conversion

Given a Binary Tree, convert it to a Binary Search Tree. The conversion must be done in such a way that keeps the original structure of Binary Tree. Examples Example 1Input: 10 / \ 2 7 / \ 8 4Output: 8 / \ 4 10 / \ 2 7Example 2Input: 10 / \ 30 15 / \ 20 5Output: 15 / \ 10 20 / \ 5 30Solution: Following is a 3 step solution for converting Binary tre

Disjoint Set Union (Randomized Algorithm)

A Disjoint set union is an algorithm that is used to manage a collection of disjoint sets. A disjoint set is a set in which the elements are not in any other set. Also, known as union-find or merge-find. The disjoint set union algorithm allows you to perform the following operations efficiently: Find: Determine which set a given element belongs to.

Article Tags :

Practice Tags :

Advanced Data Structure