Using Randomized Priorities to Maintain Balance in Search Trees

---

The Quest for Balance

In our exploration of binary search trees, we’ve encountered a recurring challenge: maintaining balance. Unbalanced trees can lead to sluggish search times, hindering the efficiency of our applications. We’ve seen how AVL trees and Red-Black trees tackle this with intricate rules and rotations, offering deterministic solutions to this balancing act.

But what if there was a simpler, more elegant approach? Enter the treap, a self-balancing binary search tree that leverages the power of randomness to achieve efficiency without the complexity of its deterministic counterparts.

Today, we’ll delve into the fascinating world of treaps, exploring their unique properties and how they provide a powerful solution for balancing BSTs, especially in dynamic and probabilistic scenarios.

Treaps Under the Microscope: A Closer Look

In the ever-evolving landscape of software development, choosing the right data structure can be the key to unlocking efficiency and maintainability. Having traversed the realms of trees and heaps, we now encounter a fascinating hybrid: the treap. This intriguing structure elegantly merges the strengths of both, offering a unique advantage—probabilistic balance—making it a compelling choice for specific scenarios. Let’s put treaps under the microscope and dissect the mechanisms that make them tick.

At its core, a treap is a binary search tree, upholding a strict order: for any node, all keys in its left subtree are smaller, and all keys in its right subtree are larger. This inherent order enables swift and efficient searches for specific elements, much like a meticulously organized index.

But treaps possess a secret ingredient that sets them apart: the heap property. Each node, in addition to its key, is assigned a randomly generated priority. These priorities act as a balancing force, preventing the treap from becoming skewed and inefficient. It’s akin to a self-adjusting library shelf that subtly rearranges books to maintain equilibrium.

Here’s where the “randomized efficiency” shines. Unlike their strictly balanced counterparts (AVL trees, red-black trees), treaps rely on these random priorities to maintain balance probabilistically. This approach simplifies implementation and fosters adaptability. It’s as if the treap has a natural balancer, effortlessly adjusting as data ebbs and flows.

For developers, this fusion of order and randomized balance is a powerful tool. Treaps excel in scenarios demanding efficient search, insertion, and deletion—operations crucial for dynamic applications where data is in constant flux. Imagine managing user data, product catalogs, or even game states—the treap’s adaptability ensures smooth performance even with frequent updates.

However, it’s important to note that treaps are not optimized for priority-based retrieval. While finding the element with the highest priority is efficient, retrieving all elements in priority order is not a strength.

After revealing the core elements of a treap, let’s focus on the specific operations that fuel its dynamism and adaptability.

How Treaps Work: Essential Operations

Introducing the Case

Imagine curating a recommendation system for a discerning clientele in a luxurious online perfume shop. Your mission is to guide customers through a fragrant tapestry of scents, suggesting perfumes that resonate with their individual preferences, olfactory desires, and even their personality nuances. A treap, with its unique blend of order and adaptability, emerges as a powerful tool to craft a truly personalized and delightful shopping experience.

In this fragrant treap, the binary search tree property ensures efficient retrieval of perfumes by name, much like a customer searching for their signature scent. Meanwhile, the heap property, dictated by a chosen priority (e.g., popularity, customer rating, scent profile similarity), subtly guides the recommendation system by influencing the order of perfumes within the treap. This allows the system to prioritize trending perfumes or surface hidden gems with high ratings when making suggestions, while maintaining a balanced structure for efficient searching.

In essence, a treap is a captivating fusion of two fundamental data structures, taking the best of both worlds:

• Heap: Provides the notion of priority, which, combined with randomization, helps maintain balance. This probabilistic balance is a distinctive feature of treaps.
• Binary Search Tree (BST): Gives the treap its ordered structure, enabling efficient key-based operations like searching, inserting, and deleting nodes.

The probabilistic aspect of treaps comes from the use of random priorities assigned to each node. Unlike AVL trees with their strict balance conditions or heaps with their rigid priority order, treaps strike a balance between order and flexibility. This allows them to adapt gracefully to changes, making them particularly well-suited for dynamic environments where data is constantly evolving.

// Simple representation of a node with key and priority
class Node {
  constructor(key, priority) {
    this.key = key;
    this.priority = priority;
  }
}

// Function to generate a random priority
function getRandomPriority() {
  return Math.floor(Math.random() * 100); // Generates a random number between 0 and 99
}

