Treap data structure is a Cartesian tree in which each key is given a (randomly chosen) numeric priority described by Raimund Seidel and Cecilia R. Aragon in 1989.
In this tutorial, we will learn about the Treap data structure and how to implement a Treap in javascript.
What is Treap data structure?.
A Treap data structure is a Balanced Binary Search Tree, which combines the best of both the heaps and binary search trees, but not guaranteed to have height as O(Log n).
It store two values.
1. A key (Ordered according to the BST property).
2. And a randomly chosen numeric priority (A random value ordered according to max-heap property).
The structure of the tree is determined by the requirement that it be heap-ordered: that is, the priority number for any non-leaf node must be greater than or equal to the priority of its children.
It is often considered as a good platform to build the randomized binary search tree.
List of operations performed on treap.
- insertNode(key):- Adds a new node with random priority.
- deleteNode(key):- Removes a node with the given key.
- searchNode(key):- Returns true if key is present in the treap, false otherwise.
- printTreap:- Prints the node in the BST order.
Implementing treap data structure in Javascript.
We will need to helper functions in-order to implement a treap rotateLeft, rotateRight which reverses the parent-child relation.
Base structure
//Generates a random number
const getRandom = (max, min = 1) => {
return Math.floor((Math.random() * (max - min + 1)) + min);
}
const Treap = function() {
//Node with priority
const Node = function(data){
this.data = data;
this.priority = getRandom(100);
this.left = this.right = null;
}
//To store the root
let root = null;
const rotateLeft = function(root) {
const R = root.right;
const X = root.right.left;
// rotate
R.left = root;
root.right = X;
// set new root
return R;
}
const rotateRight = function(root) {
const L = root.left;
const Y = root.left.right;
// rotate
L.right = root;
root.left = Y;
// set new root
return L;
}
//Other methods will go here
}
Insert operation on the treap.
To insert a key in the treap, create a new node with random priority and add it at the leaf position using the BST property to determine its initial position and then if the new node is not the root and has greater priority value than the parent then perform the tree rotation, to reverse its position with the parent.
// Recursive function to insert a given key with a priority into Treap
this.insertNode = function(data) {
const insertNodeHelper = (root, data) => {
// base case
if (root === null) {
return new Node(data);
}
// if data is less than the root node, insert in the left subtree
// else insert in the right subtree
if (data < root.data) {
root.left = insertNodeHelper(root.left, data);
// rotate right if heap property is violated
if (root.left != null && root.left.priority > root.priority) {
root = rotateRight(root);
}
}
else {
root.right = insertNodeHelper(root.right, data);
// rotate left if heap property is violated
if (root.right != null && root.right.priority > root.priority) {
root = rotateLeft(root);
}
}
return root;
}
root = insertNodeHelper(root, data);
}
Delete operation on treap.
To remove a node with given key from the treap we have to check for the following conditions.
- If the node is the leaf then remove it.
- If the node has only single child then remove the node and replace its position with its child.
- In case node has two child, swap its position in the tree with its immediate successor in the sorted order, resulting in one of the previous cases. Swapping may disrupt the heap-order priority, so we need to perform additional rotations to restore the property.
// Recursive function to delete a key from the given Treap
this.deleteNode = function(key) {
const deleteNodeHelper = (root, key) => {
// base case: key not found in tree
if (root === null) {
return null;
}
// if key is less than the root node, recur for left subtree
if (key < root.data) {
root.left = deleteNodeHelper(root.left, key);
}
// if key is more than the root node, recur for right subtree
else if (key > root.data) {
root.right = deleteNodeHelper(root.right, key);
}
// if key found
else
{
// Case 1: node to be deleted has no children (it is a leaf node)
if (root.left == null && root.right == null)
{
// deallocate the memory and update root to null
root = null;
}
// Case 2: node to be deleted has two children
else if (root.left != null && root.right != null)
{
// if left child has less priority than right child
if (root.left.priority < root.right.priority)
{
// call rotateLeft on root
root = rotateLeft(root);
// recursively delete the left child
root.left = deleteNodeHelper(root.left, key);
}
else
{
// call rotateRight on root
root = rotateRight(root);
// recursively delete the right child
root.right = deleteNodeHelper(root.right, key);
}
}
// Case 3: node to be deleted has only one child
else
{
// find child node
const child = (root.left != null) ? root.left: root.right;
root = child;
}
}
return root;
}
root = deleteNodeHelper(root, key);
}
Search operation in treap
To search a key, we can use the standard search operation of BST, ignoring the priority.
// Recursive function to search for a key in the given Treap
this.searchNode = function(key) {
const searchNodeHelper = (root, key) => {
// if key is not present in the key
if (root === null) {
return false;
}
// if key is found
if (root.data == key) {
return true;
}
// if key is less than the root node, search in the left subtree
if (key < root.data) {
return searchNodeHelper(root.left, key);
}
// else search in the right subtree
return searchNodeHelper(root.right, key);
}
return searchNodeHelper(root, key);
}
Print operation on treap.
Print the nodes in the BST order.
this.printTreap = function() {
const printTreapHealper = (root) => {
// Base case
if (root === null) {
return;
}
// print right child first
printTreapHealper(root.right);
console.log(root.data + "(" + root.priority + ")");
// print left child
printTreapHealper(root.left);
}
printTreapHealper(root);
}
}
Complete code of Treap data structure in Javascript.
const getRandom = (max, min = 1) => {
return Math.floor((Math.random() * (max - min + 1)) + min);
}
const Treap = function() {
const Node = function(data){
this.data = data;
this.priority = getRandom(100);
this.left = this.right = null;
}
let root = null;
const rotateLeft = function(root) {
const R = root.right;
const X = root.right.left;
// rotate
R.left = root;
root.right = X;
// set new root
return R;
}
const rotateRight = function(root) {
const L = root.left;
const Y = root.left.right;
// rotate
L.right = root;
root.left = Y;
// set new root
return L;
}
// Recursive function to insert a given key with a priority into Treap
this.insertNode = function(data) {
const insertNodeHelper = (root, data) => {
// base case
if (root === null) {
return new Node(data);
}
// if data is less than the root node, insert in the left subtree
// else insert in the right subtree
if (data < root.data) {
root.left = insertNodeHelper(root.left, data);
// rotate right if heap property is violated
if (root.left != null && root.left.priority > root.priority) {
root = rotateRight(root);
}
}
else {
root.right = insertNodeHelper(root.right, data);
// rotate left if heap property is violated
if (root.right != null && root.right.priority > root.priority) {
root = rotateLeft(root);
}
}
return root;
}
root = insertNodeHelper(root, data);
}
// Recursive function to search for a key in the given Treap
this.searchNode = function(key) {
const searchNodeHelper = (root, key) => {
// if key is not present in the key
if (root === null) {
return false;
}
// if key is found
if (root.data == key) {
return true;
}
// if key is less than the root node, search in the left subtree
if (key < root.data) {
return searchNodeHelper(root.left, key);
}
// else search in the right subtree
return searchNodeHelper(root.right, key);
}
return searchNodeHelper(root, key);
}
// Recursive function to delete a key from the given Treap
this.deleteNode = function(key) {
const deleteNodeHelper = (root, key) => {
// base case: key not found in tree
if (root === null) {
return null;
}
// if key is less than the root node, recur for left subtree
if (key < root.data) {
root.left = deleteNodeHelper(root.left, key);
}
// if key is more than the root node, recur for right subtree
else if (key > root.data) {
root.right = deleteNodeHelper(root.right, key);
}
// if key found
else
{
// Case 1: node to be deleted has no children (it is a leaf node)
if (root.left == null && root.right == null)
{
// deallocate the memory and update root to null
root = null;
}
// Case 2: node to be deleted has two children
else if (root.left != null && root.right != null)
{
// if left child has less priority than right child
if (root.left.priority < root.right.priority)
{
// call rotateLeft on root
root = rotateLeft(root);
// recursively delete the left child
root.left = deleteNodeHelper(root.left, key);
}
else
{
// call rotateRight on root
root = rotateRight(root);
// recursively delete the right child
root.right = deleteNodeHelper(root.right, key);
}
}
// Case 3: node to be deleted has only one child
else
{
// find child node
const child = (root.left != null) ? root.left: root.right;
root = child;
}
}
return root;
}
root = deleteNodeHelper(root, key);
}
// Utility function to print two-dimensional view of a Treap using
// reverse inorder traversal
this.printTreap = function() {
const printTreapHealper = (root) => {
// Base case
if (root === null) {
return;
}
// print right child first
printTreapHealper(root.right);
console.log(root.data + "(" + root.priority + ")");
// print left child
printTreapHealper(root.left);
}
printTreapHealper(root);
}
}
Input:
const arr = [5, 2, 1, 4, 9, 8, 10];
const treap = new Treap();
for(let val of arr){
root = treap.insertNode(val);
}
treap.printTreap();
root = treap.deleteNode(1);
console.log(" ");
console.log(treap.searchNode(8));
console.log(" ");
treap.printTreap();
Output:
"10(9)"
"9(71)"
"8(5)"
"5(21)"
"4(62)"
"2(8)"
"1(25)"
" "
true
" "
"10(9)"
"9(71)"
"8(5)"
"5(21)"
"4(62)"
"2(8)"
Time complexity of treap data structure
| # | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Average | ΘLog(N) | ΘLog(N) | ΘLog(N) | ΘLog(N) |
| Worst | OLog(N) | OLog(N) | OLog(N) | OLog(N) |
Space complexity
| # | Space |
|---|---|
| Worst | N |