How to Rotate Trees in SpaceHow to Rotate Trees in Spacehttp://www.haverford.edu/calendar/details/232041Park 338, Bryn Mawr College2013-03-01T15:00:002013-03-01T16:00:00
March 1, 3:00PM
Park 338, Bryn Mawr College
David M. Mount, Department of Computer Science, University of Maryland
Professor David Mount of the University of Maryland
Description
Balanced binary search trees, such as AVL trees, red-black trees, splay trees, and treaps are well-known data structures for storing and searching a set of n keys from an ordered domain. Through the use of a local restructuring operation, called rotation, these data structures guarantee that the tree is balanced. This means that the tree's height is O(log n), irrespective of the order in which keys are inserted, deleted, or accessed. (This holds with high probability for treaps and in the amortized sense for splay trees).
Suppose that the data set consist of points from multi-dimensional space. There are a number of balanced data structures for storing such point sets, including kd-trees, quadtrees, R-trees. These data structures all lack one important quality---there is no local restructuring operation analogous to rotation. Typically, these structures are restructured in a rather inelegant manner by completely rebuilding imbalanced subtrees.
In this talk, I will show that it is possible to design a data structure for multi-dimensional data sets that supports rotation. This data structure is a simple variant of a quadtree. The restructuring operation, called promotion, can be used to incrementally rebalance the tree in much the same manner that rotation does for binary search trees.
I will present multi-dimensional generalizations of the treap and splay tree data structures, called the quadtreap and splay quadtree, respectively. I will also discuss the similarities and differences between these structures and their one-dimensional counterparts.
For More Info
John P. Dougherty
610-896-4993
addr
Responsible at Event
JD