Data Structures & Algorithms Lecture Notes

1 April 2010 • Treaps


Outline

A Question

Tree Operations and Shape

Tree Levels

Tree Shape

Balance Examples

Getting Balanced Trees

Shuffling Data

Shuffling Problems

Overcoming Problems

Random Heap Shuffling

Treaps

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

Summary

References


This page last modified on 31 March 2010.

Creative
    Commons License