Time complexity for rebuilding binary search tree / quadtree / octtree?

Question

Let's say I have a binary search tree with N nodes. Or an quad tree, or octtree, if these make any difference.

Then let's say I run an algorithm which changes all the keys in the tree. It seems to be complicated to move stuff around. Perhaps there actually is a good algorithm for this, but let's say I take the simple route: I iterate the tree, store the keys in a list, and rebuild the tree from scratch by repeated re-insertion. That is, a complete rebuild.

What time complexity can I expect to get for doing this kind of rebuilding? There are N nodes and each insertion takes log N time, but I can't wrap my head around what will happen as the tree grows.

Answer 1

Since insertion into a (balanced) BST takes Θ(log n), and the tree starts off with 0 nodes, then 1 node, then 2, etc., we get a running time of:

Θ(log 1 + log 2 + ... + log n)

From here, we can just directly say the running time is Θ(n log n) since: (related post)

log 1 + log 2 + ... + log n <= log n + log n + ... + log n
                             = n log n

log 1 + ... + log n/2 + ... + log n >= log n/2 + ... + log n
                                    >= log n/2 + ... + log n/2
                                     = n/2 log (n/2)

This is also related to tree sort.

---

We can actually prove that we can't do this faster than Θ(n log n):

It's been proven to require at least Θ(n log n) time on average to sort (using a comparison-based algorithm).

Since we can iterate over a BST in Θ(n), we can directly infer that we need at least Θ(n log n) time for the insertion.

---

Note - for a non-balanced BST, the running time would actually be Θ(n²), since the worst-case insertion time for an unbalanced BST is Θ(n), so we have:

Θ(1 + 2 + ... + n) = Θ(n(n+1)/2) = Θ(n²)

Answer 2

Assuming that you are using a self-balancing tree, then you've already answered your own question, "There are N nodes and each insertion takes log N time." It's important that the tree be self-balancing, since that is what allows you to make the statement that each insertion takes log N time. With an unbalanced tree, the insertion time could be linear worst case.