This project aims at visualizing the different rebalancing steps that happen during insertions and deletions in a binary search tree of red-black type. The rbtree.c contains a simple version of the red-black tree data structure, and main.c is the program that does insertions and deletions step-by-step and then outputs a series of dot files which can then be converted into a nice gif using dot_to_gif.sh.

dot_to_gif.sh was initially meant to help me debug my red-tree rebalancing algorithm. It uses dot (from graphviz) and convert (from imagemagick). The script translates a series of .dot files into a single .gif by making a small readjustment of the nodes so that it looks good. Readjustments are made by a script written by Emden R. Gansner(stackoverflow).

This project is the result of a home assignment I had for the course "Data Structures" during my second year of computer science at Université de Toulouse III - Paul Sabatier. A special thank you to Professor Mathias Paulin for his excellent teachings.

To test all of this, do:

sudo apt install graphviz # Linux
brew install graphviz     # macOS

make
./rbtree_to_dot -d point -r "step_"
./dot_to_gif.sh $ (find dot -name "* .dot" | sort -n -t_ -k2)

The file animation.gif will get generated (similar as to the one above) can be opened! An example of it is displayed at the top of this readme.