This repository implements many data structures and their associated algorithms, and provides a ready to use environment to easily test them.
Here's what you'll find on this document:
This repository contains a simple implementation of some (cool) data structures. This is the second part of an assignment of a course on algorithms and data structures, the first half regarding sorting algorithms, can be found here. The thought behind the project is to create an enviroment that allows for easy performance testing.
- Linked Lists (personal test, not required by the lab.)
- Binary Search Trees
- RB-Trees (Red-Black Trees)
- B-Trees
Folders and files of this project.
data-structures
├── CMakeLists.txt
├── docs
│ ├── html
│ │ └── a lot of .html and .js and .css files
│ ├── Laboratorio (1) - BST.pdf
│ ├── Laboratorio (2) - RBT.pdf
│ └── Laboratorio (3) - BT.pdf
├── LICENSE
├── Doxyfile
├── README.md
├── results
│ ├── final
│ │ ├── final.csv
│ │ └── final.png
│ ├── lab_1
│ │ ├── 1A
│ │ │ ├── lab_1A.csv
│ │ │ └── lab_1A.png
│ │ └── 1B
│ │ ├── lab_1B.csv
│ │ └── lab_1B.png
│ ├── lab_2
│ │ ├── lab_2.csv
│ │ └── lab_2.png
│ └── lab_3
│ ├── lab_3.csv
│ └── lab_3.png
├── SECURITY.md
└── src
├── headers
│ ├── data_structures
│ │ ├── b_trees.h
│ │ ├── binary_search_trees.h
│ │ ├── linked_lists.h
│ │ └── red_black_trees.h
│ └── utils
│ ├── colors.h
│ ├── experiments.h
│ ├── tests.h
│ └── utils.h
├── main.c
└── modules
├── data_structures
│ ├── b_trees.c
│ ├── binary_search_trees.c
│ ├── linked_lists.c
│ └── red_black_trees.c
├── experiments
│ ├── lab_1A.c
│ ├── lab_1B.c
│ ├── lab_2.c
│ ├── lab_3.c
│ └── lab_final.c
└── utils
├── colors.c
├── plotter.py
├── tests.c
└── utils.c
Unless I'm missing something, the project should be 100% free from:
- 🌀 Undefined Behaviors (checked with Clang's sanitizers)
- 🐛 Bugs (hopefully)
- 💦 Memory Leaks (checks made with Clang and Valgrind)
The CMakeLists.txt (build file) ensures that debug builds have runtime sanity checks (provided by Clang) and the absence of warnings*°^ hints that there aren't weird things going on. In addition, Cppcheck (a static C/C++ code analyzer) and Valgrind confirmed that everything is compliant and safe. The DEBUG flag on the code even allows performing additional correctness checks (it ensures the data structures work correctly by using many antagonist functions). I'm keeping it as a const flag to allow the compiler to better optimize the code when it is set to false (hopefully it recognizes that its value never changes and removes the if branch of the checks completely from the binary).
I'm planning to add more specific directions on how to run the project, but afaik it should be already out-of-the-box.
I use CLion as my IDE and Clang as my compiler. The project manager is CMake.
I tried to keep the algorithms as close as possible to those shown on the book Introduction to Algorithms, but it wasn't always possible. Nevertheless, I have not used any additional resources apart my professor's PDFs and my tutor's laboratory documentations.
*: Unfortunately there's a tiny warning due to my use of rand() in the gen_rand_array() function. Basically, the IDE is saying that it has limited randomness, which is fine and totally expected. Please ignore.
°: The warnings about recursive calls can be ignored too, they're necessary to make some algorithms work properly.
^: I have not yet decided how to deal with unused functions.
The following pictures show the performance of the data structures.
The X axis represents the amount of keys that will be stored on the data structures.
The Y axis represents the time it took to run some operations on them (insertion, search and deletion of keys). It is calculated using C's clock() function, provided by the time.h library.
Yes, the pictures have watermarks, because why not.
Binary Search Trees
Linked Lists, Binary Search Trees
Red-Black Trees, Binary Search Trees
B-Trees, Red-Black Trees, Binary Search Trees
B-Trees, with variable degree t.
Resources used for my studies and the implementation:
- Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2009)
- Misc laboratory slides, Eduard I. Stan (2021)
- Misc course slides, Guido Sciavicco (2021)
- The C Programming Language, Brian W. Kernighan, Dennis Ritchie (1988)
- The Art of Computer Programming, Donald E. Knuth (1998)
- B-tree, Wikipedia (as of 2022)
- Open Data Structures, Pat Morin (2013)
- B-Trees, CIS - Saint Vincent College (2016)
- The Ubiquitous B-Tree, Sally E. Fischbeck (1987)
- The Ubiquitous B-Tree, Douglas Comer (1979)
- Modern C, Jens Gustedt (2019)
- Linux's GitHub repository, Linus Torvalds (as of 2022)