Exercises
-
Exercises 14.5, 14.12, 14.13, 14.14.
In Exercise 14.12, assume the representation from Exercise 14.11.
In Exercise 14.13, what is the complexity if the tree is height balanced?
- In the balancing algorithm for quadtrees, which runs in O(dn), where n is the size of the tree, the O(d)-part is due to searches for neighbor nodes to check if they are more finely divided than the current node. Here, d denotes the height of the quadtree. Consider maintaining a constant amount of extra information in the internal nodes of a quadtree such that this information can be obtained in constant time, thereby reducing the time complexity of the balancing algorithm to O(n).