• You will need to program a 2-3 tree as seen in the online videos posted, and discussed in 23 trees.

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

• Tree 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).

• Tree will need a size(int x) method, will return the int size of the subtree rooted at the node that contains integer x. If x is not in the tree, it should return 0.

_________________________________________________________________________________________________________________________________________________

TESTS:

import static org.junit.Assert.*; import org.junit.Test; public class GivenTreeTests { @Test public void singleNodeTree() { Tree t = new Tree(); t.insert(9); assertEquals(1, t.size(9)); assertEquals(0, t.size(8)); assertEquals(0, t.size(10)); t.insert(15); assertEquals(2, t.size(9)); assertEquals(0, t.size(8)); assertEquals(0, t.size(10)); assertEquals(2, t.size(15)); assertEquals(0, t.size(18)); t = new Tree(); t.insert(15); t.insert(9); assertEquals(2, t.size(9)); assertEquals(0, t.size(8)); assertEquals(0, t.size(10)); assertEquals(2, t.size(15)); assertEquals(0, t.size(18)); } @Test public void oneSplitLeft() { Tree t = new Tree(); t.insert(9); t.insert(15); t.insert(1); assertEquals(3, t.size(9)); assertEquals(1, t.size(15)); assertEquals(0, t.size(17)); assertEquals(0, t.size(11)); assertEquals(1, t.size(1)); assertEquals(0, t.size(0)); assertEquals(0, t.size(3)); } @Test public void oneSplitRight() { Tree t = new Tree(); t.insert(1); t.insert(9); t.insert(15); assertEquals(3, t.size(9)); assertEquals(1, t.size(15)); assertEquals(0, t.size(17)); assertEquals(0, t.size(11)); assertEquals(1, t.size(1)); assertEquals(0, t.size(0)); assertEquals(0, t.size(3)); } @Test public void oneSplitMiddle() { Tree t = new Tree(); t.insert(1); t.insert(15); t.insert(9); assertEquals(3, t.size(9)); assertEquals(1, t.size(15)); assertEquals(0, t.size(17)); assertEquals(0, t.size(11)); assertEquals(1, t.size(1)); assertEquals(0, t.size(0)); assertEquals(0, t.size(3)); } @Test public void testDuplicates() { Tree t = new Tree(); 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); assertEquals(7, t.size(9)); assertEquals(3, t.size(4)); assertEquals(3, t.size(15)); assertEquals(0, t.size(12)); assertEquals(1, t.size(13)); assertEquals(0, t.size(14)); assertEquals(0, t.size(19)); assertEquals(1, t.size(20)); assertEquals(0, t.size(21)); assertEquals(1, t.size(1)); assertEquals(0, t.size(0)); assertEquals(0, t.size(3)); assertEquals(0, t.size(6)); assertEquals(1, t.size(7)); assertEquals(0, t.size(8)); } }