Description
In this project you will create a Dictionary, aka a Red Black Tree. Using the provided link to a
dictionary, insert all the words in a Red Black Tree. Create a new file with a poem and use the
dictionary as a spell checker for your poem. A spell checker just calls lookups to the dictionary to see if
a word exists. Count the time to create the dictionary and the time for spell checking. Note: To count the
time use system.currentTimeMillis().
You can go for the generic implementation of a Red Black Tree [5pts extra] or just for Strings.
In a Red Black tree the longest path from the root to a leaf cannot be more than twice of the
shortest path from the root to a leaf. This means that the tree is always balanced and the operations are
always O(lgn).
Since a Red Black Tree is a binary search tree, the following property must be true: the value in every
node is larger than the value of the left child (or any value in the left subtree) and smaller than the value
of the right child (or any value in the right subtree). Additionally, a Red Black Tree has these properties:
1. Every node is either red or black
2. Every leaf (NULL pointer) is black
3. If a node is red, both children are black
4. Every path from node to descendent leaf contains the same number of black nodes
5. The root is always black
Red-black trees consist of nodes, which are instances of the class that is given in RBNode.
Create a Red Black Tree (RBtree) class. First you will have to give the RBtree all the functionality of a
binary search tree. Don’t use Collections. Use your own code.
Here are some of the instances/methods:
• an instance variable that points to the root RBNode.
• lookup(String): searches for a key.
• printTree(): Start at the root node and traverse the tree using preorder
• addNode(String): place a new node in the binary search tree with data the parameter and color it
red.
• getSibling(RBNode): returns the sibling node of the parameter If the sibling does not exist, then
return null.
• getAunt(RBNode): returns the aunt of the parameter or the sibling of the parent node. If the aunt
node does not exist, then return null.
• getGrandparent(RBNode): Similar to getAunt() and getSibling(), returns the parent of your parent
node, if it doesn’t exist return null.
• rotateLeft(RBNode) and rotateRight(RBNode) functions: left, resp. right, rotate around the node
parameter. See next figure that demonstrates the two rotations:
• fixTree(RBNode current) recursive function: recursively traverse the tree to make it a Red Black
tree. Here is a description of all the cases for the current pointer:
1) current is the root node. Make it black and quit.
2) Parent is black. Quit, the tree is a Red Black Tree.
3) The current node is red and the parent node is red. The tree is unbalanced and you will have
to modify it in the following way.
I. If the aunt node is empty or black, then there are four sub cases that you have to process.
A) grandparent –parent(is left child)— current (is right child) case. Solution: rotate the parent left
and then continue recursively fixing the tree starting with the original parent.
B) grandparent –parent (is right child)— current (is left child) case. Solution: rotate the parent
right and then continue recursively fixing the tree starting with the original parent.
C) grandparent –parent (is left child)— current (is left child) case. Solution: make the parent
black, make the grandparent red, rotate the grandparent to the right and quit, tree is balanced.
D) grandparent –parent (is right child)— current (is right child) case. Solution: make the parent
black, make the grandparent red, rotate the grandparent to the left, quit tree is balanced.
II. Else if the aunt is red, then make the parent black, make the aunt black, make the
grandparent red and continue recursively fix up the tree starting with the grandparent.
Deliverables:
§ Include a Tester program that creates a Dictionary using a RBtree. You read the words from a text
file and insert the words in the RBtree. Use this Dictionary to lookup words of a document. Time the
creation of the Dictionary and the loopkup calls. Use compareTo() for Strings.
§ If you choose to do the generic implementation to avoid problems separate into different
files: one interface file the Visitor, one class file the Node, one class file the Red Black Trees.
§ Create a report with your findings and challenges you faced.
§ Your main grade will be based on (a) how well your tests cover your own code, (b) how well your
code does on your tests (create for all non-trivial methods), and (c) how well your code does on my
tests (which you have to add to your test file). For JUnit tests check canvas.
§ Use sjsu..cs146.project3 as your package, and Test classes should be your main java
file, along with your JUnit java tests.
§ Export your project (LastNameFirstName.zip). Upload it with your report to canvas.
§ All projects need to compile. If your program does not compile you will receive 0 points on this
project.
§ Do not use any fancy libraries. We should be able to compile it under standard installs. Include a
readme file on how to you compile the project.