Applications

Maps, sets, and lists

set and map in C++ STL library java.util.TreeMap and java.util.TreeSet in Java

Linux kernel

quote:

There are a number of red-black trees in use in the kernel. The anticipatory, deadline, and CFQ I/O schedulers all employ rbtrees to track requests; the packet CD/DVD driver does the same. The high-resolution timer code uses an rbtree to organize outstanding timer requests. The ext3 filesystem tracks directory entries in a red-black tree. Virtual memory areas (VMAs) are tracked with red-black trees, as are epoll file descriptors, cryptographic keys, and network packets in the “hierarchical token bucket” scheduler.

Computational geometry

There are many applications of ordered dictionaries in computational geometry. In particular, the sweep line technique together with a balanced search tree can be used to efficiently solve problems such as

  • Various intersection problems. For example:

    • Given two simple polygons, do they intersect? Or more generally: given any set of lines, does any pair of lines intersect?
    • Given a set of rectangles (with sides parallel to the $x$ and $y$ axes), does any pair of rectangles intersect? This problem has applications in VLSI design.
    • Given a set of circles, does any pair of circles intersect?

    Note that these problems can be trivially solved in $O(n^2)$ by checking each pair of lines/rectangles/circles. Using the sweep line technique, we can find the answer in $O(n\log n)$ time.

  • Closest pair of points problem

  • Voronoi diagrams (see the Fortune’s algorithm)

References

  • Shamos, M. I., & Hoey, D. (1976, October). Geometric intersection problems. In Foundations of Computer Science, 1976., 17th Annual Symposium on (pp. 208-215). IEEE. [pdf]
  • Bentley, J. L., & Ottmann, T. A. (1979). Algorithms for reporting and counting geometric intersections. Computers, IEEE Transactions on, 100(9), 643-647. [pdf]
  • Bentley, J. L., & Wood, D. (1980). An optimal worst case algorithm for reporting intersections of rectangles. Computers, IEEE Transactions on, 100(7), 571-577.

Purely functional and persistent dictionaries

Point location

References

  • Sarnak, N., & Tarjan, R. E. (1986). Planar point location using persistent search trees. Communications of the ACM, 29(7), 669-679. [pdf]

::: :::