Source: LWN.net (http://lwn.net/Articles/184495/).

See a tutorial by bmerry or lecture notes by Jeff Erickson.

# Applications

## Maps, sets, and lists

`set`

and `map`

in C++ STL library `java.util.TreeMap`

and `java.util.TreeSet`

in Java

## Linux kernel

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]

::: :::