On random 2-3 trees

DOI10.1007/BF00289075zbMath0369.05024OpenAlexW1983711073MaRDI QIDQ1243733

Andrew Chi-Chih Yao

Publication date: 1978

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00289075

Mathematics Subject Classification ID

Trees (05C05) Combinatorial probability (60C05) Algorithms in computer science (68W99)

Related Items (39)

Fringe analysis of synchronized parallel insertion algorithms in 2--3 trees. ⋮ Almost optimal dynamic 2-3 trees ⋮ On rotations in fringe-balanced binary trees ⋮ Balance in AVL trees and space cost of brother trees ⋮ Expected behaviour analysis of AVL trees ⋮ Bounded disorder: The effect of the index ⋮ Modeling B-tree insertion activity ⋮ Space saving generalization of \(B\)-trees with \(2/3\) utilization ⋮ Variance of storage requirements for B+-trees ⋮ Modeling splits in file structures ⋮ Expected behaviour of \(B^+\)-trees under random insertions ⋮ Some average measures in m-ary search trees ⋮ HCB-tree: a height compressed B-tree for parallel processing ⋮ Unsafe operations in B-trees ⋮ Analysis of bounded disorder ⋮ On the average number of rebalancing operations in weight-balanced trees ⋮ Aspects of insertion in random trees ⋮ Performance analysis of file organizations that use multi-bucket data leaves ⋮ (g//0,g//1,\dots ,g//k)-trees and unary OL systems ⋮ Improved bounds for the expected behaviour of AVL trees ⋮ Page usage in a quadtree index ⋮ \(B\)-trees with inserts and deletes: Why free-at-empty is better than merge-at-half ⋮ Unbalanced multiway trees improved by partial expansions ⋮ Search trees and Stirling numbers ⋮ Analytic urns ⋮ Toward a Formal Derivation of the Expected Behavior of Prefix B-Trees ⋮ Higher order analysis of random 1–2 brother trees ⋮ 2–3 brother trees ⋮ Transforming unbalanced multiway trees into a practical external data structure ⋮ Algorithms for sequential generation of combinatorial structures ⋮ On random son-trees ⋮ A comparative study of 2-3 trees and AVL trees ⋮ Two Applications of Urn Processes The Fringe Analysis of Search Trees and The Simulation of Quasi-Stationary Distributions of Markov Chains ⋮ Insertion-safeness in balanced trees ⋮ Una struttura bidimensionale per la memorizzazione dei file trasposti ⋮ Binary search trees with limited rotation ⋮ Average number of rotations access cost in iR-trees ⋮ Some average performance measures for the B-tree ⋮ Asymptotic Normality in the Generalized Polya–Eggenberger Urn Model, with an Application to Computer Data Structures

Cites Work

• Organization and maintenance of large ordered indexes
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On random 2-3 trees