A laboratory project on optimizing word-search operations using various Binary Search Tree (BST) variants, implemented first in Z (by Pr. Zegour at ESI Algiers) and then automatically translated to C.
This is the second lab of the ALSDD (Algorithms & Dynamic Data Structures) module at ESI Algiers. Its goals are to:
- Deepen understanding of tree data structures, especially BSTs.
- Experiment with self-adjusting BST variants to speed up word searches.
- Compare three modified BSTs (BST1–3) against a standard BST (BST0).
- Compiler required: KHAWARIZM for Z
- Behavioral variants:
- BST1: On inserting a word beginning with X, Y, or Z, rotate it to the root.
- BST2: On inserting a word beginning with X, Y, or Z, rotate it to the midpoint of its search path.
- BST3: On inserting a word not beginning with X, Y, or Z, rotate it to the root.
- Core requirements:
- Implement standard BST operations (in-order traversal, breadth-first word count, etc.) to validate structure.
- Implement single-word and range-word search methods.
- Automatic translation: Generated by the Z compiler’s translation feature.
- Enhancements:
- Improved console display with colors for better visualization.
- Implementation of BST0 (a standard, unmodified BST) for baseline comparison.
- Simulation harness to collect and output performance data (note: full simulation wasn’t completed in this lab).