Binary Search Trees of Bounded Balance

DOI10.1137/0202005zbMath0262.68012OpenAlexW2026166434WikidataQ56562647 ScholiaQ56562647MaRDI QIDQ5678421

Edward M. Reingold, Jurg Nievergelt

Publication date: 1973

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0202005

Mathematics Subject Classification ID

General topics in the theory of software (68N01)

Related Items

Expected time analysis for Delaunay point location, On rotations in fringe-balanced binary trees, Fast updating of well-balanced trees, The node visit cost of brother trees, Balanced search trees made simple, Gap terminology and related combinatorial properties for AVL trees and Fibonacci-isomorphic trees, Rank-Balanced Trees, Amortized Computational Complexity, Making data structures persistent, Maintaining range trees in secondary memory. Part I: Partitions, The complexity of on-line simulations between multidimensional turing machines and random access machines, Worst-case analysis of the set-union problem with extended backtracking, Maintaining α-balanced trees by partial rebuilding, Randomized search trees, Optimizing binary heaps, Deletion without rebalancing in multiway search trees, Fibonacci BSTs: a new balancing method for binary search trees, On the average number of rebalancing operations in weight-balanced trees, Red-black trees with constant update time, Effective splaying with restricted rotations, Binary search trees in secondary memory, Dynamic planar range skyline queries in log logarithmic expected time, Binary search trees of almost optimal height, Aspects of insertion in random trees, Dynamic deferred data structuring, Efficient dynamic algorithms for some geometric intersection problems, Unnamed Item, Towards a real time algorithm for parameterized longest common prefix computation, A worst-case efficient algorithm for hidden-line elimination^†, Deciding bisimilarity and similarity for probabilistic processes., Updating approximately complete trees, Height balance distribution of search trees, Unnamed Item, Optimal binary search trees, Maintaining multiple representations of dynamic data structures, Implementing dictionaries using binary trees of very small height, Height balanced 2-3 trees, Dynamic weighted binary search trees, Agglomerative clustering of growing squares, Efficient Top-k Queries for Orthogonal Ranges, Intersection joins under updates, Preprocessing Ambiguous Imprecise Points, Some Results for Elementary Operations, Measuring tree balance using symmetry nodes -- a new balance index and its extremal properties, A comparative study of 2-3 trees and AVL trees, A data structure for dynamic trees, A data structure for dynamic range queries, A NEW WEIGHT BALANCED BINARY SEARCH TREE, Fast algorithms for bin packing, Maintaining order in a generalized linked list, New trie data structures which support very fast search operations, Purely top-down updating algorithms for stratified search trees, Efficient splitting and merging algorithms for order decomposable problems., A simple, faster method for kinetic proximity problems, Maintaining AUC and \(H\)-measure over time, A comparison of iterative and defined classes of search trees