首页 >
> 详细

CMPSCI 187 / Fall 2018

Binary Search Trees and Red-Black Trees

Mark Corner and Joe Chiu

1

CMPSCI 187 / Fall 2018 Binary Search Trees and Red-Black Trees

Contents

Overview 3

Learning Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

General Information [Common] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Import Project into Eclipse [Common] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Problem 1 4

What to Do . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Problem 2 5

Self-Balancing Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Red-black Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

What to Do . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Export and Submit [Common] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

Page 2 of 8

CMPSCI 187 / Fall 2018 Binary Search Trees and Red-Black Trees

Overview

In this project, you’ll start with a codebase for binary search tree (BST) similar to that presented in lectures. You’ll

need to implement several additional methods for binary search trees. Then, you’ll create a subclass of BST called

“scapegoat tree” — a simple form of a self-balancing binary search tree.

Learning Goals

• Show understanding of binary trees, and implement several non-trivial methods .

• Learn and implement scapegoat tree – a form of self-balancing trees.

• Continue to develop unit-testing skills.

General Information [Common]

Reminder: Copying partial or whole solutions, obtained from other students or elsewhere, is academic dishonesty.

Do not share your code with your classmates, and do not use your classmates’ code. If you are confused about what

constitutes academic dishonesty you should re-read the course policies. We assume you have read the course policies

in detail and by submitting this project you have provided your virtual signature in agreement with these policies.

• For some projects, it may be useful for you to write additional java files. Any java file you write MUST be

placed in the provided src directory of your Eclipse project.

• When submitting your project, be sure to remove all compilation errors. Any compilation errors will cause

the autograder to fail to run, and consequently you will receive a zero for your submission. No Exceptions!

In the test directory, we provide several JUnit tests that we refer to as the public tests. We recommend you run the

tests often and use them as starting points to test your project. In addition, some of the java files come with their own

main functions. You can run them as Java applications to interact with the project.

Be aware that the autograder will use a more comprehensive set of tests (referred to as private tests) to grade your

project. These tests are hidden from you. We recommend that you think about possible test cases and add new @Test

cases to your public test files as part of your programming discipline. In particular, you should consider:

• Do your methods handle edge cases such as integer arguments that may be positive, negative, or zero. Many

methods only accept arguments that are in a particular range.

• Does your code handle cases such as when an array or list is empty, or has reached full capacity?

More complex tests will be project-specific. To build good test cases, think about ways to exercise methods. Work out

the correct result for a call of a method with a given set of parameters by hand, then add it as a test case.

Import Project into Eclipse [Common]

Begin by downloading the starter project and importing it into your workspace. It is very important that you do not

rename this project as its name is used during the autograding process. If the project is renamed, your assignment will

not be graded, and you will receive a zero.

The imported project may have some compilation errors, but these should not prevent you from getting started. Specifically, we may provide JUnit tests for classes that do not yet exist in your code. You can still run the other JUnit tests.

After completing your code, the compilation errors should be gone.

The project should normally contain the following root items:

Page 3 of 8

CMPSCI 187 / Fall 2018 Binary Search Trees and Red-Black Trees

src This is the source folder where all code you are submitting must go. You can change anything you want in this

folder (unless otherwise specified), you can add new files, etc.

support This folder contains support code that we encourage you to use (and must be used to pass certain tests). You

must not change or add anything in this folder. To help ensure that, we suggest that you set the support folder

to be read-only. You can do this by right-clicking on it in the package explorer, choosing Properties from the

menu, choosing Resource from the list on the left of the pop-up Properties window, unchecking the Permissions

check-box for Owner-Write, and clicking the OK button. A dialog box will show with the title “Confirm recursive

changes”, and you should click on the “Yes” button.

test The test folder where all of the public unit tests are available. You can feel free to add your own tests here.

JUnit 4 A library that is used to run the test programs.

JRE System Library This is what allows Java to run; it is the location of the Java System Libraries.

If you are missing any of the above or if errors are present in the project (other than as specifically described below),

seek help immediately so you can get started on the project right away.

Problem 1

Note that for both parts of this project, you are allowed to use classes that implement the Collection class when

needed. For example, you may use java.util.ArrayList, java.util.Queue etc. in your implementations,

which eliminates the need to implement these yourself.

What to Do

Take a look at BinarySearchTree and BSTInterface.As taught in lectures, BSTs must obey the ordering

rules, and the rules must be preserved when inserting or removing nodes. Before you start, please carefully read

BSTInterface.java for specifications of each method, including expected return values and exceptions that need

to be thrown. Your first task is to implement the methods that are not yet implemented (that is, whose method bodies

are marked with TODOs). In doing so, you may find that you need or want to change other methods. This is generally

OK, with the following restrictions: Your changes must NOT break the semantics of the methods. And you may NOT

change the signatures of the public methods, or add or remove public methods to the interface.

