Treap (Randomized Binary Search Tree)

beginner
8 min

Treap (Randomized Binary Search Tree)

Welcome to our deep dive into the world of Treaps, a randomized binary search tree! šŸŽÆ This data structure will help us understand how to combine the efficiency of binary search trees with the balance of self-balancing binary search trees like AVL and Red-Black trees. Let's get started!

Table of Contents

  1. Introduction to Treaps
    • Why we need Treaps
    • Key Concepts
  2. Building a Treap
    • Creating a Node
    • Initializing a Treap
  3. Basic Operations
    • Insertion
    • Deletion
    • Searching
  4. Priority and Size
    • Priority and its Importance
    • Updating Priority and Size
  5. Re-balancing
    • Rotations
    • Merging
  6. Advanced Applications and Real-world Examples
    • Treap Median
    • Range Sum Query
  7. Quiz šŸ“

1. Introduction to Treaps

Why we need Treaps

Treaps combine the advantages of both binary search trees (BST) and self-balancing BSTs like AVL and Red-Black trees. BSTs offer fast lookup times, while self-balancing BSTs ensure that the tree remains balanced during insertions and deletions, maintaining a logarithmic time complexity. Treaps, however, provide a simpler solution with a faster rebalancing mechanism.

Key Concepts

  • Randomized Priority: Each node has a random priority. In case of a conflict during re-balancing, the node with a higher priority wins.
  • Size: The number of nodes in a subtree.

2. Building a Treap

Creating a Node

python
class TreapNode: def __init__(self, key, priority, left=None, right=None, size=0): self.key = key self.priority = priority self.left = left self.right = right self.size = size + 1

Initializing a Treap

python
def create_treap(keys): if not keys: return None root = TreapNode(keys[0], random.randint(1, 100000)) for key in keys[1:]: insert(root, key) return root

3. Basic Operations

Insertion

python
def insert(root, key): if not root: return TreapNode(key, random.randint(1, 100000)) if key < root.key: root.left = insert(root.left, key) else: root.right = insert(root.right, key) update_size_and_priority(root) return rebalance(root)

Deletion

python
def remove(root, key): if not root: return root if key < root.key: root.left = remove(root.left, key) elif key > root.key: root.right = remove(root.right, key) else: if root.left is None: return root.right elif root.right is None: return root.left root.key, root.right.key = root.right.key, root.key root.right = remove(root.right, root.key) update_size_and_priority(root) return rebalance(root)

Searching

python
def search(root, key): current = root while current: if current.key == key: return current elif key < current.key: current = current.left else: current = current.right return None

4. Priority and Size

Priority and its Importance

Priority determines the order of nodes during re-balancing. The node with a higher priority has a higher chance of winning.

Updating Priority and Size

python
def update_size_and_priority(node): if node: node.size = node.left.size + node.right.size + 1

5. Re-balancing

Rotations

Treaps use left and right rotations to re-balance the tree.

Merging

When a node is removed, its subtree is merged with the tree.

6. Advanced Applications and Real-world Examples

Treap Median

Treaps can be used to find the median of a set of numbers efficiently.

Range Sum Query

Treaps can also be used to find the sum of numbers in a given range efficiently.

7. Quiz šŸ“

Quick Quiz
Question 1 of 1

What is a Treap?