Data Structures & Algorithms Lecture Notes

1 April 2010 • Treaps


A Question

Tree Operations and Shape

Tree Levels

Tree Shape

Balance Examples

Getting Balanced Trees

Shuffling Data

Shuffling Problems

Overcoming Problems

Random Heap Shuffling


Treap Nodes

Example Treap

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

Maintaining the BST Property

Insertion Example

Treap Deletion

Deletion Example

Treap Performance



This page last modified on 31 March 2010.

    Commons License