The goal of this C project is managing a dynamic set of in-memory bank accounts 💰 proficiently as possible (by run-time means, as a factor of set size, i.e., the amount of bank accounts in the set). Managment of the dynamic set includes supporting the basic dictionary CRUD operations and additional custom queries, such as finding maximum account in the set & finding all accounts which contain a negative balance.

Considering the tradeoffs of different data-structures for the problem in hand, those which were found as most appropriate were Red-Black 🔴⚫ and Order-Statistic 📊 balanced ⚖️ binary-search trees 🌴. These data-structures are fully implemented in this project from scratch, based on the pseudo-code of CLRS. With these data-structures all basic dictonary operations & queries take O(lgN) at most (where N is size of the dynamic set), while some (such as querying the max key record) take only constant time O(1). Besides these, the query which enumerates all M records with a negtive balance requires O(M+lgN).

Inorder to enable these optimized run times for queries both by Account id and Account balance, the program maintains two red-black trees: one manages all records in the set by balance as the primary key of the records, and other serves as an index and manages a light-weight version of the records by accout id as a primary key. Both are pointing towards each-other between parallel nodes inorder to keep in sync and bind the data regardless the index (tree) used.

For further details of the considerations taken, runtime analysis and so forth, see: detailed documentation 📑

The following two conventions are used throughout in this project:

• OS-Tree: Order-Statistic Tree (which is an extended red-black balanced binary search tree).
• RB-Tree: Red-Black Tree balanced binary search tree.

• Example 1
  • File1 Input
  • File1 Output
• Example 2
  • File2 Input
  • File2 Output

A standard red-black binary search tree: