Source code online books for professionals by professionals

AVL-trees, splay trees), some of them randomized (treaps), and some of them only abstractly representing trees (skip 
lists). There are also whole families of specialized tree structures for indexing multidimensional coordinates (so-called 
spatial access methods) and distances (metric access methods). Other trees structures to check out are interval trees, 
quadtrees, and octtrees.
Exercises
6-1. Write a Python program that implements the solution to the skyline problem.
6-2. Binary search divides the sequence into two approximately equal parts in each recursive step. 
Consider ternary search, which divides the sequence into three parts. What would its asymptotic 
complexity be? What can you say about the number of comparisons in binary and ternary search?
6-3. What is the point of multiway search trees, as opposed to binary search trees?
6-4. How could you extract all keys from a binary search tree in sorted order, in linear time?
6-5. How would you delete a node from a binary search tree?
6-6. Let’s say you insert n random values into an initially empty binary search tree. What would, on 
average, be the depth of the leftmost (that is, smallest) node?
6-7. In a min-heap, when moving a large node downward, you always switch places with the smallest 
child. Why is that important?
6-8. How (or why) does the heap encoding work?
6-9. Why is the operation of building a heap linear?
6-10. Why wouldn’t you just use a balanced binary search tree instead of a heap?
6-11. Write a version of partition that partitions the elements in place (that is, moving them around in 
the original sequence). Can you make it faster than the one in Listing 6-3?
6-12. Rewrite quicksort to sort elements in place, using the in-place partition from Exercise 6-11.
6-13. Let’s say you rewrote select to choose the pivot using, for example, random.choice. What 
difference would that make? (Note that the same strategy can be used to create a randomized 
quicksort.)
6-14. Implement a version of quicksort that uses a key function, just like list.sort.
6-15. Show that a square of side d can hold at most four points that are all at least a distance of d apart. 

---

Chapter 6 
■
 DiviDe, Combine, anD Conquer
138
6-16. In the divide-and-conquer solution to the closest pair problem, you can get away with examining 
at most the next seven points in the mid-region points, sorted by y-coordinate. Show how you could 
quite easily reduce this number to five.
6-17. The element uniqueness problem is to determine whether all elements of a sequence are unique. 
This problem has a proven loglinear lower bound in the worst case for real numbers. Show that this 
means the closest pair problem also has a loglinear lower bound in the worst case. 
6-18. How could you solve the greatest slice problem in linear time?
References
Andersson, A. (1993). Balanced search trees made simple. In Proceedings of the Workshop on Algorithms and Data 
Structures (WADS), pages 60-71.
Bayer, R. (1971). Binary B-trees for virtual memory. In Proceedings of the ACM SIGFIDET Workshop on Data Description, 
Access and Control, pages 219-235.
Blum, M., Floyd, R. W., Pratt, V., Rivest, R. L., and Tarjan, R. E. (1973). Time bounds for selection. Journal of Computer 
and System Sciences, 7(4):448-461.
de  Berg,  M.,  Cheong,  O.,  van  Kreveld,  M.,  and  Overmars,  M.  (2008).  Computational  Geometry:  Algorithms  and 
Applications, third edition. Springer.

---

139