| | |
Draw the 2-3 tree that results when you insert the keys E A S Y Q U E S T I O N in that order into an initially empty tree.
|
+-----S--------+
| |
+----E O----+ +--U--+
| | | | |
A I N Q T Y
Draw the red-black tree that results when you insert the keys E A S Y Q U E S T I O N in that order into an initially empty tree.
|
+-----S-----+
| |
+========O--+ +--U--+
‖ | | |
+--E-----+ Q T Y
| |
A +==N
‖
I
Draw the 2-3 tree that results when you insert the keys 2 1 4 5 9 3 6 7 in that order into an initially empty tree.
|
+--------5-----+
| |
+--2-----+ +--7--+
| | | |
1 3 4 6 9
Draw the red-black tree that results when you insert the keys 2 1 4 5 9 3 6 7 in that order into an initially empty tree.
|
+--------5-----+
| |
+--2-----+ +--7--+
| | | |
1 +==4 6 9
‖
3
Consider the following code intended to put a new key-value pair into a red black tree. Assume the Node class is reasonably defined given its usage below, and the methods rotateLeft(), rotateRight(), and flipColors() all work as expected. Still, there is a bug in this code -- in that the lines with comments Line 1, Line 2, and Line 3 are not in the correct order. In what order should they be arranged?
private Node put(Node n, Key key, Value val) {
if (n = null) {
Node newNode = new Node(key, val, RED);
newNode.count = 1;
return newNode;
}
int cmp = key.compareTo(n.key);
if (cmp < 0) n.left = put(n.left, key, val);
else if (cmp > 0) n.right = put(n.right, key, val);
else n.val = val;
if (isRed(n.left) && isRed(n.right) flipColors(n); \\# Line 1
if (isRed(n.right) && !isRed(n.left)) n = rotateLeft(n); \\# Line 2
if (isRed(n.left) && isRed(n.left.left)) n = rotateRight(n); \\# Line 3
n.count = 1 + size(n.left) + size(n.right);
return n;
}
if (isRed(n.right) && !isRed(n.left)) n = rotateLeft(n); \\# Line 2 if (isRed(n.left) && isRed(n.left.left)) n = rotateRight(n); \\# Line 3 if (isRed(n.left) && isRed(n.right) flipColors(n); \\# Line 1
The characters U N D E R F O U R are inserted into an intially empty 2-3 tree as keys, in that order. The associated values are the ASCII values of the characters. Draw the state of the tree (showing only the keys) after each letter is inserted.
inserting U:
|
U
inserting N:
|
N U
inserting D:
|
+--N--+
| |
D U
inserting E:
|
+--N--+
| |
D E U
inserting R:
|
+---N---+
| |
D E R U
inserting F:
|
+-----E N-----+
| | |
D F R U
inserting O:
|
+-----N-----+
| |
+--E--+ +--R--+
| | | |
D F O U
(Note, inserting U and then R doesn't change the tree as these merely update
the values associated with these keys which are already in the tree.)
The characters S C A R L E T I N K are inserted into an initially empty red-black tree as keys, in that order. The associated values are the ASCII values of the characters. Draw the state of the tree (showing only the keys) after each letter is inserted.
inserting S:
|
S
inserting C:
|
+==S
‖
C
inserting A:
|
+--C--+
| |
A S
inserting R:
|
+--C-----+
| |
A +==S
‖
R
inserting L:
|
+=====R--+
‖ |
+--C--+ S
| |
A L
inserting E:
|
+========R--+
‖ |
+--C-----+ S
| |
A +==L
‖
E
inserting T:
|
+========R-----+
‖ |
+--C-----+ +==T
| | ‖
A +==L S
‖
E
inserting I:
|
+-----I-----+
| |
+--C--+ +--R-----+
| | | |
A E L +==T
‖
S
inserting N:
|
+-----I--------+
| |
+--C--+ +--R-----+
| | | |
A E +==N +==T
‖ ‖
L S
inserting K:
|
+-----I-----------+
| |
+--C--+ +=====R-----+
| | ‖ |
A E +--L--+ +==T
| | ‖
K N S
There is a bug in the following code which is intended to implement a "rotate right" operation in a red-black tree (with left-leaning red links) as needed for any insertions to the tree. Describe this bug and it's fix.
private Node rotateRight(Node n) {
Node t = n.left;
n.left = t.right;
t.right = n;
t.color = n.color;
t.size = n.size;
n.size = 1 + size(n.left) + size(n.right);
return t;
}
When inserting into a red-black tree, we only call "rotate right" when the links to $n$'s left child and left-most grandchild are both red. After the rotation the first of these red links must still be red. However, the link color is stored in the lower node (which is now a different node, i.e., $n$). Thus, we must force the color stored in $n$ to be red -- which the code above fails to do. The fix is easy, simply add the statement:
n.color = RED;
t.color = n.color;, as otherwise the color stored in node $t$ will not reflect the color of the link originally referencing $n$.
Complete the given class Movies.java by adding code in the areas specified. This class is intended to implement a Red-Black Tree for storing movie information in the form of a Movie objects whose structure is defined by Movie.java, and where one can use a method named getFromPrefix() to collect an ArrayList of all Movie objects in the tree whose longName instance variable has a given prefix.
When determining if the prefix matches the first characters of a movie's name, the matching should be done in a case-insensitive way.
The class LookupMovie.java provides a way to check your work as the sample run below demonstrates. In order to run this last class, you will need to download the following database text file and save it somewhere on your local machine: moviesDB.txt.
In case you are curious, IMDb.com publishes some of their datasets for public non-commercial use here. The moviesDB.txt this program uses is built from those publicly-available datasets.
Also, when a movie is printed as in the sample run, the first entry (often starting with "tt") is a special identifier one can use to pull up the movie online at IMDb.com. For example, to see the web page for "The Hobbit: An Unexpected Journey", go to the web page at https://www.imdb.com/title/tt0903624
Be aware, that not shown in the sample run is the program initially displaying a FileChooser dialog to allow the user to locate one of these files to open. (The code for displaying and using this FileChooser is already written and present in the LookupMovie class.)
$ java LookupMovie↵ Preparing to read /Users/pauloser/Desktop/data/movies.txt... Inserted 10000 records. Inserted 20000 records. Inserted 30000 records. Inserted 40000 records. . . . Inserted 650000 movies into the collection. Inserted 660000 movies into the collection. Building collection of movies complete. Inserted 667387 movies. Elapsed time = 2 seconds. Enter prefix of movie to search for: q to quit King Kong tt9542460 2016 140min King Kong - FAN FILM tt7733440 2018 116min King Kong tt1959437 - - King Kong tt13153924 2020 90min King Kong en Asunción tt0360717 2005 187min King Kong tt0242576 1962 142min King Kong tt0091344 1986 105min King Kong Lives tt0074751 1976 134min King Kong tt0056142 1963 91min King Kong vs. Godzilla tt0087560 1985 80min King Kongs Faust tt1663652 2010 72min King Kongs Tränen tt0024216 1933 100min King Kong the hobbi tt0903624 2012 169min The Hobbit: An Unexpected Journey tt2310332 2014 144min The Hobbit: The Battle of the Five Armies tt1170358 2013 161min The Hobbit: The Desolation of Smaug tt4171362 2014 72min The Hobbit: The Swedolation of Smaug tHe BrIdE oF fRaNkEnStEin tt3402260 2013 57min The Bride of Frankenstein