Analysis of the standard deletion algorithms in exact fit domain binary search trees

Abstract. It is well known that the expected search time in an N node binary search tree generated by a random sequence of insertions is O(log N). 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 O(N1/2)