Binary vs. AVL vs. B Tree's in C++

Cancelado Publicado Oct 7, 2008 Pagado a la entrega
Cancelado Pagado a la entrega

Be wrote in C++ and finished by 10/9/08 at midnight. You are to measure the relative performance of these three data structures(Binary Search Trees vs. AVL Trees vs. B-Trees) while implementing a basic spell checker program. The three data structures that you will be working with for this programming assignment are a binary search tree, an AVL tree and a B-Tree. We will do performance tests on the building of the three data structures as well as searching through the three data structures. The program should prompt the user for a word to be checked, search for this word in your tree, and if it is found, tell the user that the word is spelled correctly. The user will also have the option to insert a new word or delete a word. I have attached a detailed instruction and a [url removed, login to view] file below for this project.

## Deliverables

1. Provide an implementation of the Binary Search Tree Class. This class should have functions for creating an empty tree (constructor), inserting of a word into the tree, deleting a word from the tree, determining the size of the tree (that is the number of nodes in the tree), and determining the height of the tree. 2. Thoroughly test all of your BST class functionality and log the results of these tests. 3. Create an AVL tree that is derived from the BST. It should have all of the same functions as the BST. In addition, it should maintain the AVL property, which means keeping track of the balance factors and performing the appropriate rotations when insertion/deletion causes an imbalance in the tree. 4. Thoroughly test all of your AVL class functionality and log the results of these tests. 5. Implement a B-Tree Class. It should have the same functions as the BST (creating an empty tree, inserting a word, deleting a word, determining tree size and height). 6. Thoroughly test all of your B-Tree class functionality and log the results of these tests. 7. Create a driver program which will instantiate an instance of your BST, AVL and B-tree. This driver should read in the [url removed, login to view] file and then insert the values in that file into each of your trees in the order that they are found in the file. Keep track of the amount of time it takes to create the trees and record that amount in your report. 8. After reading the dictionary and creating the trees the driver program should accept user input for a word to search. This program should then search the trees to determine if the word was in the dictionary. It should let the user know if the word was there. Also it should tell the user how long it took to search for the word on each of the trees (see below). 9. The driver program should also allow the user to insert a new word into the dictionary or delete a word from the dictionary. You do not have to modify the [url removed, login to view] file, merely insert or delete nodes from your trees. 10. Since we want to get a comparable time for our different trees but searching will be relatively quick, you should run the search procedure 100,000 times for each word being searched for. -And then do the same timing for the AVL and B-tree search 11. Perform searches after varying numbers of inserts and deletes and compare the search times between the three trees. 12. Repeat these experiments for at least 4 different types of B-Trees (2-3 trees, 2-4 trees, etc.) and determine which is the most optimal for this dataset. 13. Report all of your timing in a chart comparing the three tree types and place in the lab report.

## Platform

Be wrote in C++ and able to run in Microsoft Visual C++ 2008

Odd Jobs

Nº del proyecto: #3289751

Sobre el proyecto

Proyecto remoto Activo Oct 8, 2008