Homework 8 (Due date: Dec 8, 1999, 12 PM)
You must follow the specifications below. Otherwise, points will be deducted.
You are not allowed to change the return types or parameters of any methods
You must make all methods and valuables public.
Classes that you need to write are ...
rbitem (lower case)
RedBlackTree
CheckedList
rbitem - extends the Item class
You must have a value called color which keeps track of the color of the item.
color = 0 means red
color = 1 means black
color = 2 means double black
RedBlackTree - implements RedBlackLocator interface
You must have a value called rbtree which is an object of LinkedBinaryTree
You need to implement all methods in the interface RedBlackLocator.
You need to implement a method called public String toKeyString(Board b)
What the method does is to create a unique key string that represents the board. See below to see how to create the key string
find method -- accepts an object of Board as the only parameter, returns the position where you find the Board. It returns null if the Board is not in the tree.
insert method -- accepts a key string of a Board and the Board as the parametersin that order, returns the position where the Board is inserted to the tree
remove method -- accepts a position, returns the key string
CheckedList - rewrite it so that it uses RedBlackTree.
IMPORTANT: Name the object of RedBlackTree as Checked_list
You must implement all methods that indicated in the CheckedListAbstract.java
You need to create a key for a board based on the pattern of the board. You need to convert the 16 integers to 16 hex values and form them as a String, which will be the key for the board.
For example,
| 0 |
3 |
4 |
5 |
| 10 |
11 |
14 |
15 |
| 2 |
1 |
6 |
7 |
| 8 |
9 |
12 |
13 |
The key for the above board would be 0345ABEF216789CD