## February 12, Winter Quarter 2010: Theory Seminar

### 1:00pm in 1423 Bren Hall

#
Deletion Without Rebalancing in Balanced Binary Trees

## Kiran Shivaram, UC Irvine

Presenting results in a paper by Siddhartha Sen and Robert E.
Tarjan from SODA10.

Abstract:
We address the vexing issue of deletions in balanced trees.
Rebalancing after a deletion is generally more complicated than
rebalancing after an insertion. Textbooks neglect deletion
rebalancing, and many database systems do not do it. We describe a
relaxation of AVL trees in which rebalancing is done after insertions
but not after deletions, yet access time remains logarithmic in the
number of insertions. For many applications of balanced trees, our
structure offers performance competitive with that of classical
balanced trees. With the addition of periodic rebuilding, the
performance of our structure is theoretically superior to that of
many if not all classic balanced tree structures. Our structure needs
O(log log m) bits of balance information per node, where m
is the number of insertions, or O(log log n) with periodic
rebuilding, where n is the number of nodes. An insertion takes up to
two rotations and O(1) amortized time. Using an analysis that relies
on an exponential potential function, we show that rebalancing steps
occur with a frequency that is exponentially small in the height of
the affected node.