// Create nodes with deterministic priorities (for a heap-like structure)
const heapNodes = [
  new Node("A", 1), 
  new Node("B", 2),
  new Node("C", 3),
  new Node("D", 4),
];

// Create nodes with probabilistic priorities (for a treap-like structure)
const treapNodes = [
  new Node("A", getRandomPriority()),
  new Node("B", getRandomPriority()),
  new Node("C", getRandomPriority()),
  new Node("D", getRandomPriority()),
];

console.log("Heap-like nodes (deterministic priorities):", heapNodes);
console.log("Treap-like nodes (probabilistic priorities):", treapNodes);

/* "Heap-like nodes (deterministic priorities):", [{
  key: "A",
  priority: 1
}, {
  key: "B",
  priority: 2
}, {
  key: "C",
  priority: 3
}, {
  key: "D",
  priority: 4
}]
"Treap-like nodes (probabilistic priorities):", [{
  key: "A",
  priority: 33
}, {
  key: "B",
  priority: 65
}, {
  key: "C",
  priority: 22
}, {
  key: "D",
  priority: 59
}]*/

You might wonder if using random priorities would cause the treap to aggressively re-balance itself with every change, potentially leading to cascading updates throughout the entire structure.

However, a key characteristic of treaps mitigates this concern. Unlike some self-balancing trees that require global adjustments, treaps maintain balance through localized rotations. When a node’s priority changes, the re-balancing process (typically involving rotations) is confined to a limited portion of the tree, often involving only the node’s siblings and parents.

This localized nature of re-balancing ensures that updates are contained and efficient, preventing unnecessary disruptions to the overall tree structure. This is a key distinction that sets treaps apart from other self-balancing trees and makes them a valuable tool in various applications, especially those with dynamic priority criteria where performance is critical, even if it means a slight compromise on perfect accuracy in priority order.

You can think of the trade-off between strictness in deterministic data structures and flexibility in treaps as analogous to the choices made in database consistency models. Traditional, centralized databases often adhere to ACID properties, ensuring strong consistency and data integrity, much like deterministic data structures that maintain strict order and priority. On the other hand, distributed databases often embrace eventual consistency, prioritizing availability and partition tolerance over strict, immediate consistency, similar to how treaps leverage probabilistic balance to achieve efficiency and adaptability.

This makes treaps a compelling choice for scenarios with dynamic priorities and large datasets where adaptability and efficient updates are paramount, especially when probabilistic balance provides sufficient order for the application’s needs.

Insertion

Imagine our online perfume shop expands its collection with a captivating new fragrance called “Midnight Bloom.” To include this newcomer in our treap-powered recommendation system, we need to insert it into the existing structure. This process involves two main steps: finding the right spot and maintaining balance.

The initial structure, with perfume names and stock quantities (as priority criteria, it can be anything else) in each node:

              +-------------------+       
              | Chanel No. 5 (50) |   
              +-------------------+      
                /                \
        +-------------------+   +----------------------------+
        | Dior J'adore (70) |   | Givenchy Irresistible (30) | 
        +-------------------+   +----------------------------+

To this existing min-heap structure, we aim to add Midnight Bloom (20). After inserting Midnight Bloom (20), the structure looks like this:

              +-------------------+       
              | Chanel No. 5 (50) |   
              +-------------------+      
                /                \
        +-------------------+   +----------------------------+
        | Dior J'adore (70) |   | Givenchy Irresistible (30) | 
        +-------------------+   +----------------------------+
                                   /
                        +---------------------+
                        | Midnight Bloom (20) |
                        +---------------------+

In a treap, we need to maintain:

• Heap Property: The parent node has a higher priority than its children in a min-heap.
• BST Property: The left child has a key less than its parent, and the right child has a key greater.

In this case, Givenchy Irresistible (30) is the parent of Midnight Bloom (20). Since 30 > 20, this violates the min-heap property.

To fix the violations, we need to swap Midnight Bloom (20) with Givenchy Irresistible (30). After swapping, the structure becomes:

              +-------------------+       
              | Chanel No. 5 (50) |   
              +-------------------+      
                /                \
        +-------------------+   +---------------------+
        | Dior J'adore (70) |   | Midnight Bloom (20) | 
        +-------------------+   +---------------------+
                                   /
                        +----------------------------+
                        | Givenchy Irresistible (30) |
                        +----------------------------+

Now, the properties are satisfied:

