Skip to main content

Deletion Without Rebalancing in Binary Search Trees

Author(s): Sen, Siddhartha; Tarjan, Robert E; Kim, David H K

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1b250
Full metadata record
DC FieldValueLanguage
dc.contributor.authorSen, Siddhartha-
dc.contributor.authorTarjan, Robert E-
dc.contributor.authorKim, David H K-
dc.date.accessioned2021-10-08T19:48:31Z-
dc.date.available2021-10-08T19:48:31Z-
dc.date.issued2016-09en_US
dc.identifier.citationSen, Siddhartha, Robert E. Tarjan, and David Hong Kyun Kim. "Deletion Without Rebalancing in Binary Search Trees." ACM Transactions on Algorithms 12, no. 4 (2016): 57:1-57:31. doi:10.1145/2903142en_US
dc.identifier.issn1549-6325-
dc.identifier.urihttp://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.726.540&rep=rep1&type=pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1b250-
dc.description.abstractWe 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 B-tree--based 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 worst-case access time remains logarithmic in the number of insertions. For any application of balanced trees in which the number of updates is polynomial in the tree size, 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 lg lg m+ 1 bits of balance information per node, where m is the number of insertions and lg is the base-two logarithm, or lg lg n+ O(1) with periodic rebuilding, where n is the number of nodes. An insertion takes up to two rotations and O(1) amortized time, not counting the time to find the insertion position. This is the same as in standard AVL trees. 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. Our techniques apply to other types of balanced trees, notably B-trees, as we show in a companion article, and particularly red-black trees, which can be viewed as a special case of B-trees.en_US
dc.format.extent57:1 - 57:31en_US
dc.language.isoen_USen_US
dc.relation.ispartofACM Transactions on Algorithmsen_US
dc.rightsAuthor's manuscripten_US
dc.titleDeletion Without Rebalancing in Binary Search Treesen_US
dc.typeJournal Articleen_US
dc.identifier.doi10.1145/2903142-
dc.identifier.eissn1549-6333-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
DeletionWithoutRebalanceBinarySearchTree.pdf467.88 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.