Data Structure Definition

The FHQ Treap (Fredman, Hendler, and Zhou Treap) relies on a randomized heap priority to maintain balance without requiring complex tree rotations. Each node in the structure maintains essential metadata: pointers to left and right children, the node's value, a random priority weight, and the size of the subtree rooted at that node.

struct TreapNode {
    int children[2]; 
    int value;
    int priority;
    int subtreeSize;
} nodes[MAX_CAPACITY];

int rootIndex = 0;
int allocationIndex = 0;

Core Operation: Split

The split operation partitions a tree into two separate trees based on a threshold value. One resulting tree contains all nodes with values less than or equal to the threshold, while the other contains nodes with values greater than the threshold. This function operates recursively by deciding which subtree the current node belongs to based on its value.

void splitTree(int currentIndex, int threshold, int &leftRoot, int &rightRoot) {
    if (currentIndex == 0) {
        leftRoot = rightRoot = 0;
        return;
    }
    
    if (nodes[currentIndex].value <= threshold) {
        leftRoot = currentIndex;
        splitTree(nodes[currentIndex].children[1], threshold, nodes[currentIndex].children[1], rightRoot);
    } else {
        rightRoot = currentIndex;
        splitTree(nodes[currentIndex].children[0], threshold, leftRoot, nodes[currentIndex].children[0]);
    }
    
    updateSubtreeSize(currentIndex);
}

Core Operation: Merge

The merge operation combines two trees that satisfy the condition that all values in the first tree are strictly less than all values in the second tree. The merge process compares the random priorities of the roots to determine the new root, ensuring the heap property is preserved. Because the priority is random, the expected height of the tree remains logarithmic, specifically O(log n).

int mergeTrees(int leftRoot, int rightRoot) {
    if (leftRoot == 0 || rightRoot == 0) {
        return leftRoot + rightRoot;
    }
    
    if (nodes[leftRoot].priority < nodes[rightRoot].priority) {
        nodes[leftRoot].children[1] = mergeTrees(nodes[leftRoot].children[1], rightRoot);
        updateSubtreeSize(leftRoot);
        return leftRoot;
    } else {
        nodes[rightRoot].children[0] = mergeTrees(leftRoot, nodes[rightRoot].children[0]);
        updateSubtreeSize(rightRoot);
        return rightRoot;
    }
}

It is crucial to use a robust random number generator for the priority field. Using methods with low entropy, such as rand() & 1, can lead to significant tree imbalance and degrade performance to O(n).

Derived Operations

Most standard binary search tree operations can be implemented efficiently using combinations of split and merge. For instance, insertion involves splitting the tree by the value to be inserted and then merging the left part, the new node, and the right part sequentially. Deletion follows a similar pattern of splitting the tree to isolate the target node and merging the remaining parts.