TY - GEN

T1 - Deletion without rebalancing in balanced binary trees

AU - Sen, Siddhartha

AU - Tarjan, Robert E.

PY - 2010/1/1

Y1 - 2010/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77951668554&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77951668554&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973075.121

DO - 10.1137/1.9781611973075.121

M3 - Conference contribution

AN - SCOPUS:77951668554

SN - 9780898717013

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1490

EP - 1499

BT - Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms

PB - Association for Computing Machinery

T2 - 21st Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 17 January 2010 through 19 January 2010

ER -