• Chanel No. 5 (50) is still the root.
• Midnight Bloom (20) is less than Givenchy Irresistible (30), satisfying the min-heap property.
• The binary search tree property is also maintained since the left child (Dior J’adore (70)) is greater than Chanel No. 5 (50), and Givenchy Irresistible (30) is greater than Midnight Bloom (20).

In the context of a treap, which combines properties of a binary search tree (BST) and a heap, we need to focus on the direct parent-child relationships when making adjustments after an insertion. Therefore, the adjustment only involves swapping Midnight Bloom (20) and Givenchy Irresistible (30) to ensure both the min-heap and BST properties are maintained correctly.

In a heap, insertion involves adding a new element at the end and then “bubbling up” to maintain the heap property, which takes 𝑂(log 𝑛). In a treap, you insert as in a BST (which takes 𝑂(log 𝑛) on average) and then potentially perform a few rotations to restore the heap property, often leading to fewer comparisons.

Leaf node deletion

Let’s continue with the deletion of Dior J’adore (70) from the our last treap:

              +-------------------+       
              | Chanel No. 5 (50) |   
              +-------------------+      
                /                \
        +-------------------+   +---------------------+
        | Dior J'adore (70) |   | Midnight Bloom (20) | 
        +-------------------+   +---------------------+
                                   /
                        +----------------------------+
                        | Givenchy Irresistible (30) |
                        +----------------------------+

Since “Dior J’adore (70)” has no children, it’s a leaf node. Therefore, we can directly delete it without any rotations (balancing). This is what the final treap structure looks like:

              +-------------------+       
              | Chanel No. 5 (50) |   
              +-------------------+      
                               \
                             +---------------------+
                             | Midnight Bloom (20) | 
                             +---------------------+
                                     /
                        +----------------------------+
                        | Givenchy Irresistible (30) |
                        +----------------------------+

Deleting “Dior J’adore (70)” did make the treap a bit more unbalanced. The left subtree became heavier than the right. However, this is a minor imbalance, and in a larger treap with many nodes and random priorities, such minor imbalances are unlikely to significantly impact performance.

Root node deletion

The initial treap structure looks like this:

              +-------------------+       
              | Chanel No. 5 (50) |   
              +-------------------+      
                /                \
        +-------------------+   +---------------------+
        | Dior J'adore (70) |   | Midnight Bloom (20) | 
        +-------------------+   +---------------------+
                                   /
                        +----------------------------+
                        | Givenchy Irresistible (30) |
                        +----------------------------+

This time, let’s try deleting “Chanel No. 5 (50)”, the root node. This is a more complex case because it has two children.

Here’s how the deletion would proceed:

1. Locate “Chanel No. 5 (50)”.
2. Determine Rotation: “Chanel No. 5 (50)” has children with priorities 70 and 20. Since “Midnight Bloom (20)” has the lower priority (higher priority in the min-heap), we perform a right rotation.

              +--------------------+                          
              | Midnight Bloom (20)|                         
              +--------------------+                            
                 /              \
+-------------------+     +----------------------------+      
| Chanel No. 5 (50) |     | Givenchy Irresistible (30) |   
+-------------------+     +----------------------------+     
        /                                    
+-------------------+
| Dior J'adore (70) |
+-------------------+

3. Determine Rotation (again): Now, “Chanel No. 5 (50)” has priorities 70 and “Givenchy Irresistible (30)” has the lower priority, so we perform another right rotation.

              +---------------------+                          
              | Midnight Bloom (20) |                         
              +---------------------+                            
                /                 \
+----------------------------+    +-------------------+
| Givenchy Irresistible (30) |    | Chanel No. 5 (50) |
+----------------------------+    +-------------------+
      /
+-------------------+
| Dior J'adore (70) |
+-------------------+

4. Delete: “Chanel No. 5 (50)” is now a leaf node, so we can delete it.
5. However, this violates the binary search tree property of the treap. “Dior J’adore (70)” should be in the right subtree of “Givenchy Irresistible (30)” because its key (70) is greater. Therefore, a final rotation is needed to restore the BST property, leading to the correct final treap:

              +---------------------+                          
              | Midnight Bloom (20) |                         
              +---------------------+                            
                  /               \   
+----------------------------+    +-------------------+
| Givenchy Irresistible (30) |    | Dior J'adore (70) |
+----------------------------+    +-------------------+

This demonstrates how deleting a non-leaf node involves rotations to maintain the treap’s properties.

Read all the elements by key (Traversal)

