Lecture 21: 03/05/2012

Today’s topic: Treaps (or Tree-heap).

What are they? A cross between a binary search trees and heaps. They are binary trees where nodes are “in-order”, meaning that a node k is greater than anything in its left subtree and less than everything in its right subtree.

Furthermore, every node is assigned a priority p(k), such that p(parent(k)) < p(k) (assuming that 1 is the highest priority and smaller number is higher priority), and the root has the highest priority.

At first you might think that a treap might not exist, given a set of keys S, and a priority assignment for S. However, you can simply insert the keys into a new treap T, ordered by their priorities, as you would in a normal binary search tree. If the priorities are all unique, then we get a unique treap:

The highest priority key must be the root, then recursively build the unique treaps for the elements less than k and greater than k and attach them to k as the left and right subtrees, respectively.

How are they like BSTs? insert(x, T), member(x, T), and delete(x, T) all run in expected O(log n) time.

insert(x, T): do a normal insert into T as a leaf as you would for a BST, then randomly generate a priority for x, and percolate it up until the heap property is restored

member(x, T): same as for BST

delete(x, T): look for x as you would for a BST, then once we find it, rotate it down to a leaf by rotating x with its higher priority child, then we trim it off the tree
we must rotate it with the higher priority child so that we don’t mess up the heap property

All that’s left is the analysis. We’ll see that all of it is in expectation. We saw examples of treaps that are highly unbalanced, but if we average over all possible treaps on the same set of keys, the expected depth will be O(log n).

Advertisements

Lecture 16: 02/20/2012

Today we covered Danny and Bob’s (Sleator and Tarjan, respectively) favorite data structure, the Splay tree.

But first, a bit about the midterm. It’s coming up on Wednesday. Manuel mentioned that he’ll have a couple short questions to test your understanding of the basic material from lectures, as well as a data structure design question. Other than that, all material mentioned in lecture at any point is fair game, even if it wasn’t written down.

A couple students mentioned that they want to share HW4 problems to help you study, so if you wish, comment on the HW4 post with your question. Try not to give the solution (or at least try to hide it) so that we can think about it first.

Now, back to trees. We covered the basics of binary search trees and found that they can actually be quite bad if we don’t balance them. But balancing is a pain, so its better if the tree does it on its own (just like malloc and garbage collection).

The magic in splay trees is the all-powerful Splay(i, S) operation, that brings the element i to the root of S, but instead of doing vanilla rotations, which we saw don’t help very much, we’re going to have some special rotations (elsewhere called zig, zig-zig, and zig-zag) that help balance the tree on the way up.

Today was mostly terminology so on Friday we’ll actually dive into the analysis of the operations.

Good luck studying for the midterm!