ISSN:
1432-0541
Keywords:
Binary search tree
;
Data structure
;
Average case analysis
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract It is well known that the expected search time in anN node binary search tree generated by a random sequence of insertions isO(logN). Little has been published about the asymptotic cost when insertions and deletions are made following the usual algorithms with no attempt to retain balance. We show that after a sufficient number of updates, each consisting of choosing an element at random, removing it, and reinserting the same value, that the average search cost is Θ(N 1/2).
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01840390
Permalink