sherqo/cpp-optimal-bst-visualizer: C++ implementation and visualizer for Optimal Binary Search Trees, focusing on dynamic programming and GCC optimization. · GitHub

The Optimal Binary Search Tree (OBST) project is a C++ application designed for constructing and analyzing OBSTs interactively via a Command-Line Interface (CLI). It minimizes search costs based on provided probabilities, ensuring an efficient structure for search operations. Users can create, edit, visualize, and analyze OBSTs, along with viewing derived cost tables and probabilities.

The CLI provides a user-friendly menu to navigate through the features:

Allows users to create or modify the OBST structure.

Prints the constructed OBST in a textual format, showing parent-child relationships for each node.

Generates a graphical representation of the OBST using Graphviz:

• Outputs a .dot file.
• Converts it into an PNG image.
• Displays the image for better understanding.

Provides insights into the tree:

• Total Cost: Displays the cost of searching within the OBST.
• Efficiency Metrics: Calculates and presents efficiency statistics.

Displays the dynamic programming tables used during OBST construction:

• Cost Table: Shows the cost of all possible subtrees.
• Weight Table: Displays cumulative weights for the ranges.
• Root Table: Lists the roots of the optimal subtrees.

Shows the input data in a clean tabular format:

• Data Labels: List of keys (nodes).
• Probabilities (p): Probabilities of successful searches.
• Probabilities (q): Probabilities of unsuccessful searches.

Terminates the program.

• Define data labels and probabilities.
• The program validates input and builds the OBST using dynamic programming.

• View the cost matrix and identify the minimal search cost.
• Check the efficiency of the OBST structure.

• Generate a .dot file and visualize it graphically with Graphviz.

• Analyze the cost, weight, and root matrices to understand the OBST construction process.

The project utilizes a custom Vector class for efficient dynamic array operations.

The Settings class allows users to customize tree visualization properties (e.g., node color, shape, font size) by modifying an external settings.txt file. It enables easy personalization and persists changes across sessions. For missing files, defaults are automatically generated. This integrates seamlessly into the Visualize Tree feature, enhancing the clarity and usability of tree representations.

Required for generating graphical representations of the OBST. The .dot files are processed into PNG.

Used for:

• Algorithms
• File I/O
• Dynamic memory management
• Exception handling

MIT License file are included in the source code, explore it for more details. 2024 Ain Shams University, Cairo, Egypt, All rights reserved.