Data Structures & Algorithms Lecture Notes

19 November 2010 • Treaps

---

Outline

• Data and balance.
• Random data.
• Rotating binary-search-tree nodes.
• Treaps

A Question

• Here are two binary search trees containing the same data.

  

  Why are they different?

Tree Operations and Shape

• Tree operations can influence a tree’s shape.

  

• Tree shape influences tree operation performance.

Tree Levels

• A node n is at level i in a tree T if n is i edges away from the root.

  The ith level of T is the nonempty set of all nodes at level i in T.

• A node’s depth d is the node’s level.
• A tree’s height h is the largest level in the tree.

Tree Shape

• Tree operations have good performance when each decision throws away half the data.
  • This occurs when each subtree has half the data.
• This property is captured by the notion of balance.
• A tree is balanced if any two sibling subtrees differ in height by at most 1.

Balance Examples

Getting Balanced Trees

• Several techniques produce balanced trees:
  • Shuffle the data before inserting it.
    • May not be practical or always applicable.
  • Ocassionally reconstruct a balanced tree.
    • Effective but possibly expensive.
  • Rebalance the tree after every operation.
    • Effective, moderately expensive, complicates operations.

Shuffling Data

• Shuffling data reduces the possiblity of bad ordering.

  

Shuffling Problems

• Data may be added incrementally, making it impossible to shuffle.
• Effectively shuffling large data blocks is expensive in time and space.
• Second-order groupings may survive shuffling, causing bad balance.
• Shuffling doesn’t deal with deletions.

Overcoming Problems

• Make shuffling incremental too.
  • See how balance is effected, and shuffle to adjust.
• Shuffle after insertions and deletions.
  • Shuffle any time balance is degraded.
• Shuffle once the data’s in the tree.
  • Shuffling is an operation on the tree.
• How can a binary search tree be randomly shuffled?

Random Heap Shuffling

• Combine a binary search tree and a min or max heap of random values.
  • The binary search tree orders the data for intelligent traversals.
  • The random heap shuffles the tree structure for reasonable performance.

Treaps

• A treap (= tree + heap) is a combined binary search tree and min or max heap.
• A treap simultaniously satisfies the binary search tree property and the heap property.
• Becasue it relies on random values, a treap is a probabilistic data structure.
  • A particular treap may have bad (or good) worst-case performance.
  • Many treaps average out to good worst-case performance overall.

Treap Nodes

• A treap is a regular binary tree with an extra field for the heap value.

  private class TreapNode {
    T tree_value;
    int heap_value;
    TreapNode left, right;
    }
  

  • The heap value is often called the priority.
• The treap assigns each tree value a unique random heap value.

Example Treap

• Insertion order: a, ..., z.

  

Treap Insertion

1. Insert the new tree value into the treap to preserve the binary search tree property.
2. Assign the new tree value a unique random heap value.
   • The treap code assigns the heap value.
3. Use node rotations to bubble up the new heap value to re-establish the heap property if necessary.
   • Maintaining the bst property.

Node Rotations

• A node rotation locally manipulates a binary tree.

  

• Treap nodes rotate to maintain the heap property.

Maintaining the BST Property

• A node rotation maintains the BST property.

  

Insertion Example

Treap Deletion

• There are two ways to delete a treap node:
  1. Rotate the target node to a leaf, remove.
     • Maintaining the heap and bst properties.
  2. A BST-style leaf-hoist requires two traversals worst case.
     • Find and hoist the leaf value.
     • Re-establish the heap property.

Deletion Example

Treap Performance

• The ith tree value added to a treap has average depth H_i.
  • H_i is the ith harmonic number,

    H_i = 1/1 + 1/2 + · · · + 1/i

• H_i has worst-case bound O(ln i).
• The expected performance for treap operations is O(log n).

Summary

• Fundamental ADT performance may be data dependent.
• Randomization may provide good long-term worst-case performance.
  • Don’t fear the probability, exploit it.
• A treap combines a binary search tree and a random heap.
  • The BST property for order, the heap property for structure.

References

• Randomized Search Trees by Cecilia Aragon and Raimund Seidel in Algorithmica, October-November 1996.
• Treaps in Java by Stefan Nilsson in Dr Dobb’s Journal, July 1997.

---

This page last modified on 16 November 2010.