{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:17:34Z","timestamp":1763468254384,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,6,2]],"date-time":"2015-06-02T00:00:00Z","timestamp":1433203200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF CCF grant \u201cDistributed Algorithms for Near-Planar Networks\u201d"},{"name":"AFOSR MURI"},{"name":"NSF","award":["CCF-0830676 and CCF-0832797"],"award-info":[{"award-number":["CCF-0830676 and CCF-0832797"]}]},{"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":[[2015,6,23]]},"abstract":"<jats:p>\n            Since the invention of AVL trees in 1962, many kinds of binary search trees have been proposed. Notable are red-black trees, in which bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and O(1) rotations worst-case. But the design space of balanced trees has not been fully explored. We continue the exploration. Our contributions are three: We systematically study the use of\n            <jats:italic>ranks<\/jats:italic>\n            and\n            <jats:italic>rank differences<\/jats:italic>\n            to define height-based balance in binary trees. Different invariants on rank differences yield AVL trees, red-black trees, and other kinds of balanced trees. By relaxing AVL trees, we obtain a new kind of balanced binary tree, the\n            <jats:italic>weak AVL tree (wavl tree)<\/jats:italic>\n            , whose properties we develop. Bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and at most two rotations, improving the three or more rotations per deletion needed in all other kinds of balanced trees of which we are aware. The height bound of a wavl tree degrades gracefully from that of an AVL tree as the number of deletions increases and is never worse than that of a red-black tree. Wavl trees also support top-down, fixed look-ahead rebalancing in O(1) amortized time. Finally, we use exponential potential functions to prove that in wavl trees rebalancing steps occur exponentially infrequently in rank. Thus, most of the rebalancing is at the bottom of the tree, which is crucial in concurrent applications and in those in which rotations take time that depends on the subtree size.\n          <\/jats:p>","DOI":"10.1145\/2689412","type":"journal-article","created":{"date-parts":[[2015,6,2]],"date-time":"2015-06-02T18:19:47Z","timestamp":1433269187000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Rank-Balanced Trees"],"prefix":"10.1145","volume":"11","author":[{"given":"Bernhard","family":"Haeupler","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, PA, United States"}]},{"given":"Siddhartha","family":"Sen","sequence":"additional","affiliation":[{"name":"Microsoft Research, New York, NY, United States"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[{"name":"Princeton University and Intertrust Technologies, Princeton, NJ, United States"}]}],"member":"320","published-online":{"date-parts":[[2015,6,2]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1259","article-title":"An algorithm for the organization of information","volume":"3","author":"Adel\u2019son-Vel\u2019skii G. M.","year":"1962","journal-title":"Sov. Math. Dokl."},{"key":"e_1_2_1_2_1","unstructured":"Alfred V. Aho John E. Hopcroft and Jeffrey D. Ullman. 1983. Data Structures and Algorithms. Addison-Wesley.   Alfred V. Aho John E. Hopcroft and Jeffrey D. Ullman. 1983. Data Structures and Algorithms. Addison-Wesley."},{"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.1007\/BF00288683"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90018-3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1511"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90005-4"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840439"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.3"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03367-4_31"},{"volume":"104","volume-title":"GI-Conference on Theoretical Computer Science (LNCS)","author":"Huddleston S.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288968"},{"key":"e_1_2_1_15_1","unstructured":"Donald E. Knuth. 1973. The Art of Computer Programming Volume 3: Sorting and Searching. Addison-Wesley.  Donald E. Knuth. 1973. The Art of Computer Programming Volume 3: Sorting and Searching. Addison-Wesley."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054196000142"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214021"},{"key":"e_1_2_1_18_1","unstructured":"Kurt Mehlhorn. 1984. Data Structures and Algorithms 1: Sorting and Searching. Vol. 1. Springer-Verlag. Pages 198--199.  Kurt Mehlhorn. 1984. Data Structures and Algorithms 1: Sorting and Searching. Vol. 1. Springer-Verlag. Pages 198--199."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215002"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202005"},{"key":"e_1_2_1_22_1","first-page":"51","article-title":"A new class of balanced search trees: Half balanced binary search trees","volume":"16","author":"Olivi\u00e9 Henk J.","year":"1982","journal-title":"ITA"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90005-3"},{"key":"e_1_2_1_24_1","unstructured":"Robert Sedgewick. 2008. Left-leaning Red-Black Trees. Retrieved from http:\/\/www.cs.princeton.edu\/ rs\/talks\/LLRB\/LLRB.pdf.  Robert Sedgewick. 2008. Left-leaning Red-Black Trees. Retrieved from http:\/\/www.cs.princeton.edu\/ rs\/talks\/LLRB\/LLRB.pdf."},{"key":"e_1_2_1_25_1","unstructured":"Steven S. Skiena. 1998. The Algorithm Design Manual. Springer-Verlag.   Steven S. Skiena. 1998. The Algorithm Design Manual. Springer-Verlag."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90099-6"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0606031"},{"key":"e_1_2_1_29_1","unstructured":"Hans van der Laan. 1997. Le Nombre Plastique: Quinze Lecons Sur L\u2019Ordonnance Architectonique. Brill Academic.  Hans van der Laan. 1997. Le Nombre Plastique: Quinze Lecons Sur L\u2019Ordonnance Architectonique. Brill Academic."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289574"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2689412","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2689412","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:55:46Z","timestamp":1750272946000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2689412"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,2]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,6,23]]}},"alternative-id":["10.1145\/2689412"],"URL":"https:\/\/doi.org\/10.1145\/2689412","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2015,6,2]]},"assertion":[{"value":"2012-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}