## Exercises - 2-3 Trees and Red-Black Trees

1. 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

2. 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

3. 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

4. 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

5. 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

6. 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.)

7. 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


8. 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;

Importantly, however -- this addition must happen after the statement: t.color = n.color;, as otherwise the color stored in node $t$ will not reflect the color of the link originally referencing $n$.

9. 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↵
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