Here are some hints for the methods we’ve left for you to complete. Again, go to BSTInterface.java to read the

full details about each method:

• contains: You should implement this method in terms of the get method.

• get: returns the element being searched for; or null if it doesn’t exist in the BST.

• getMinimum and getMaximum: returns the minimum and maximum elements respectively.

• height: The height of the tree is the height of the node that is furthest from the root. A recursive solution is

probably the easiest.

• pre- and postorderIterator: These methods are probably easiest to implement in terms of a Queue

— see inorderIterator for an example. Recursively traverse the tree in the correct order, and insert each

node into the queue as it is visited. Then, just return the result of calling iterator() on the queue.

• equals: returns true if two trees are identical (i.e. contains the equal elements and the tree structure is the

same). This method is probably easiest to express with a recursive helper method.

• sameValues: Have you already implemented a method that imposes a deterministic order on the values in the

tree? (Spoiler: yes.) If so, that will make writing this method straightforward.

Problem 1 continued on next page. . . Page 4 of 8

CMPSCI 187 / Fall 2018 Binary Search Trees and Red-Black Trees Problem 1 (continued)

• isBalanced: For this project, a tree is considered balanced when 2h ≤ n < 2h+1, where h is the tree’s

height, and n its size.

• balance: Review the lecture slides for this method.

And here are some notes on some of the utility methods we’ve provided to you, that you should NOT change: • getRoot: This method returns the root node of the tree. Normally, you wouldn’t expose such a detail in your

implementation, but we require it in order to run autograder tests. You may want to use it in your own testing,

or with the following method.

• toDotFormat: This method will output a representation of the tree rooted at the given node in the DOT

language, as described by its left and right child references. There are many programs that can read this language

and display the results. For example, http://sandbox.kidstrythisathome.com/erdos/index.

html allows to do so in your browser. This is very helpful for visualizing the tree and debugging.

Finally, if you need to allocate an array of generic (T) objects in your implementation of BinarySearchTree:

in the past we’ve been doing so with T[] array = (T[]) new Object[size]; For this project, you will

find that just doing the above you’ll still get a ClassCastException. Why? Because T is no longer an unconstrained generic type. Because in the interface its full signature is T extends Comparable, to satisfy this requirement, you’ll need an array capable of holding objects compatible with that type, so you must use

T[] array = (T[]) new Comparable[size]; instead.

Tests

You’ll note that for this problem (and the next one), we have provided only a small set of tests. These are an absolutely

minimal set of tests, and definitely do not cover all possible cases!

You will need to come up with some tests of your own. Try to think of all of the cases that could occur in each method

you write, and write tests to check each of them. Look back at previous assignments’ tests for a refresher if you’re not

sure how to do this. You will not be graded on your tests, but writing them and passing them is the only way that you

can be reasonably sure that your code works.

Problem 2

Self-Balancing Binary Trees

Just obeying the BST rule is not sufficient to achieve O(log n) performance when searching in a binary search tree. The

tree must be balanced, or close to be balanced, so that the height of the tree is on the order of O(log n). This should be

done automatically with mathematically proven guarantees. Therefore manually calling balance() yourself from

time to time does not suffice.

The solution to this problem is to build a self-balancing tree, that is, a tree that makes certain guarantees across calls

to add or remove. This enforces that the tree remains approximately balanced, and does so at an amortized low cost.

(You can think of this as an analog to the technique of resizing the array that backs an array-based stack or queue: by

doing so infrequently and in a specific way, we still achieved asymptotically good performance.) Here, we’ll focus on

an effective form of self-balancing tree: the red-black tree.

Red-black Trees

In Red-black tree, each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or

black) of the node. In this project, you can use getColor and setColor method to access the color bit of BSTNode. The

Problem 2 continued on next page. . . Page 5 of 8

G P

Subtree

A

Subtree

B X U

Subtree

D

Subtree

C L R

Subtree

E

Subtree

F

Subtree

G

Subtree

H

CMPSCI 187 / Fall 2018 Binary Search Trees and Red-Black Trees Problem 2 (continued)

colors you will need are defined as BSTNode.RED and BSTNode.BLACK. These color bits are used to ensure the tree

remains self-balanced during insertions and deletions. Red-black tree is guarantees its self-balance by satisfying the

rules as followed,

1. Each node is either red or black.

2. The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not

necessarily vice versa, this rule has little effect on analysis.

3. All leaves (node == NULL) are black. Note that the leaf node here does not contain any data.

4. If a node is red, then both its children are black.

5. Every path from a given node to any of its descendant NULL nodes contains the same number of black nodes.

These rules guarantee that for each path from the root to leaf node, you cannot find another path is more than twice as

long as it.

What to Do

You will implement RedBlackTree as a subclass to BinarySearchTree. You will need to implement the add

methods in this subclass (and the other methods are the same as BST so do not need to be re-implemented).

Before you start, please review the lecture slides which contain important details about these two methods. Below is a

