{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:35:05Z","timestamp":1763458505200,"version":"3.45.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,9,2]],"date-time":"2017-09-02T00:00:00Z","timestamp":1504310400000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"AFOSR MURI grant"},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-0830676 and CCF-0832797"],"award-info":[{"award-number":["CCF-0830676 and CCF-0832797"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"US-Israel Binational Science Foundation","award":["2006204"],"award-info":[{"award-number":["2006204"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,9,2]]},"abstract":"<jats:p>\n                    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 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\n                    <jats:italic toggle=\"yes\">m<\/jats:italic>\n                    + 1 bits of balance information per node, where\n                    <jats:italic toggle=\"yes\">m<\/jats:italic>\n                    is the number of insertions and lg is the base-two logarithm, or lg lg\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    + O(1) with periodic rebuilding, where\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\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.\n                  <\/jats:p>","DOI":"10.1145\/2903142","type":"journal-article","created":{"date-parts":[[2016,9,2]],"date-time":"2016-09-02T10:33:50Z","timestamp":1472812430000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Deletion Without Rebalancing in Binary Search Trees"],"prefix":"10.1145","volume":"12","author":[{"given":"Siddhartha","family":"Sen","sequence":"first","affiliation":[{"name":"Microsoft Research, New York, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[{"name":"Princeton University and Intertrust Technologies, Sunnyvale, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David Hong Kyun","family":"Kim","sequence":"additional","affiliation":[{"name":"University of Chicago, Chicago, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,9,2]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"143","article-title":"Zipf\u2019s law and the Internet","volume":"3","author":"Adamic Lada A.","year":"2002","unstructured":"Lada A. Adamic and Bernardo A. Huberman. 2002. Zipf\u2019s law and the Internet. Glottometrics 3, 143--150.","journal-title":"Glottometrics"},{"key":"e_1_2_1_2_1","first-page":"1259","article-title":"An algorithm for the organization of information","volume":"3","author":"Adel\u2019son-Vel\u2019skii G. M.","year":"1962","unstructured":"G. M. Adel\u2019son-Vel\u2019skii and E. M. Landis. 1962. An algorithm for the organization of information. Soviet Mathematics Doklady 3, 1259--1262.","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/645929.672716"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1734714.1734731"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289509"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1511"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1693453.1693488"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/32.1.68"},{"key":"e_1_2_1_9_1","volume-title":"Gammes Stenographiques","author":"Estoup J. B.","unstructured":"J. B. Estoup. 1916. Gammes Stenographiques (4th ed.). Paris Institut Stenographique, Paris, France.","edition":"4"},{"key":"e_1_2_1_10_1","unstructured":"Caxton C. Foster. 1965. A Study of AVL Trees. Technical Report GER-12158. Goodyear Aerospace Corporation Akron OH."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840439"},{"key":"e_1_2_1_12_1","unstructured":"J. Gray and A. Reuter (Eds.). 1993. B-trees. In Transaction Processing: Concepts and Techniques. Morgan Kaufmann San Mateo CA 851--876."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.3"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03367-4_31"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2689412"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/648256.752883"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/182.358442"},{"volume-title":"Department of Mathematics","author":"Kyun Kim David Hong","key":"e_1_2_1_18_1","unstructured":"David Hong Kyun Kim. 2010. Deletions Without Rebalancing in Red Black Trees. Undergraduate Junior Thesis, Department of Mathematics, Princeton University, Princeton, NJ."},{"volume-title":"The Art of Computer Programming, Volume 3: Sorting and Searching","author":"Knuth Donald E.","key":"e_1_2_1_19_1","unstructured":"Donald E. Knuth. 1973. The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054196000142"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215002"},{"key":"e_1_2_1_22_1","unstructured":"J. Metzger. 1975. Managing Simultaneous Operations in Large Ordered Indexes. Technical Report. Technische Universit\u00e4t M\u00fcnchen Institut f\u00fcr Informatik TUM-Math."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202005"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03036462"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/28659.28677"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1982160100511"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1268708.1268751"},{"key":"e_1_2_1_28_1","volume-title":"Seltzer","author":"Olson Michael A.","year":"2000","unstructured":"Michael A. Olson, Keith Bostic, and Margo I. Seltzer. 2000. Berkeley DB."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90005-3"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/6138.6151"},{"key":"e_1_2_1_31_1","volume-title":"Retrieved","author":"Sedgewick Robert","year":"2008","unstructured":"Robert Sedgewick. 2008. Left-Leaning Red-Black Trees. Retrieved July 14, 2016, from http:\/\/www.cs.princeton.edu\/&sim;rs\/talks\/LLRB\/LLRB.pdf."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_84"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873722"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2540068"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90042-4"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90099-6"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0606031"},{"key":"e_1_2_1_39_1","unstructured":"Robert Endre Tarjan. 1985b. Efficient Top-Down Updating of Red-Black Trees. Technical Report TR-006-85. Department of Computer Science Princeton University Princeton NJ."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/2161700"},{"key":"e_1_2_1_41_1","unstructured":"S. Yang and R. E. Tarjan. 2014. Eager and lazy deletion rebalancing in binary search trees. Unpublished manuscript."},{"volume-title":"Selected Studies of the Principle of Relative Frequency in Language","author":"Zipf G. K.","key":"e_1_2_1_42_1","unstructured":"G. K. Zipf. 1932. Selected Studies of the Principle of Relative Frequency in Language. Harvard University Press, Cambridge, MA."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2903142","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2903142","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2903142","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:27:15Z","timestamp":1763458035000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2903142"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,2]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,9,2]]}},"alternative-id":["10.1145\/2903142"],"URL":"https:\/\/doi.org\/10.1145\/2903142","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2016,9,2]]},"assertion":[{"value":"2015-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}