Understanding Treap: A Balanced Tree Explained

A treap combines the binary‑search‑tree property (all keys in the left subtree are smaller than the node’s key, all keys in the right subtree are larger) with the heap property (nodes are ordered by a randomly assigned priority). Each node therefore has two important values: key , which determines its position in the BST, and priority , which determines the heap ordering and keeps the tree balanced.

For example, the keys 2, 3, 4, 5, 6 with priorities 0.6, 0.4, 0.9, 0.3, 0.7 form the following treap:

4(0.9)
     /      \
 2(0.6)    6(0.7)
    \         /
    3(0.4) 5(0.3)

Insertion process

Insert 2(0.6) – becomes the root.

Insert 3(0.4) – placed as the right child of 2; because its priority (0.4) is lower than 2’s (0.6), no rotation is needed.

Insert 4(0.9) – goes to the right of 2 then right of 3. Since 4’s priority (0.9) exceeds both 3’s (0.4) and 2’s (0.6), two left rotations are performed:

First left rotation makes 4 the parent of 3.

Second left rotation lifts 4 to become the root, with 2 as its left child.

Insert 5(0.3) – placed as the right child of 4 because 5 > 4; its priority is the smallest, so it stays there.

Insert 6(0.7) – goes to the right of 4 then right of 5. Since 6’s priority (0.7) is higher than 5’s (0.3), a left rotation around 5 makes 6 the right child of 4.

The final treap after all insertions is:

4(0.9)
    /      \
 2(0.6)   6(0.7)
    \        \
    3(0.4) 5(0.3)

Rotation rules

Left rotation : performed when a node’s right child has a higher priority than the node.

Right rotation : performed when a node’s left child has a higher priority than the node.

Illustrative diagrams:

y                 x
   / \   right →   A   y
  x   C               / \
 A B               B   C

x                y
  / \   left →    x   C
 A   y          / \
    / \       A   B
   B   C

Recursive nature

Each node can be treated as the root of a subtree, so operations such as insertion, deletion, and search are naturally expressed recursively. A recursive call first finds the correct position according to the BST rule, then checks the heap property; if violated, the appropriate rotation restores balance before returning the (possibly new) subtree root.

Python implementation

import random

class TreapNode:
    def __init__(self, key):
        self.key = key
        self.priority = random.random()
        self.left = None
        self.right = None

class Treap:
    def __init__(self):
        self.root = None

    def _rotate_right(self, y):
        x = y.left
        y.left = x.right
        x.right = y
        return x

    def _rotate_left(self, x):
        y = x.right
        x.right = y.left
        y.left = x
        return y

    def insert(self, key):
        self.root = self._insert_recursive(self.root, key)

    def _insert_recursive(self, root, key):
        if root is None:
            return TreapNode(key)
        if key < root.key:
            root.left = self._insert_recursive(root.left, key)
            if root.left.priority > root.priority:
                root = self._rotate_right(root)
        else:
            root.right = self._insert_recursive(root.right, key)
            if root.right.priority > root.priority:
                root = self._rotate_left(root)
        return root

    def inorder(self):
        result = []
        self._inorder_recursive(self.root, result)
        return result

    def _inorder_recursive(self, root, result):
        if root:
            self._inorder_recursive(root.left, result)
            result.append(root.key)
            self._inorder_recursive(root.right, result)

    def search(self, key):
        return self._search_recursive(self.root, key)

    def _search_recursive(self, root, key):
        if root is None or root.key == key:
            return root
        if key < root.key:
            return self._search_recursive(root.left, key)
        return self._search_recursive(root.right, key)

    def delete(self, key):
        self.root = self._delete_recursive(self.root, key)

    def _delete_recursive(self, root, key):
        if root is None:
            return None
        if key < root.key:
            root.left = self._delete_recursive(root.left, key)
        elif key > root.key:
            root.right = self._delete_recursive(root.right, key)
        else:
            if root.left is None and root.right is None:
                return None
            if root.left is None:
                return root.right
            if root.right is None:
                return root.left
            if root.left.priority > root.right.priority:
                root = self._rotate_right(root)
                root.right = self._delete_recursive(root.right, key)
            else:
                root = self._rotate_left(root)
                root.left = self._delete_recursive(root.left, key)
        return root

Example deletion of node 4 (which has two children) triggers a series of rotations to maintain heap order, ultimately re‑balancing the tree as shown in the step‑by‑step diagrams in the article.

Relationship between root and TreapNode root is a reference to the entry point of the whole treap; it points to a TreapNode instance or None when the tree is empty. TreapNode represents each node and stores key, priority, and pointers left and right.

All tree operations return a TreapNode which becomes the new root of the (sub)tree, preserving the recursive structure.