1989/01/01 by Joseph Culberson · 2 citations
Computer Science · #Distributed systems and fault tolerance #Caching and Content Delivery #Algorithms and Data Compression
paper · pdf · doi:10.1093/comjnl/32.1.68
openalex publication_date 1989/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
In this paper we present an extensive study into the long-term behaviour of binary search trees subjected to updates using the usual deletion algorithms taught in introductory textbooks. We develop a model of the behaviour of such trees which leads us to conjecture that the asymptotic average search path length is Θ(N½). We present results of large simulations which strongly support this conjecture. However, introducing a simple modification to ensure symmetry in the algorithms, the model predicts no such long-term deterioration. Simulations in fact indicate that asymptotically the average path length of such trees is less than the 1.386…log2 N average path length of trees generated from random insertion sequences.