首页 >
> 详细

CS590 homework 3 – Binary-Search, and Red-black Trees

The due date for this assignment is Friday, April 9th, at 11.59pm. This assignment is worth 10% of your final grade.

Any sign of collaboration will result in a 0 and being reported to the Graduate Academic Integrity Board. Late submission policy

described in the syllabus will be applied.

(100 points)

We can use binary-search and red-black trees in order to sort an array of n integers by inserting them into

an empty tree, and using a modified INORDER-TREE-WALK algorithm to copy the elements back to the

array sorted.

1. You are given an implementation of red-black trees. Implement a binary-search tree with the

corresponding functionality. You can omit the delete functionality for binary-search and red-black trees,

but you have to modify the insertion routine of the binary-search and red-black tree to not allow duplicate

values. The insertion functions should not insert a value if the value is already in the tree.

2. Modify the INORDER-TREE-WALK algorithm for binary-search and red-black trees such that it traverses

the tree in order to copy its elements back to an array, in a sorted ascending order. The number of

elements in the tree might be less than n due to the elimination of key duplicates. The function should

therefore return the number n’ of elements that were copied into the array (number of tree elements).

Notes: The algorithm relies only on the binary-search tree properties which also red-black trees satisfy.

Keep in mind that only the first n’ elements of your array are afterwards sorted. This should be

implemented in the method convert() provided in the skeleton code.

3. Modify your insertion routine for binary-search and red-black trees such that it counts the following

occurrences over the sequence of insertions.

• Counter for the number of duplicates.

• Counter for each of the insertion cases (case 1, case 2, and case 3) (red-black tree only).

• Counter for left rotate and for right rotate (red-black tree only).

You should have 1 counter for binary-search trees and 6 counters for red-black trees altogether.

4. Develop a test function for red-black trees such that, given a node of the red-black tree, traverses to

each of the accessible leaves and counts the number of black nodes on the path to the leave.

Notes: You could use your test function to verify whether or not your red-black tree implementation

satisfies red-black property 5.

5. Measure the runtime performance of your "Binary-Search Tree Sort" and "Red-Black Tree Sort" for

random, sorted, and inverse sorted inputs of size n = 50000; 65000; 80000; 95000; 110000; 125000. You

can use the provided functions create random, create sorted, create reverse sorted.

Repeat each test a number of times (usually at least 7 times) and compute the average running time and

the average counter values for each combination of input and size n. Report and comment on your results.

How do the counters change in comparison to how the running time behaves.

(You might have to adjust the value for n dependent on your computers speed, but allow each test to take

up to a couple of minutes. Start with smaller values of n and stop if one instance of the algorithm takes

more than 3 min to complete).

Remarks:

• You are not allowed to use code from online resources. Your submission will be tested against

that, and will receive a 0, and a report to the Graduate Academic Integrity Board if it is detected.

• Your report has to be typed, and submitted in a pdf file. You should provide figures that plot the

running times in relation to the input size parameters.

• No additional libraries are allowed to be used

• A Makefile is provided for both problems to build the code in the Virtual Box

• Your code has to compile, and will be graded on the Virtual Box. • The programming, and testing will take some time. Start early.

• Feel free to use the provided source code for your implementation. You have to document your

code.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-21:00
- 微信：codinghelp

- 代写 Lab 2: Threads 2022-05-10
- 辅导assessment 1. Present Your Client ... 2022-05-10
- 5Cce2sas辅导、Python，Java程序辅导 2022-05-10
- 代写brae Webb编程 2022-05-09
- 辅导csci 3110 Assignment 1 2022-05-09
- Mth2222 Assignment 2代写 2022-05-09
- Cse3bdc Assignment 2022辅导 2022-05-08
- 辅导cis 468、辅导java，Python编程 2022-05-08
- Comp Sci 4094/4194/7094 Assignment 3 D... 2022-05-07
- Cs 178: Machine Learning & Data Mining... 2022-05-07
- Data7703 Assignment 4 2022-05-07
- 讲解assignment 2: Databases 2022-04-25
- 辅导ait681 Static Analysis 2022-04-25
- Cse121 & Cse121l 编程辅导、辅导c++程序语言 2022-04-25
- 辅导iti1120 Bject-Oriented Programming 2022-04-25
- Cmt304语言辅导、辅导c++，Python编程 2022-04-25
- 辅导comp/Engn4528 Computer Vision 2022-04-24
- 辅导fin 2200 Bloomberg Investment Proj... 2022-04-24
- 辅导bism 7255 Uml Assignment 2022-04-23
- 讲解comp202 Programming Assignment 2022-04-23