The initial treap structure looks like this:

              +-------------------+       
              | Chanel No. 5 (50) |   
              +-------------------+      
                /                \
        +-------------------+   +---------------------+
        | Dior J'adore (70) |   | Midnight Bloom (20) | 
        +-------------------+   +---------------------+
                                      /
                        +----------------------------+
                        | Givenchy Irresistible (30) |
                        +----------------------------+

To read the treap by key, we perform an in-order traversal. This gives us the keys in ascending sorted order:

1. Traverse the left subtree: “Dior J’adore (70)”
2. Visit the root: “Chanel No. 5 (50)”
3. Traverse the right subtree:
   • Traverse the left subtree: “Givenchy Irresistible (30)”
   • Visit the node: “Midnight Bloom (20)”

Therefore, the output when reading by key is: “Dior J’adore (70)”, “Chanel No. 5 (50)”, “Givenchy Irresistible (30)”, “Midnight Bloom (20)”

Reading all elements by priority in a treap is not efficient it’s a min-heap. The structure isn’t designed to optimize for that kind of retrieval. It would essentially involve traversing a significant portion of the tree, which could be time-consuming, especially for larger treaps. “Peeking” by priority, on the other hand, is a much more feasible operation. Let’s see.

“Peeking” by Priority

The initial treap structure looks like this:

              +-------------------+       
              | Chanel No. 5 (50) |   
              +-------------------+      
                /                \
        +-------------------+   +---------------------+
        | Dior J'adore (70) |   | Midnight Bloom (20) | 
        +-------------------+   +---------------------+
                                     /
                        +----------------------------+
                        | Givenchy Irresistible (30) |
                        +----------------------------+

To “peek” at the highest priority element, we follow the leftmost path:

1. Go to its left child: “Midnight Bloom (20)”
2. Start at the root: “Chanel No. 5 (50)”
3. Go to its left child: “Dior J’adore (70)”
4. Go to its left child: “Givenchy Irresistible (30)”

Therefore, “Midnight Bloom (20)” has the highest priority (lowest stock level).

Key takeaway:

• Reading all elements by priority: Inefficient, involves traversing most of the treap.
• “Peeking” at the highest priority element: Efficient, involves traversing only a single path down the left side of the treap.

Search for an Element

The initial treap structure looks like this:

              +-------------------+       
              | Chanel No. 5 (50) |   
              +-------------------+      
                /                \
        +-------------------+   +---------------------+
        | Dior J'adore (70) |   | Midnight Bloom (20) | 
        +-------------------+   +---------------------+
                                      /
                        +----------------------------+
                        | Givenchy Irresistible (30) |
                        +----------------------------+

Searching in a treap is very similar to searching in a binary search tree. We leverage the ordered property of the treap to efficiently locate the desired element.

Example: Search for “Givenchy Irresistible (30)”

1. Start at the root: “Chanel No. 5 (50)”
2. Compare: “Givenchy Irresistible” comes after “Chanel No. 5” alphabetically, so we go to the right subtree.
3. Compare: We’re at “Midnight Bloom (20)”. “Givenchy Irresistible” comes before “Midnight Bloom”, so we go left.
4. Found: We’ve reached “Givenchy Irresistible (30)”.

Example: Search for “Gucci Bloom (15)”

1. Start at the root: “Chanel No. 5 (50)”
2. Compare: “Gucci Bloom” comes after “Chanel No. 5” alphabetically, so we go to the right subtree.
3. Compare: We’re at “Midnight Bloom (20)”. “Gucci Bloom” comes after “Midnight Bloom”, so we go right again.
4. Not Found: There’s no right child, and we haven’t found “Gucci Bloom”. We conclude that it’s not in the treap.

As you can see, keys in treaps are used for searching, just like in a standard binary search tree (BST). In fact, most operations, such as insertion, deletion, and searching, are performed in the same way as in a BST. The key differences lie in how treaps maintain balance through rotations based on randomized priorities and how they allow efficient retrieval of the highest-priority element (peeking) using the heap property.

Time and Space Complexity Efficiency

Here’s a table summarizing the time and space complexity of common operations on treaps compared to other data structures:

