fig_1

While working on Swift implementation of Fortunes Algorithm for Dirichlet Tesselation and Delaunay Triangulations building i had a nice time figuring out how the Red-black trees are built. Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein aka CRLS is a great source of wisdom.

To use my implementation you can create a new Xcode Command line tool project, replace your main.swif file with the content of the following gist and run.

printDOT() method prints DOT language representation of the tree. If you paste digraph G {...} and it’s contents to the http://www.webgraphviz.com website and hit “Sumbit”, you will see that the tree is balanced and nice.

I encourage you to experiment and have fun. For more intuition see this Amazing algorithms visualisation website: www.cs.usfca.edu

You may never use Quicksort or RedBlack tree explicitly in practice, yet Algorithms study help us to develop brain. Which is kinda required for software development.

Have fun!