Siddhartha Sen at theory lunch

Siddhartha Sen at theory lunch: "

Feb

12

11:45 am

Theory Lunch, Fri Feb 12, 2010, 11:45am, COS 402.

Simpler, Better Balanced Search Trees

Siddhartha Sen (Princeton University)



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 than existing trees, showing that the design space of this classical data structure is far from being exhausted.

We begin with 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 a novel analysis that relies on an exponential potential function, we show that rebalancing modifies nodes exponentially infrequently in their heights.

Building on these techniques, we 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. Ravl 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. Both rank-balanced trees and ravl trees show great promise in practice and are currently being taught to undergraduates.

"