6.851: Advanced Data Structures (Spring'12)

Prof. Erik Demaine     TAs: Tom Morgan, Justin Zhang

[Home] [Lectures] [Assignments] [Project] [Problem Session]

Lecture 15 Video     [previous] [next]

[+] Static trees: least common ancestor, range minimum queries, level ancestor Scribe Notes [src]

It's amazing what you can do in constant time using only linear space. This lecture is about such data structures for jumping around (static) rooted trees. Given two nodes, we'll see how to find their least common ancestor in constant time. Given a node and a number k, we'll see how to find the kth ancestor of the node in constant time. Both data structures use a nice collection of ideas, including a powerful trick we haven't used before: lookup tables for small inputs.

Along the way, we'll solve another seemingly unrelated problem: preprocess an array of numbers to support queries of the form: what's the smallest number in a given interval of the array? Again, we'll show that constant-time queries are possible using only linear space.

Download Video: 360p, 720p

Lecture notes, page 1/8[previous page][next page][PDF]

Lecture notes, page 1/8[previous page][next page][PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.