Advanced Data Structures & Time-Complexity Optimization

An exploration of advanced data structure design, focusing on strict time-complexity constraints, custom architectures, and edge-case resilience. This project includes standard ADT implementations alongside two highly optimized, custom-designed composite data structures.

Overview

This repository contains Java implementations of various algorithmic structures, built from the ground up without the use of built-in Java collections. The core objective is managing complex data relationships—such as chronological insertion order paired with dynamic maximum tracking—while adhering to rigorous $O(1)$ and $O(\log n)$ performance requirements.

Core Architectures & Implementations

1. Dynamic Set (MyDynamicSet.java)

A Dynamic Set ADT backed by a custom sorted doubly-linked list.

• Design: Prioritizes constant-time retrieval for boundary and relative queries over insertion speed.
• Performance: Achieves $O(1)$ for minimum(), maximum(), successor(), and predecessor(), with $O(n)$ insert() and search().

2. Chronological AVL Tree (MyFirstDataStructure.java)

A composite structure designed to maintain elements with rapid access to their chronological insertion order, maximum value, and logarithmic time search/deletion.

• Synergy: Combines a balanced AVL Tree with an underlying unsorted Linked List. Tree nodes maintain direct references to their list counterparts.
• Resilience: Successfully handles the "Two-Child Deletion Trap" by swapping list pointers dynamically when the AVL tree performs an in-order successor swap during a root/parent deletion.
• Performance: $O(\log n)$ for insert() and findAndRemove(). Strict $O(1)$ for first(), last(), and maximum().

3. Product Inventory System (MySecondDataStructure.java)

A highly optimized e-commerce data structure managing products with unique IDs, prices, and bounded quality tiers.

• Delta Tracking (Lazy Updates): Employs an $O(1)$ mass price raise mechanism. Price hikes are tracked in a fixed-size array, and newly inserted items normalize their base price downward to offset the delta.
• Histogram Bucketing: Leverages the bounded quality domain (0-5) using a frequency histogram, enabling strict $O(1)$ resolution for medianQuality() and avgQuality().
• Performance: $O(1)$ insert(), $O(1)$ raisePrice(), $O(1)$ mostExpensive(), and $O(n)$ findAndRemove().

Testing

The project includes a robust test suite (Tester.java) designed to validate internal pointer integrity and algorithmic constraints.

Key test cases include:

• The Offset Trap: Verifies that new products inserted after an $O(1)$ mass price raise calculate their true price correctly without double-counting the delta.
• Pointer Integrity: Ensures that chronological first() and last() pointers survive deep tree restructurings and root deletions.
• Reversal Logic: Validates custom, in-place reversal algorithms for raw arrays and linked lists.

Getting Started

Prerequisites

• Java JDK 8 or higher.
• Git.

Installation & Execution

1. Clone the repository:

   git clone https://github.com/tomerba6/dynamic-sets-implementation.git
   cd dynamic-sets-implementation
   

2. Compile the source code:

   cd src
   javac *.java
   

3. Run the test suite:

   java Tester