Explaining the Behaviour of Binary Search Trees Under Prolonged Updates: A Model and Simulations
Open Access
- 1 January 1989
- journal article
- research article
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 32 (1) , 68-75
- https://doi.org/10.1093/comjnl/32.1.68
Abstract
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.Keywords
This publication has 0 references indexed in Scilit: