You will need a TwoThreeTree class, with a TwoThreeTree constructor which takes no parameters. Once again, use the default package (no package statement).

TwoThreeTree will need an insert(int x) method, which will insert the value x into your tree. For this tree, duplicate insertions should be discarded. That is, if I insert a value into the tree which is already in the tree, do not change your tree. Your method should return true if the element is added (which should happen if it isn't already in the tree), and false if it is not added (if the number was already in the tree).

TwoThreeTree will need a search(int x) method, which will search for the value x in your tree. The method should return a String, formatted as follows. If the value x is in the tree, it will reside in a node with either one or two keys. For a one key node, the string will just be that node's key as a String. If it is a two key node, the string should be the two values, in increasing order, with a single space between them. Example: if we are searching for the number 17, and it is a key alone in a node, the search function should return "17". If it is in a node with 35, you should return "17 35". If it is in a node with 3, you should return "3 17". Do not format differently. No different spaces, no extra spaces at the end.

If the value searched for is not in the tree, your search should have terminated at a leaf node. In that case, print the contents of that leaf node, with the same formatting described above. That is, if 17 is not in the tree, and you end in a node that contains keys 18 and 20, return "18 20".

You should create your own JUnit tests as well, in a file with a name ending in Test.java or Tests.java.

In order to make some of your JUnit tests, you should build some 2-3 trees by hand, on paper, by calling insertion, and then search. Create some tests which make sure that your code gives you back exactly what you expect for those cases. It is really difficult to test your code for correctness if you don't actually test it. For correctness. Note: in your JUnit code, you can have "magic numbers" all over the place.

Heres the given tests:

import static org.junit.Assert.*; import org.junit.Test; public class TwoThreeTreeGivenTests { @Test public void singleNodeTree() { TwoThreeTree t = new TwoThreeTree(); int val = 9; t.insert(val); String expected = "9"; assertEquals(expected, t.search(val)); val = 8; assertEquals(expected, t.search(val)); val = 10; assertEquals(expected, t.search(val)); val = 15; t.insert(val); expected = "9 15"; val = 9; assertEquals(expected, t.search(val)); val = 8; assertEquals(expected, t.search(val)); val = 10; assertEquals(expected, t.search(val)); val = 15; assertEquals(expected, t.search(val)); val = 18; assertEquals(expected, t.search(val)); t = new TwoThreeTree(); val = 15; t.insert(val); val = 9; t.insert(val); val = 9; assertEquals(expected, t.search(val)); val = 8; assertEquals(expected, t.search(val)); val = 10; assertEquals(expected, t.search(val)); val = 15; assertEquals(expected, t.search(val)); val = 18; assertEquals(expected, t.search(val)); } @Test public void oneSplitLeft() { TwoThreeTree t = new TwoThreeTree(); t.insert(9); t.insert(15); t.insert(1); String expected = "9"; assertEquals(expected, t.search(9)); expected = "15"; assertEquals(expected, t.search(15)); assertEquals(expected, t.search(17)); assertEquals(expected, t.search(11)); expected = "1"; assertEquals(expected, t.search(1)); assertEquals(expected, t.search(0)); assertEquals(expected, t.search(3)); } @Test public void oneSplitRight() { TwoThreeTree t = new TwoThreeTree(); t.insert(1); t.insert(9); t.insert(15); String expected = "9"; assertEquals(expected, t.search(9)); expected = "15"; assertEquals(expected, t.search(15)); assertEquals(expected, t.search(17)); assertEquals(expected, t.search(11)); expected = "1"; assertEquals(expected, t.search(1)); assertEquals(expected, t.search(0)); assertEquals(expected, t.search(3)); } @Test public void oneSplitMiddle() { TwoThreeTree t = new TwoThreeTree(); t.insert(1); t.insert(15); t.insert(9); String expected = "9"; assertEquals(expected, t.search(9)); expected = "15"; assertEquals(expected, t.search(15)); assertEquals(expected, t.search(17)); assertEquals(expected, t.search(11)); expected = "1"; assertEquals(expected, t.search(1)); assertEquals(expected, t.search(0)); assertEquals(expected, t.search(3)); } @Test public void testDuplicates() { TwoThreeTree t = new TwoThreeTree(); t.insert(1); t.insert(9); t.insert(15); t.insert(13); t.insert(20); t.insert(7); t.insert(4); t.insert(1); t.insert(9); t.insert(15); t.insert(1); t.insert(9); t.insert(15); t.insert(13); t.insert(20); t.insert(7); t.insert(4); t.insert(13); t.insert(20); t.insert(7); t.insert(4); String expected = "9"; assertEquals(expected, t.search(9)); expected = "4"; assertEquals(expected, t.search(4)); expected = "15"; assertEquals(expected, t.search(15)); expected = "13"; assertEquals(expected, t.search(12)); assertEquals(expected, t.search(13)); assertEquals(expected, t.search(14)); expected = "20"; assertEquals(expected, t.search(19)); assertEquals(expected, t.search(20)); assertEquals(expected, t.search(21)); expected = "1"; assertEquals(expected, t.search(1)); assertEquals(expected, t.search(0)); assertEquals(expected, t.search(3)); expected = "7"; assertEquals(expected, t.search(6)); assertEquals(expected, t.search(7)); assertEquals(expected, t.search(8)); } }