Treap
A treap is a binary search tree that uses randomized priorities to be self-balancing in expectation. It combines properties of binary search trees and heaps.
Java example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Node {
int key, priority, size;
Node left, right;
public Node(int key) {
this.key = key;
priority = rand.nextInt();
size = 1;
}
}
Node insert(Node root, int key) {
if (root == null) {
return new Node(key);
}
if (key < root.key) {
root.left = insert(root.left, key);
} else {
root.right = insert(root.right, key);
}
if (root.left != null && root.left.priority > root.priority) {
// rotate right
}
if (root.right != null && root.right.priority > root.priority) {
// rotate left
}
// update size
return root;
}
|
C++ example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| struct Node {
int key, priority, size;
Node *left, *right;
Node(int k) : key(k) {
priority = rand();
size = 1;
}
};
Node* insert(Node* root, int key) {
if (root == nullptr)
return new Node(key);
if (key < root->key) {
root->left = insert(root->left, key);
} else {
root->right = insert(root->right, key);
}
// rotations, size, etc
return root;
}
|
Python example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| import random
class Node:
def __init__(self, key):
self.key = key
self.priority = random.random()
self.size = 1
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
# rotations, size, etc
return root
|
Treaps provide average O(log n) time for operations with efficient priority-based balancing.
A Treap is a hybrid data structure that combines the properties of a binary search tree (BST) and a heap. In a Treap, each node has a key and a priority. The key follows the rules of a binary search tree, while the priority obeys the heap property. Specifically, keys are ordered just like in a BST, and priorities are organized so that parent nodes have higher priorities than their children. This dual structure guarantees that the Treap is balanced probabilistically, ensuring expected logarithmic time complexity for operations like insert, delete, and search.
Java Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| import java.util.Random;
class Node {
int key, priority;
Node left, right;
public Node(int key) {
this.key = key;
this.priority = new Random().nextInt(100);
}
}
public class Treap {
Node root;
// Right Rotation
public Node rightRotate(Node y) {
Node x = y.left;
y.left = x.right;
x.right = y;
return x;
}
// Left Rotation
public Node leftRotate(Node x) {
Node y = x.right;
x.right = y.left;
y.left = x;
return y;
}
public Node insert(Node root, int key) {
if (root == null) return new Node(key);
if (key <= root.key) {
root.left = insert(root.left, key);
if (root.left.priority > root.priority) {
root = rightRotate(root);
}
} else {
root.right = insert(root.right, key);
if (root.right.priority > root.priority) {
root = leftRotate(root);
}
}
return root;
}
}
|
In Java, we define a Node class with key and priority fields. The Treap class contains methods for right and left rotations, and an insert method that considers both key and priority.
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <cstdlib>
#include <ctime>
struct Node {
int key, priority;
Node *left, *right;
Node(int key) : key(key), priority(rand() % 100), left(nullptr), right(nullptr) {}
};
class Treap {
public:
Node* root;
Node* rightRotate(Node* y) {
Node* x = y->left;
y->left = x->right;
x->right = y;
return x;
}
Node* leftRotate(Node* x) {
Node* y = x->right;
x->right = y->left;
y->left = x;
return y;
}
Node* insert(Node* root, int key) {
if (!root) return new Node(key);
if (key <= root->key) {
root->left = insert(root->left, key);
if (root->left->priority > root->priority) {
root = rightRotate(root);
}
} else {
root->right = insert(root->right, key);
if (root->right->priority > root->priority) {
root = leftRotate(root);
}
}
return root;
}
};
|
In C++, we use a struct for Node and a class for Treap. The logic for rotations and insertions is similar to the Java implementation.
Python Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| import random
class Node:
def __init__(self, key):
self.key = key
self.priority = random.randint(0, 100)
self.left = None
self.right = None
class Treap:
def __init__(self):
self.root = None
def right_rotate(self, y):
x = y.left
y.left = x.right
x.right = y
return x
def left_rotate(self, x):
y = x.right
x.right = y.left
y.left = x
return y
def insert(self, root, key):
if root is None:
return Node(key)
if key <= root.key:
root.left = self.insert(root.left, key)
if root.left.priority > root.priority:
root = self.right_rotate(root)
else:
root.right = self.insert(root.right, key)
if root.right.priority > root.priority:
root = self.left_rotate(root)
return root
|
In Python, the Node and Treap classes are straightforward. The insert method is implemented recursively, just like in the Java and C++ versions.
The treap is useful for situations where you need both map (BST) and priority queue (heap) operations. It’s simple to implement, easy to understand, and the average-case time complexities are quite favorable.