Binary Search Tree and Map Implementation in C++

This project, completed as part of EECS 280 at the University of Michigan, involved implementing a Binary Search Tree (BST) and leveraging it to build a custom Map class. The focus was on designing a robust and efficient data structure that adheres to object-oriented principles while supporting key operations such as insertion, deletion, and traversal.

Project Overview

My Contribution

  • Binary Search Tree: Developed a flexible BST class supporting generic types and core operations like insertion, deletion, and lookup.

  • Map Class: Extended the BST to create a custom Map class, implementing key-value storage with efficient retrieval and updates.

  • Custom Comparators: Designed support for user-defined comparators, enabling the handling of custom objects in the BST.

  • Iterator Support: Implemented iterators for traversing the BST and Map, ensuring compatibility with modern C++ standards.

  • Extensive Testing: Wrote unit tests for edge cases (empty trees, duplicate keys, deep trees) and validated sorting invariants.

Key Features

  • Efficient Traversal: Implemented in-order, pre-order, and post-order traversal methods for data processing.

  • Custom Map Class: Built a high-level Map abstraction on top of the BST, mimicking standard library functionality.

  • Sorting Validation: Ensured the BST maintains sorting properties across all operations using invariant checks.

Skills and Tools

  • Languages: C++

  • Techniques: Data Structures, Object-Oriented Programming, Iterators, Unit Testing

  • Tools: Git, C++, Custom Test Framework

Code Access

The source code for this project is private due to the University of Michigan’s Honor Code. However, I’m happy to discuss the implementation in more detail or share access to my GitHub repository upon request. Please feel free to email me at vlamas@umich.edu