On the average cost of insertions on random relaxed K-d trees

摘要

In this work we refine the average case analysis of randomized insertions and deletions in random relaxed K-d trees, first given by Broutin et al. in [3]. The analysis is based in the analysis of the split and join algorithms, which recursively call one another and are the basis of the randomized update operations under consideration. For K = 2 the average cost of insertions and deletions is Θ(log n). For K > 2, this average cost is Θ(n{sup}(Φ(k)-1)), for some Φ(K) > 1. This immediately follows from the analysis of the expected cost s{sub}n of splitting a tree of size n, which is the same as the expected cost m{sub}n of joining a pair of trees with total size n. These costs are, for K = 2, s{sub}n = m{sub}n = Θ(n) and, for K > 2, s{sub}n = m{sub}n = Ω(n{sup}(Φ(k))). In this abstract we find a closed form for the value of the exponent Φ(K), as well as the constant factor multiplying the main order term in s{sub}n.