Operation	Treap (Average)	BST (Average)	BST (Worst)	AVL Tree	Red-Black Tree	Heap
Insert	O(log n)	O(log n)	O(n)	O(log n)	O(log n)	O(log n)
Top/Peek	O(1)	O(log n)	O(n)	O(log n)	O(log n)	O(1)
Remove	O(log n)	O(log n)	O(n)	O(log n)	O(log n)	O(log n)
Contains	O(log n)	O(log n)	O(n)	O(log n)	O(log n)	–
Update Priority	O(log n)	–	–	–	–	–
Min/Max	O(log n)	O(log n)	O(n)	O(log n)	O(log n)	O(1)
Space	O(n)	O(n)	O(n)	O(n)	O(n)	O(n)

n represents the number of nodes.

• Top/Peek and Min/Max: Heaps are specifically designed to efficiently provide the highest or lowest priority element (O(1)). This is where they outperform the other tree-based structures.
• Update Priority: This operation is specific to treaps and doesn’t directly apply to the other structures.

In the average case, the random priorities ensure that the tree remains relatively balanced, leading to logarithmic time complexity for most operations.

However, in the highly unlikely worst-case scenario, the random priorities could be assigned in such a way that the treap degenerates into a linear structure (like a linked list). Imagine if the priorities were assigned in strictly increasing or decreasing order. This would lead to a skewed tree, and operations like search, insertion, and deletion would take O(n) time to traverse the entire structure.

While the theoretical worst-case complexity is O(n), the probability of this happening with truly random priorities is extremely low, and the chances decrease as the number of nodes (n) increases. In practice, treaps perform very well and are considered a good alternative to other balanced binary search trees like AVL trees or red-black trees, offering a compelling balance of efficiency and simplicity.

Much like hash tables that can degrade to O(n) time complexity due to unlikely collisions, treaps can exhibit similar behavior with unfavorable ‘priority collisions’ that skew the tree. Yet, both structures remain highly efficient in practice due to the low probability of these worst-case scenarios.

Real-life Practical Applications

Ranked Retrieval: Top-K Elements

Imagine an online store with millions of products. A treap can be used to efficiently maintain a real-time ranking of products based on sales, popularity, or customer ratings. This allows the website to quickly display the “top 10 best-selling products” or the “100 most popular items” to customers.

Let’s take the example of the “top 10 best-selling products”. This is a possible way to implement in JavaScript:

class TreapNode {
  constructor(productId, sales) {
    this.productId = productId;
    this.sales = sales; // Key for BST ordering
    this.priority = Math.random(); // Random priority for heap property
    this.left = null;
    this.right = null;
  }
}

class Treap {
  constructor() {
    this.root = null;
  }

  // Right rotate
  rotateRight(y) {
    const x = y.left;
    const T2 = x.right;
    x.right = y;
    y.left = T2;
    return x;
  }

  // Left rotate
  rotateLeft(x) {
    const y = x.right;
    const T2 = y.left;
    y.left = x;
    x.right = T2;
    return y;
  }

  // Insert a new product by sales
  insert(root, productId, sales) {
    if (!root) return new TreapNode(productId, sales);

    // Standard BST insert
    if (sales < root.sales) {
      root.left = this.insert(root.left, productId, sales);

      // Heap property violation, fix it
      if (root.left.priority > root.priority) {
        root = this.rotateRight(root);
      }
    } else if (sales >= root.sales) {
      root.right = this.insert(root.right, productId, sales);

      // Heap property violation, fix it
      if (root.right.priority > root.priority) {
        root = this.rotateLeft(root);
      }
    }
    return root;
  }

  // Insert a product into the treap
  addProduct(productId, sales) {
    this.root = this.insert(this.root, productId, sales);
  }

  // Helper function for in-order traversal to get top N sales
  inOrder(root, result, limit) {
    if (!root || result.length >= limit) return;
    this.inOrder(root.right, result, limit); // Traverse right (higher sales)
    if (result.length < limit) {
      result.push({ productId: root.productId, sales: root.sales });
      this.inOrder(root.left, result, limit); // Traverse left (lower sales)
    }
  }

  // Get top N best-selling products
  getTopProducts(limit = 10) {
    const result = [];
    this.inOrder(this.root, result, limit);
    return result;
  }
}

// Example usage with more products
const treap = new Treap();

// Inserting a variety of products with sales data
treap.addProduct('Product1', 500);
treap.addProduct('Product2', 1200);
treap.addProduct('Product3', 300);
treap.addProduct('Product4', 700);
treap.addProduct('Product5', 1500);
treap.addProduct('Product6', 1000);
treap.addProduct('Product7', 200);
treap.addProduct('Product8', 2500);
treap.addProduct('Product9', 1800);
treap.addProduct('Product10', 1300);
treap.addProduct('Product11', 900);
treap.addProduct('Product12', 50);
treap.addProduct('Product13', 250);
treap.addProduct('Product14', 3500);
treap.addProduct('Product15', 2200);

