Almost optimal dynamic 2-3 trees (Q1084868)

This paper presents a principle to create almost optimal dynamical 2-3 trees based on the theory of \textit{R. Miller}, \textit{N. Pippenger}, \textit{A. Rosenberg}, and \textit{L. Snyder} [SIAM J. Comput. 8, 42-59 (1979; Zbl 0458.05026)], and gives a searching algorithm, an insertion algorithm and a deletion algorithm for these 2-3 trees. Experimental result given in this paper indicates that these 2-3 trees have very good performance at node-visit cost. We discuss asymptotic property of the 2-3 trees as \(N\to \infty\), and evaluate its approximate height, \(h=\log_{2.45}(N+1)\), where N is the number of nodes of a 2-3 tree. Finally, this paper analyses the time complexities of the algorithms, which are \(O(\log_{2.45}(N+1))\).