Collection Kit

Treap

Tree

A Treap is a combination of a binary search tree and a heap, maintaining both properties. Each node has a key and a priority, and the tree is organized such that the binary search tree property is maintained based on keys, while the heap property is maintained based on priorities.

Import Statement
import { Treap } from "collection-kit";

Key Features

  • Randomized Structure: The priorities are assigned randomly, which helps maintain balance.
  • Efficient Operations: Provides O(log n) expected time complexity for search, insertion, and deletion operations.

Common Operations

Insert
Add a new element while maintaining both the binary search tree and heap properties.
Remove
Delete an element while maintaining the properties.
Search
Retrieve an element from the tree.

Example Code

import { Treap } from "collection-kit";

const treap = new Treap();
treap.insert(10, 5);  // key, priority
treap.insert(20, 3);
treap.insert(5, 8);

console.log("Search 20:", treap.search(20)); // true
treap.remove(10);
console.log("Search 10:", treap.search(10)); // false