// Retrieve top 10 best-selling products
const topSellingProducts = treap.getTopProducts(10);
console.log('Top 10 Best-Selling Products:', topSellingProducts);

// Let's check how many products are there in total, demonstrating that we have more than 10 products in the treap.
const allProducts = [];
treap.inOrder(treap.root, allProducts, Infinity); // Get all products
console.log('Total Products:', allProducts.length);
console.log('All Products:', allProducts);

The output is:

Top 10 Best-Selling Products: [
  { productId: 'Product14', sales: 3500 },
  { productId: 'Product8', sales: 2500 },
  { productId: 'Product15', sales: 2200 },
  { productId: 'Product9', sales: 1800 },
  { productId: 'Product5', sales: 1500 },
  { productId: 'Product10', sales: 1300 },
  { productId: 'Product2', sales: 1200 },
  { productId: 'Product6', sales: 1000 },
  { productId: 'Product11', sales: 900 },
  { productId: 'Product4', sales: 700 }
]

Total Products: 15

....

The same approach can be applied to cases like music or video streaming charts and social media trending topics, where the key would be the song/video ID or hashtag, and the priority would be based on the number of plays, user ratings, or mentions.

In-memory Storage: Dynamic Dictionaries

We can also use the treap to manage key-value pairs, where the keys can be dynamically inserted, updated, and retrieved efficiently. This is useful for scenarios where we need an in-memory structure that balances both search time and dynamic insertion/deletion.

In the JavaScript implementation below:

• Keys: Represent unique identifiers (e.g., strings, integers).
• Values: Data associated with each key, allowing for flexible storage and retrieval.
• The Treap maintains the keys in a sorted order (based on lexicographical or numerical ordering), and the heap property ensures balanced insertion/deletion.

class TreapNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.priority = Math.random(); // Random priority for heap property
    this.left = null;
    this.right = null;
  }
}

class TreapDictionary {
  constructor() {
    this.root = null;
  }

  // Right rotation for balancing
  rotateRight(y) {
    const x = y.left;
    const T2 = x.right;
    x.right = y;
    y.left = T2;
    return x;
  }

  // Left rotation for balancing
  rotateLeft(x) {
    const y = x.right;
    const T2 = y.left;
    y.left = x;
    x.right = T2;
    return y;
  }

  // Insert a key-value pair, or update if the key already exists
  insert(root, key, value) {
    if (!root) return new TreapNode(key, value);

    // If key already exists, update the value
    if (root.key === key) {
      root.value = value;
      return root;
    }

    // Standard BST insert logic
    if (key < root.key) {
      root.left = this.insert(root.left, key, value);

      // Check heap property
      if (root.left && root.left.priority > root.priority) {
        root = this.rotateRight(root);
      }
    } else {
      root.right = this.insert(root.right, key, value);

      // Check heap property
      if (root.right && root.right.priority > root.priority) {
        root = this.rotateLeft(root);
      }
    }
    return root;
  }

  // Add or update key-value pair in the treap
  addOrUpdate(key, value) {
    this.root = this.insert(this.root, key, value);
  }

  // Search for a key and return the value
  search(root, key) {
    if (!root) return null;
    if (root.key === key) return root.value;
    if (key < root.key) return this.search(root.left, key);
    return this.search(root.right, key);
  }

  // Search interface for the user
  get(key) {
    return this.search(this.root, key);
  }

  // Delete a key-value pair
  deleteNode(root, key) {
    if (!root) return null;

    // Standard BST deletion
    if (key < root.key) {
      root.left = this.deleteNode(root.left, key);
    } else if (key > root.key) {
      root.right = this.deleteNode(root.right, key);
    } else {
      // Node with only one child or no child
      if (!root.left) return root.right;
      if (!root.right) return root.left;

      // Node with two children: Get the inorder successor (smallest in right subtree)
      const temp = this.findMin(root.right);
      root.key = temp.key;
      root.value = temp.value;
      root.right = this.deleteNode(root.right, temp.key);
    }

    return root;
  }

  // Delete key-value pair
  remove(key) {
    this.root = this.deleteNode(this.root, key);
  }

  // Find the minimum key node
  findMin(node) {
    while (node.left) node = node.left;
    return node;
  }

