1982/05/05 by Paul F. Dietz · 284 citations
Computer Science · Mathematics · #Advanced Database Systems and Queries #Algorithm #Algorithms and Data Compression #B-tree #Binary search tree #Binary tree #Combinatorics #Computer science #Constant (computer programming) #Context (archaeology) #Data Management and Algorithms #Data structure #Mathematics #Order (exchange) #Programming language #Representation (politics) #Search algorithm #Search tree #Theoretical computer science #Time complexity #Tree (set theory) #Tree structure #Weight-balanced tree
paper · pdf · doi:10.1145/800070.802184
openalex publication_date 1982/05/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We present a new representation for linked lists. This representation allows one to efficiently insert objects into the list and to quickly determine the order of list elements. The basic data structure, called an indexed 2-3 tree, allows one to do n inserts in O(nlogn) steps and to determine order in constant time. We speed up the algorithm by dividing the data structure up into log*n layers. The improved algorithm does n insertions and comparisons in O(nlog*n) steps. The paper concludes with two applications: determining ancestor relationships in a growing tree and maintaining a tree structured environment (context tree).