Siddhartha Sen

New Balanced Search Trees

ABSTRACT
Balanced search trees are ubiquitous in computer
science, appearing in database systems, the Linux task
scheduler, and many other applications. In this talk, I will
present new balanced search trees that are simpler and more
efficient in several ways, showing that the design space of
this classical data structure has not been exhausted. At the
core of our results is a new method for analyzing tree
rotations that relies on an exponential potential function.

We first present the rank-balanced tree, a simple relaxation of
AVL trees that takes $O(1)$ amortized time to rebalance after
insertions and deletions. Rank-balanced trees perform fewer
rotations than red-black trees and achieve better height
bounds. Using an exponential potential function, we show that
rebalancing in both types of trees modifies nodes exponentially
infrequently in their heights.

We then show that balanced search trees remain efficient even
if deletion is done without any rebalancing. These results
justify the practice of many B-tree-based database systems. In
the case of binary trees, the underlying data structure must be
modified to obtain such a result, leading to the relaxed AVL
(ravl) tree and relaxed versions of red-black trees. These
trees have height logarithmic in the number of insertions, and
rebalancing modifies nodes exponentially infrequently in their
heights. However, this seems to require $\Omega(\log\log n)$
bits of balance information at each of the $n$ nodes.

Joint work with Bernhard Haeupler and Robert Tarjan.


BIO:
Siddhartha Sen is a Ph.D. candidate in Princeton
University's Department of Computer Science, advised by Robert
Tarjan and Michael Freedman. His research interests lie at the
boundary of systems and theory, with the goal of designing data
structures and algorithms for building provably scalable and
reliable distributed systems. Before Princeton, he received his
S.B. and M.Eng degrees from MIT under the supervision of
Charles Leiserson, and spent three years in the Network Load
Balancing group of Windows Server at Microsoft Corp.