Original Project Repository
Single Header Project Repository
Summary
Developed for the Advanced Data Structures course (UFC). This project implements a database query system using an AVL tree to support exact, prefix, and range searches over personal data loaded from a CSV file. In the original project, the data structure is integrated with an interactive terminal UI (as seen in the showcase GIF). Later, the core logic was refactored into a single-header C++ library for reusability, decoupled from the accompanying CLI interface.
Lessons Learned
- Algorithm Mechanics: Consolidated theoretical concepts of self-balancing binary search trees, specifically managing height invariants and implementing left/right rotations.
- Software Design: Demonstrated the importance of isolating core data structures from application-specific I/O (CSV parsing and CLI handling) to maintain modular and reusable code.
Application and Efficiency
AVL trees are ideal for read-heavy scenarios requiring predictable, low-latency lookups and ordered data retrieval. They prevent the structural degradation common in standard unbalanced BSTs when handling sorted or skewed inputs.
Performance Comparison: Searching in a sequentially inserted dataset of 1,000,000 items.
| Metric | Standard Unbalanced BST | AVL Tree |
|---|---|---|
| Worst-case Time Complexity | \(O(n)\) | \(O(\log n)\) |
| Maximum Comparisons | 1,000,000 | ~20 |
| Comparisons Saved | 0 | 999,980 |
The AVL strict balancing guarantees logarithmic lookup times regardless of the input insertion order.