This is a refreshed version of my Data Structures Library project that I worked on in my CS 201 (Data Structures & Algorithms) class. This repository contains files for a Circular Dynamic Array, Red-Black Tree, Binary Heap, and Binomial Heap. All of these Data Structures include additional methods for functionality.
Manually coding Data Structures for this project provided me with quite the challenge, however I feel that it was a valuable experience which allowed me to strengthen my programming skills and understanding of DSA. I managed a project average of 83.7%, but decided to challenge myself once again after a few months with this refresh!
Circular Dynamic Array (CircularDynamicArray.cpp):
Original code decreased by 52%
The CDA is a data structure that consists of two concepts: Circular Arrays and Dynamic Arrays.
Circular Array: An array in which the next element of the last element is the first element of the array.
Dynamic Array: An array that resizes itself once 100% full (increase by double), or 25% full (decrease by half).
Red-Black Tree (RBTree.cpp):
Original code decreased by 40%
The RBT is a variation of a balanced Binary Search Tree, with the following properties:
- Every node is either red or black.
- Every leaf (nil) is black.
- If a node is red, then both its children are black.
- Every simple path from a node to a descendant leaf contains the same number of black nodes.
Binary Heap (Heap.cpp):
A Binary Heap is a complete Binary Tree that satisfies the heap ordering property (Min Heap or Max Heap), usually represented using an array. The CDA that is included here will be used in Heap.cpp! The Binary heap featured in this library is a min heap.
Binomial Heap (BHeap.cpp):
A Binomial Heap is a set of Binomial Trees where each Binomial Tree follows the Min Heap property. There can be at most one Binomial Tree of any degree. Trees will merge together once more than one tree of each degree exists.