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.