Search Trees Write a Java application that implements the following four methods for a binary search tree of order 5 (nodes with 4 data values and 5 pointers to other nodes). The key values should be integer and the pointers should reference String data. addTraverse - Search for add position, add new data, and (if necessary) perform a "split" operation to accomodate the new data splitBTreeNode - perform a search tree split operation that converts one node into a parent node with two child nodes find - find first occurance of given data. Returns true or false findCost - Determine cost of finding given data. Cost is returned as number of comparisons Starter code for this assignment is available on the course Web site. (provided at the bottom) The following example illustrates how data should be added to the BTree structure. Insert examples --------------- Each input pair is an integer key and associated pointer to String data. The examples below show the actual string values rather than the pointers to them but the search tree nodes contain pointers to String objects. add values --> (12,"home"),(33,"add"), (20,"clean"),(50,"bean"),(32,"heat"), (42,"close"),(2, "hot") add values --> (13,"art"), ( 6, "clue"),(25,"bark"), ( 8,"more"),( 7, "red"),(4, "toy"), (11, "door") ---------------------------- Add 12,20,33,50 | 12 | 20 | 33 | 50 | ----------------------------<-- Each node also contains 4 pointers to the | | | | | | String data (not shown here) that macthes ---------------------------- up with each of the 4 key values (shown) ---------------------------- Add 32 (split) | 32 | | | | ---------------------------- | * | * | | | | --/-----\------------------- / \ / \ ---------------------------- ---------------------------- | 12 | 20 | | | | 33 | 50 | | | ---------------------------- ---------------------------- | | | | | | | | | | | | ---------------------------- ---------------------------- Add 42 ---------------------------- | 32 | | | | ---------------------------- | * | * | | | | --/-----\------------------- / \ / \ ---------------------------- ---------------------------- | 12 | 20 | | | | 33 | 42 | 50 | | ---------------------------- ---------------------------- | | | | | | | | | | | | ---------------------------- ---------------------------- Add 2 ---------------------------- | 32 | | | | ---------------------------- | * | * | | | | --/-----\------------------- / \ / \ ---------------------------- ---------------------------- | 2 | 12 | 20 | | | 33 | 42 | 50 | | ---------------------------- ---------------------------- | | | | | | | | | | | | ---------------------------- ---------------------------- Add 13 ---------------------------- | 32 | | | | ---------------------------- | * | * | | | | --/------\------------------ / \ / \ ---------------------------- ---------------------------- | 2 | 12 | 13 | 20 | | 33 | 42 | 50 | | ---------------------------- ---------------------------- | | | | | | | | | | | | ---------------------------- ---------------------------- Add 6 (split) ---------------------------- | 12 | 32 | | | ---------------------------- | * | * | * | | | --/-----\-----\------------- / \ \_____________________________ / \ \ ---------------------------- ---------------------------- ---------------------------- | 2 | 6 | | | | 13 | 20 | | | | 33 | 42 | 50 | | ---------------------------- ---------------------------- ---------------------------- | | | | | | | | | | | | | | | | | | ---------------------------- ---------------------------- ---------------------------- Add 25 ---------------------------- | 12 | 32 | | | ---------------------------- | * | * | * | | | --/-----\-----\------------- / \ \_____________________________ / \ \ ---------------------------- ---------------------------- ---------------------------- | 2 | 6 | | | | 13 | 20 | 25 | | | 33 | 42 | 50 | | ---------------------------- ---------------------------- ---------------------------- | | | | | | | | | | | | | | | | | | ---------------------------- ---------------------------- ---------------------------- Add 8 ---------------------------- | 12 | 32 | | | ---------------------------- | * | * | * | | | --/-----\-----\------------- / \ \_____________________________ / \ \ ---------------------------- ---------------------------- ---------------------------- | 2 | 6 | 8 | | | 13 | 20 | 25 | | | 33 | 42 | 50 | | ---------------------------- ---------------------------- ---------------------------- | | | | | | | | | | | | | | | | | | ---------------------------- ---------------------------- ---------------------------- Add 7 ---------------------------- | 12 | 32 | | | ---------------------------- | * | * | * | | | --/-----\-----\------------- / \ \_____________________________ / \ \ ---------------------------- ---------------------------- ---------------------------- | 2 | 6 | 7 | 8 | | 13 | 20 | 25 | | | 33 | 42 | 50 | | ---------------------------- ---------------------------- ---------------------------- | | | | | | | | | | | | | | | | | | ---------------------------- ---------------------------- ---------------------------- Add 4 (split) ---------------------------- | 6 | 12 | 32 | | ---------------------------- | * | * | * | * | | --/-----|-----\------\------ __________________________/ | \ \____________________________ / | \ \ ---------------------------- ---------------------------- ---------------------------- ---------------------------- | 2 | 4 | | | | 7 | 8 | | | | 13 | 20 | 25 | | | 33 | 42 | 50 | | ---------------------------- ---------------------------- ---------------------------- ---------------------------- | | | | | | | | | | | | | | | | | | | | | | | | ---------------------------- ---------------------------- ---------------------------- ---------------------------- Add 11 ---------------------------- | 6 | 12 | 32 | | ---------------------------- | * | * | * | * | | --/-----|-----\------\------ __________________________/ | \ \____________________________ / | \ \ ---------------------------- ---------------------------- ---------------------------- ---------------------------- | 2 | 4 | | | | 7 | 8 | 11 | | | 13 | 20 | 25 | | | 33 | 42 | 50 | | ---------------------------- ---------------------------- ---------------------------- ---------------------------- | | | | | | | | | | | | | | | | | | | | | | | | ---------------------------- ---------------------------- ---------------------------- ---------------------------- Starter Code: package source; public class BTree { BTreeNode root; boolean found; int cost; class SplitInfo { Integer splitIndex; String splitData; BTreeNode newNode; boolean rootSplit; public SplitInfo() { splitIndex = null; splitData = null; newNode = null; rootSplit = false; } } public BTree() { root = null; found = false; cost = 0; } public BTreeNode getRoot() { return root; } public void add(Integer index, String str) { SplitInfo splitResult; if (root == null) // Empty tree. Add root node { BTreeNode node = new BTreeNode(); node.indexes.add(index); node.data.add(str); root = node; } else { // Search the tree and locate the position to add content splitResult = addTraverse(index,str,root); // Check for a possible split at the top if (splitResult != null) if (splitResult.splitIndex != null) { // If the root has been split then we must create a new // root node here and connect it to the split child nodes if (splitResult.rootSplit) { BTreeNode newRoot = new BTreeNode(); newRoot.indexes.add(0, splitResult.splitIndex); newRoot.data.add(0, splitResult.splitData); newRoot.nodePtrs.add(0, root); newRoot.nodePtrs.add(1, splitResult.newNode); root = newRoot; } } } } private SplitInfo addTraverse(Integer index, String str, BTreeNode ptr) { BTreeNode nextPtr; SplitInfo splitResult = null; /**************************** * * Add your code here * ****************************/ return splitResult; } private int getAddPosition(BTreeNode ptr, Integer index) { int addPos; for (addPos=0; addPos < ptr.indexes.size(); addPos++) { if (index <= ptr.indexes.get(addPos)) break; // Found add position } return addPos; } private SplitInfo splitBTreeNode(BTreeNode ptr) { SplitInfo splitResult = new SplitInfo(); /**************************** * * Add your code here * ****************************/ return splitResult; } public boolean find(String data, BTreeNode ptr) { /**************************** * * Add your code here * ****************************/ if (found) { found = false; return true; } else return false; } public int findCost(String data, BTreeNode ptr) { /**************************** * * Add your code here * ****************************/ return cost; } public void print(BTreeNode ptr) { // This is a post-order traversal that prints from the bottom up if (ptr == null) return; for (int i=0; i < ptr.nodePtrs.size(); i++) { print(ptr.nodePtrs.get(i)); } System.out.println(); for (int i=0; i < ptr.indexes.size(); i++) { System.out.print("("+ptr.indexes.get(i)+","+ ptr.data.get(i)+") "); } if (ptr == root) System.out.println(); } } package source; import java.util.ArrayList; public class BTreeNode { ArrayList indexes; ArrayList nodePtrs; ArrayList data; public final int BTREE_ORDER = 5; public BTreeNode() { indexes = new ArrayList(); nodePtrs = new ArrayList(); data = new ArrayList(); for (int i=0; i < BTREE_ORDER; i++) { nodePtrs.add(null); } } public void clear() { indexes.clear(); data.clear(); for (int i=0; i < BTREE_ORDER; i++) { nodePtrs.add(null); } } } package source; public class PA10 { BTreeNode ptr; public PA10() { BTree bt = new BTree(); // Add data here bt.add(12,"home"); bt.add(33,"add"); bt.add(20,"clean"); bt.add(50,"bean"); bt.add(32, "heat"); bt.add(42,"close"); bt.add(2,"hot"); bt.add(13,"art"); bt.add(6,"clue"); bt.add(25, "bark"); bt.add(8,"more"); bt.add(7, "red"); bt.add(4,"toy"); bt.add(11, "door"); ptr = bt.getRoot(); bt.print(ptr); System.out.println(); if (bt.find("hot", bt.getRoot())) System.out.println("The data value 'hot' was found"); else System.out.println("The data value 'home' was not found"); if (bt.find("now", bt.getRoot())) System.out.println("The data value 'now' was found"); else System.out.println("The data value 'now' was not found"); System.out.println(); int cost1 = bt.findCost("hot", bt.getRoot()); System.out.println("The cost of searching for 'hot' was " + cost1); int cost2 = bt.findCost("now", bt.getRoot()); System.out.println("The cost of searching for 'now' was " + cost2); } public static void main(String[] args) { PA10 pa10 = new PA10(); } }