Scribd
Upload
4 views3 pages

BST Algorithms: Insertion, Deletion, Search

The project involves building a Binary Search Tree (BST) with functionalities for insertion, deletion, and searching. It requires testing the performance of these operations on both skewed and balanced trees, measuring real runtime against expected time complexity. Additional features such as tree visualization, self-balancing options, and a user interface are encouraged for an enhanced grade, along with a comprehensive report and optional presentation.

Uploaded by

Rajat agarwal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views3 pages

BST Algorithms: Insertion, Deletion, Search

The project involves building a Binary Search Tree (BST) with functionalities for insertion, deletion, and searching. It requires testing the performance of these operations on both skewed and balanced trees, measuring real runtime against expected time complexity. Additional features such as tree visualization, self-balancing options, and a user interface are encouraged for an enhanced grade, along with a comprehensive report and optional presentation.

Uploaded by

Rajat agarwal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Binary Search Tree (BST) Project Requirements

Project Title:

Evaluating Binary Search Tree (BST) Algorithms: Insertion, Deletion, and Search

Goal of the Project:

- Build a Binary Search Tree (BST) in code.

- Add functions to insert, delete, and search for values.

- Test how fast these operations are in different situations (balanced tree vs. skewed tree).

- Compare real runtime with expected time complexity.

What You Need to Do (Detailed List):

1. Create a Binary Search Tree (BST)

- Make a class for the Node (with value, left, and right pointers).

- Make a BST class with these methods:

insert(value)

delete(value)

search(value)

2. Test Different Tree Shapes

A. Skewed Tree

- Insert numbers in sorted order (1, 2, 3, 4...).

- This creates a linked list-like tree.

B. Balanced Tree
- Insert in a way that keeps the tree balanced (e.g., random order).

3. Measure Performance

- Use a timer to measure insert, delete, and search times.

- Test with 10, 100, 1000, and 10,000 elements.

- Show results using graphs or tables.

4. Analyze and Compare

- Explain Big-O complexity:

Balanced Tree: O(log n)

Skewed Tree: O(n)

- Compare real run times with theory.

- Explain impact of tree shape.

5. Extra Features (for A+ grade)

A. Tree Visualization

- Show tree structure after each operation.

B. Self-Balancing Tree (Optional)

- Implement AVL or Red-Black Tree.

- Compare with standard BST.

C. Simple Interface

- Create a menu or UI to interact with the tree.

6. Write a Report

- Explain how it works with diagrams.


- Include complexity, test results, and what you learned.

7. Make a Presentation (Optional)

- 510 slides showing your work and results.

Summary of What to Submit:

Deliverable Description

-------------------------------------------------------------

Code Insert, delete, search functions

Test Results Runtime and performance analysis

Report Explanations, charts, and comparisons

Extra Features Visuals, UI, AVL comparison, etc.

Presentation Slides (Optional) Project summary slides

You might also like