  // In-order traversal to get all key-value pairs
  inOrder(root, result) {
    if (!root) return;
    this.inOrder(root.left, result);
    result.push({ key: root.key, value: root.value });
    this.inOrder(root.right, result);
  }

  // Get all key-value pairs in sorted order
  getAll() {
    const result = [];
    this.inOrder(this.root, result);
    return result;
  }
}

// Example usage
const treapDict = new TreapDictionary();

// Adding or updating key-value pairs
treapDict.addOrUpdate('apple', 100);
treapDict.addOrUpdate('banana', 50);
treapDict.addOrUpdate('cherry', 200);
treapDict.addOrUpdate('date', 30);
treapDict.addOrUpdate('elderberry', 150);
treapDict.addOrUpdate('fig', 80);
treapDict.addOrUpdate('apple', 500); // Update value for existing key

// Retrieve a value by key
console.log('Value for "apple":', treapDict.get('apple')); // Output: 500 (updated value)

// Remove a key-value pair
treapDict.remove('date');
console.log('All key-value pairs after removal:', treapDict.getAll());

// Get all key-value pairs
console.log('All key-value pairs:', treapDict.getAll());

The output is:

Value for "apple": 500
All key-value pairs after removal: [
  { key: 'apple', value: 500 },
  { key: 'banana', value: 50 },
  { key: 'cherry', value: 200 },
  { key: 'elderberry', value: 150 },
  { key: 'fig', value: 80 }
]
All key-value pairs: [
  { key: 'apple', value: 500 },
  { key: 'banana', value: 50 },
  { key: 'cherry', value: 200 },
  { key: 'elderberry', value: 150 },
  { key: 'fig', value: 80 }
]

In both cases, whether for product ranking or dynamic dictionaries, the core logic of maintaining a binary search tree (BST) property with heap balancing remains the same. The only major distinction is how we interpret the data stored within the treap.

Text Editors: Efficient String Manipulation

In the context of efficient string manipulation for text editors, a Treap can be a powerful tool for managing dynamic text. Here, we focus on efficiently handling operations like insertion, deletion, concatenation, and splitting strings, especially when the text is frequently updated (like in a text editor).

In a typical array-based string, operations like inserting or deleting in the middle of the text are expensive. A treap, however, allows these operations to be performed in logarithmic time:

• Insert a Substring: Insert a new piece of text at any position.
• Delete a Substring: Remove a specific section of the text.
• Concatenation and Splitting: Treap supports splitting the text at a given position and concatenating two texts efficiently.

class TreapNode {
  constructor(key, value) {
    this.key = key; // Position in the string
    this.value = value; // The character or substring
    this.priority = Math.random(); // Random priority for balancing
    this.left = null;
    this.right = null;
    this.size = 1; // Subtree size for maintaining string positions
  }

  // Update size of the subtree
  updateSize() {
    this.size = 1 + (this.left ? this.left.size : 0) + (this.right ? this.right.size : 0);
  }
}

class TreapTextEditor {
  constructor() {
    this.root = null;
  }

  // Right rotation
  rotateRight(y) {
    const x = y.left;
    const T2 = x.right;
    x.right = y;
    y.left = T2;
    y.updateSize();
    x.updateSize();
    return x;
  }

  // Left rotation
  rotateLeft(x) {
    const y = x.right;
    const T2 = y.left;
    y.left = x;
    x.right = T2;
    x.updateSize();
    y.updateSize();
    return y;
  }

  // Insert character (or string) at a specific position
  insert(root, pos, value) {
    if (!root) return new TreapNode(pos, value);

    // Update positions by maintaining subtree sizes
    const leftSize = root.left ? root.left.size : 0;

    if (pos <= leftSize) {
      root.left = this.insert(root.left, pos, value);
      if (root.left.priority > root.priority) {
        root = this.rotateRight(root);
      }
    } else {
      root.right = this.insert(root.right, pos - leftSize - 1, value);
      if (root.right.priority > root.priority) {
        root = this.rotateLeft(root);
      }
    }

    root.updateSize();
    return root;
  }

  // Public method to insert at any position
  insertAt(pos, value) {
    this.root = this.insert(this.root, pos, value);
  }