quick summary. Figure 1 shows basic relationship between nodes.

Figure 1: Based on the node X, P is the parent node, L is the left child, R is the right child, G is the grandparent node,

and U is the uncle node.

To implement the add method, first use the usual BST insertion algorithm to add the new element to the BST, then

coloring the node RED. The reason to coloring RED is that it does not break the rule 5, reducing the complexity of

rebalance. At this point, you may get lucky and its parent node’s color is BLACK. If so, nothing else needs to be

done. Unfortunately, it will sometimes happen that, by coloring this node RED, you’ve broken some rules. The first

case is simpler: if the new node is root, it breaks the rule 2. In this case, you can solve it just by changing its color to

BLACK. However, if its parent’s node’s color is RED, it breaks the rule 4 and there’re more complicated cases need

to be considered. First, if the color of uncle node (another child node of grandparent node) is also RED, we repaint

both the parent and uncle node BLACK to solve the broken of rule 4. We need to repaint the grandparent node RED

Problem 2 continued on next page. . . Page 6 of 8

CMPSCI 187 / Fall 2018 Binary Search Trees and Red-Black Trees Problem 2 (continued)

to satisfy rule 5, too. After repainting, the grandparent node might break rule 2 or rule 4, with same problem as the

new node coloring, so we do recursion on the grandparent node.

Second, if the color of uncle node is BLACK and current node is on the “inside” of the sub-tree under the grandparent

node G, which means current node N is the left child of the right child of G or the right child of the left child of G, we

do rotation on parent node P and switch the role of the N and P, forcing the new current node P to be on the “outside”

of the sub-tree under G. This step is a pre-stage for the next case since the current node N cannot be rotate to the

position of G if it’s on the “inside” of the sub-tree under G. Note that the current node is changed to P because P is

child of N after the rotation. In this project, you can use rotationRight and rotationLeft to implement. See

the figure 2 and 3 to learn how rotationRight and rotationLeft work.

Figure 2: Left Rotation.

Figure 3: Right Rotation.

Third, if the color of uncle node is BLACK and current node is on the outside of the sub-tree under the grandparent

node G, which means current node N is the left child of the left child of G or the right child of the right child of G,

we repaint the parent node BLACK and the grandparent node RED, and do rotation on G. Here, we switch the color

of parent node and grandparent node to satisfy the rule 4: both children of grandparent node (RED) are BLACK.

Also, we do the rotation for satisfying the rule 5 since all paths from any given node went through G before are now

can go though P after the rotation without going through extra BLACK node. Think each case carefully, then start to

implement. Here, think it recursively will save you time to program.

Export and Submit [Common]

When you have completed this project, you should export an archive file containing the entire Java project. To do

this, click on the bst-redblack-student project in the package explorer. Then choose “File → Export” from the

menu. In the window that appears, under “General” choose “Archive File”. Then choose “Next” and enter a destination

Problem 2 continued on next page. . . Page 7 of 8

CMPSCI 187 / Fall 2018 Binary Search Trees and Red-Black Trees Problem 2 (continued)

for the output file. Be sure that the project is named bst-redblack-student (otherwise you may be exporting

the wrong project!). Save the exported file with the zip extension.

Once you have the zip file ready, you can submit it to the online autograder (Gradescope). Please see the course

website and/or documentation explaining how to use the online autograder. If you have any questions please be

prompt in asking the course staff before it is too late to submit your solution. If you encounter any errors that look like

the autograder failed and not your project, please let the instructors know.

联系我们

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

- Tsp课程作业代写、代做algorithms留学生作业、代做java，C/C 2020-06-23
- Kit107留学生作业代做、C++编程语言作业调试、Data课程作业代写、代 2020-06-23
- Sta302h1f作业代做、代写r课程设计作业、代写r编程语言作业、代做da 2020-06-22
- 代写seng 474作业、代做data Mining作业、Python，Ja 2020-06-22
- Cmpsci 187 Binary Search Trees 2020-06-21
- Comp226 Assignment 2: Strategy 2020-06-21
- Math 504 Homework 12 2020-06-21
- Math4007 Assessed Coursework 2 2020-06-21
- Optimization In Machine Learning Assig... 2020-06-21
- Homework 1 – Math 104B 2020-06-20
- Comp1000 Unix And C Programming 2020-06-20
- General Specifications Use Python In T... 2020-06-20
- Comp-206 Mini Assignment 6 2020-06-20
- Aps 105 Lab 9: Search And Link 2020-06-20
- Aps 105 Lab 9: Search And Link 2020-06-20
- Mech 203 – End-Of-Semester Project 2020-06-20
- Ms980 Business Analytics 2020-06-20
- Cs952 Database And Web Systems Develop... 2020-06-20
- Homework 4 Using Data From The China H... 2020-06-20
- Assignment 1 Build A Shopping Cart 2020-06-20