Case study
Data analysis on self-built structures
A data analysis tool built on hand-written AVL trees and linked lists rather than library containers, as the final project for the data structures course.
Overview
The final project for the data structures course. A tool that loads a dataset, indexes it and answers queries over it, with every structure underneath written by hand rather than taken from the standard library.
Complexities tackled
Balancing is where the theory becomes real. An AVL tree is straightforward until the rotations, and the rotations are only exercised by the insertion orders you did not think to test. Writing one properly is the difference between having read about tree balancing and being able to reason about why a lookup degraded.
Choosing the structure for the access pattern. The tree indexes what is looked up by key; the linked list holds what is only ever walked in order. Using one for both jobs works and is measurably worse, which is exactly what the exercise is meant to demonstrate.
Stack
C++, no external libraries.
Working on something similar?
Tell me what you are building and what is in the way. I will tell you honestly whether I am the right person for it.