  // Split the treap into two at position pos
  split(root, pos) {
    if (!root) return [null, null];

    const leftSize = root.left ? root.left.size : 0;
    if (pos <= leftSize) {
      const [left, right] = this.split(root.left, pos);
      root.left = right;
      root.updateSize();
      return [left, root];
    } else {
      const [left, right] = this.split(root.right, pos - leftSize - 1);
      root.right = left;
      root.updateSize();
      return [root, right];
    }
  }

  // Merge two treaps
  merge(left, right) {
    if (!left) return right;
    if (!right) return left;

    if (left.priority > right.priority) {
      left.right = this.merge(left.right, right);
      left.updateSize();
      return left;
    } else {
      right.left = this.merge(left, right.left);
      right.updateSize();
      return right;
    }
  }

  // Delete a character at a specific position
  delete(root, pos) {
    if (!root) return null;

    const leftSize = root.left ? root.left.size : 0;

    if (pos < leftSize) {
      root.left = this.delete(root.left, pos);
    } else if (pos > leftSize) {
      root.right = this.delete(root.right, pos - leftSize - 1);
    } else {
      // Found the node to delete
      return this.merge(root.left, root.right);
    }

    root.updateSize();
    return root;
  }

  // Public method to delete at any position
  deleteAt(pos) {
    this.root = this.delete(this.root, pos);
  }

  // In-order traversal to retrieve the entire text
  inOrder(root, result) {
    if (!root) return;
    this.inOrder(root.left, result);
    result.push(root.value);
    this.inOrder(root.right, result);
  }

  // Get the full text as a string
  getText() {
    const result = [];
    this.inOrder(this.root, result);
    return result.join('');
  }
}

// Example Usage:
const editor = new TreapTextEditor();

// Insert characters at specific positions
editor.insertAt(0, 'H');
editor.insertAt(1, 'e');
editor.insertAt(2, 'l');
editor.insertAt(3, 'l');
editor.insertAt(4, 'o');
editor.insertAt(5, ',');
editor.insertAt(6, ' ');
editor.insertAt(7, 'W');
editor.insertAt(8, 'o');
editor.insertAt(9, 'r');
editor.insertAt(10, 'l');
editor.insertAt(11, 'd');
editor.insertAt(12, '!');

// Output the text
console.log(editor.getText()); // "Hello, World!"

// Delete character at position 5 (the comma)
editor.deleteAt(5);
console.log(editor.getText()); // "Hello World!"

// Insert at position 5 again (replace the comma)
editor.insertAt(5, ',');
console.log(editor.getText()); // "Hello, World!"

Key statements:

1. Insert: Adds characters or substrings at a given position while maintaining the treap’s balanced structure.
2. Delete: Removes a character (or a group of characters) from any position.
3. Split: Allows splitting the text at any given position, making it easy to manage text portions separately.
4. Merge: Merges two separate treap parts, useful when combining two texts or reconciling after a split.

Key Points:

• Operations like insertion and deletion are logarithmic in nature, making this suitable for large-scale text manipulation.
• By using priorities, the treap remains balanced even with frequent updates, ensuring smooth user experience in a text editor.
• The treap can handle dynamic string updates more efficiently than typical array-based approaches, which require shifting elements for every modification.

This case inspires me to use a Treap as the low-level data structure for an efficient array. It can provide excellent performance for operations like insertion, deletion, and splitting, especially in scenarios where updates are frequent and must occur in the middle of the array.

See you soon, not goodbye

Treaps, with their unique blend of binary search tree properties and randomized heap priorities, offer a compelling approach to maintaining balanced data structures. They provide efficient performance for key-based operations like searching, insertion, and deletion, while their probabilistic balance makes them adaptable to dynamic environments where priorities change frequently.

While treaps might not be as widely known as some other self-balancing trees like AVL or Red-Black trees, they offer a valuable alternative, especially in scenarios where a slight compromise on strict priority order is acceptable in exchange for performance gains and implementation simplicity.

As we’ve seen, treaps have applications in diverse domains, from maintaining ranked lists and dynamic dictionaries to efficiently manipulating strings in text editors. Their ability to handle dynamic priorities and large datasets makes them a valuable tool in the developer’s toolkit.

The concept of prioritizing elements, as seen in heaps and treaps, is also central to caching strategies. Two common algorithms, LFU (Least Frequently Used) and LRU (Least Recently Used), employ different prioritization methods. LFU caches data based on how often it’s accessed, while LRU prioritizes recently used data.

In my next article, we’ll delve into LFU and LRU caching, comparing their strategies and trade-offs, and examining their applications in various systems. See you soon! 😍