Home Page > > Details

CMPSCI 187 Binary Search Trees and Red-Black Trees

 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. Specif￾ically, 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 un￾constrained generic type. Because in the interface its full signature is T extends Comparable, to sat￾isfy 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
Sub￾tree
A
Sub￾tree
B X U
Sub￾tree
D
Sub￾tree
C L R
Sub￾tree
E
Sub￾tree
F
Sub￾tree
G
Sub￾tree
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.
 
Contact Us - Email:99515681@qq.com    WeChat:codinghelp
Programming Assignment Help!