
doi: 10.1007/bf02943273
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))\).
searching algorithm, Graph theory (including graph drawing) in computer science, deletion algorithm, node-visit cost, insertion algorithm, Searching and sorting, Trees
searching algorithm, Graph theory (including graph drawing) in computer science, deletion algorithm, node-visit cost, insertion algorithm, Searching and sorting, Trees
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
