完成Red Black Tree的空缺部分的代码实现。
Requirement
You will submit a zip archive of your Eclipse project and a PDF with your experimental analysis. You are encouraged to discuss the assignment with your peers, but do not share solutions. Your submission will be individual.
Here is what you cannot do:
- Do not search for solutions online. This is considered a violation of the Academic Integrity Policy.
- Do not share your solutions with anyone else and do not copy solutions from another student.
- Do not post assignments or solutions to sites like Chegg or CourseHero because it is considered a violation of the Academic Integrity Policy. Plus, Miami’s Academic Integrity Office has full access to the materials on such sites.
Visit the instructor’s office hours or the TAs’ help sessions if you are stuck.
Objectives
- Modify and analyze Red-Black Trees.
- Modify the implementation of hash tables with linear probing.
Preliminaries
- Download and review the starter Java files StdRandom.java, RedBlackBST.java, and LinearProbingHashST.java are provided for you. They are part of the supporting code for the SEDGEWICK textbook.
Tasks
Red-Black Trees (Use starter files RedBlackBST.java and StdRandom.java)
Rotations
Modify the put() method in RedBlackBST.java to report the number of rotations that are performed when building a tree. (As an example, you could introduce a static variable that will keep track of the number of rotations per tree created. If you use this approach, make sure to reset the variable as needed). Create a class called RedBlackBSTTester.java to run tests and collect results. Run 1000 checks on 5,000 differently sized trees from size 1 to size 5,000, and calculate the average number of rotations per tree size. This means that for each tree size from 1-5,000 you will run 1000 tests (i.e., create 1000 trees of that size) and you will report the average number of rotations per tree size. You can use the provided StdRandom.java class to generate random numbers to insert into the RBT. Store the results in a file and then plot using an Excel spreadsheet (scatter plot with straight lines and markers, as in Mini-Project 1). Discuss the results.
Black-Height
Modify the code in RedBlackBST.java to report the black-height of the RBT, i.e., the black-height of the root. Note that there is a method called height() that reports the overall height of the RBT, not the black-height. Run tests and collect results by expanding the class called RedBlackBSTTester.java that you created for counting rotations. Run 1000 checks on 5,000 differently sized trees from size 1 to size 5,000, and calculate the average black-height for each tree size. This means that for each tree size from 1-5,000 you will run 1000 tests (i.e., create 1000 trees of that size) and you will report the average black-height per tree size. You can use the provided StdRandom.java class to generate random numbers to insert into the RBT. Store the results in a file and then plot using an Excel spreadsheet (scatter plot with straight lines and markers, as in Mini-Project 1). Discuss the results.
Hash Tables (Use starter file LinearProbingHashST.java)
Mark Deleted Entries
In the provided implementation, whenever an entry is deleted, the entries that formed a cluster with the deleted entry are all rehashed. Modify the implementation of the delete() method, so that when an entry is deleted, that slot is not set to null, but it is rather filled with a special value, which indicates that something was previously at that location but was deleted. Assume that this special value will be set in the constructor. In your tests, you will use entries with String keys and Integer values. Use the String value “deleted” as your special marker. You will also have to modify the get() method to treat the special key as a filled location and keep looking for the key in the next slot(s). Modify the put() method to treat the special marker similarly to a null key. Create a class LinearProbingHashSTTester.java to test your code. You will be graded on the quality of your tests. Make sure to include test cases in which deletions are followed by searches and insertions of new elements. At least 5 test cases are necessary.
What to Submit
Go to the folder where your eclipse workspace is saved (e.g., “C:\eclipse-workspace”) and find the folder associated with your project. Zip up all the contents in your project and submit the zip archive to Canvas. The zip file should include all the java files that you develop, including:
- Modified RedBlackBST.java file
- RedBlackBSTTester.java
- Modified LinearProbingHashST.java
- LinearProbingHashSTTester.java
- StdRandom.java
- An excel file with two tables, one reporting the average number of rotations for tree sizes from 1 to 5,000 and another one reporting the average black-height for tree sizes from 1 to 5,000.
Submit a PDF containing your report for:
The tasks related to Red-Black Trees:
- A graph (i.e., a scatter plot with straight lines and markers) showing the average number of rotations as a function of the tree size N
- A graph (i.e., a scatter plot with straight lines and markers) showing the average black-tree height as a function of the tree size N.
- A discussion of the meaning and implications of the data in the two graphs included in the report, from the point of view of the performance and usefulness of the RBT data structure.
The task related to Hash Tables:
- A description of each of the test cases you created and whether they were passed or not by your implementation.