You will need a TwoThreeTree class, with a TwoThreeTree constructor which takes
ID: 3728094 • Letter: Y
Question
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:
Explanation / Answer
import java.util.ArrayList;
import java.util.TreeSet;
public class TwoThreeTree {
private Node root;
private ArrayList<Integer> tracker;
public TwoThreeTree() {
root = null;
tracker = new ArrayList<Integer>();
}
public boolean insert(int x) {
System.out.println("Inserting: " + x);
if (root == null) {
root = new Node(x);
return true;
}
Node nodeInsertionPoint = traverseNodeFor(root, x);
if (tracker.contains(x)) {
return false;
}
//If node is a 2-node, regularly insert data into node.
if (!nodeInsertionPoint.isDataFull()) {
nodeInsertionPoint.addData(x);
}
//If node is a 3-node
else {
nodeInsertionPoint.addData(x);
System.out.println("Node Insertion B4 Split: " + nodeInsertionPoint);
System.out.println("Parent of Node B4 Split: " + nodeInsertionPoint.getParent());
split(nodeInsertionPoint);
}
tracker.add(x);
return true;
}
public void split(Node n) {
//Sorting the data of n.
n.sortData();
//Case: root
if (n == root) {
root = new Node(n.getMiddleData());
root.addChild(new Node(n.getLeftData()));
root.addChild(new Node(n.getRightData()));
root.orderChildren();
}
//Case: others
else {
//Single Split:
System.out.println("single split");
Node parentOfN = n.getParent();
parentOfN.addData(n.getMiddleData());
//////
n.dataList.remove(1);
//N's left and right data -> nodes to be added into parent of n.
Node leftSplitOfN = new Node(n.getLeftData());
Node rightSplitOfN = new Node(n.getRightData());
parentOfN.addChild(leftSplitOfN);
parentOfN.addChild(rightSplitOfN);
//Double Split:
if (parentOfN.numberOfChildren() == 4) {
System.out.println("double split attempt");
Node leftSplitOfParentOfN = new Node(parentOfN.getLeftData());
Node rightSplitOfParentOfN = new Node(parentOfN.getRightData());
Node parentParentOfN = new Node(parentOfN.getMiddleData());
leftSplitOfParentOfN.addChild(parentOfN.children.get(0));
leftSplitOfParentOfN.addChild(parentOfN.children.get(1));
rightSplitOfParentOfN.addChild(parentOfN.children.get(2));
rightSplitOfParentOfN.addChild(parentOfN.children.get(3));
parentOfN.removeChildren();
parentParentOfN.addChild(leftSplitOfParentOfN);
parentParentOfN.addChild(rightSplitOfParentOfN);
root = parentParentOfN;
}
}
}
public String search(int x) {
Node searchedNode = traverseNodeFor(root, x);
return searchedNode.toString();
}
private Node traverseNodeFor(Node currentNode, int data) {
if (currentNode.isLeaf()) {
return currentNode;
}
if (currentNode.contains(data)) {
System.out.println(currentNode);
return currentNode;
}
else if (data < currentNode.getLeftData()) {
return traverseNodeFor(currentNode.getLeftChild(), data);
}
else if (data > currentNode.getRightData()) {
return traverseNodeFor(currentNode.getRightChild(), data);
}
else {
return traverseNodeFor(currentNode.getMiddleChild(), data);
}
}
private class Node implements Comparable<Node>{
//If there is only one data, will be stored into leftData.
private ArrayList<Integer> dataList;
////// ^^^^^^ TRY USING AN ARRAYLIST.
private Node parent;
private ArrayList<Node> children;
public Node(int data) {
parent = null;
dataList = new ArrayList<Integer>();
dataList.add(data);
children = new ArrayList<Node>();
}
public boolean contains(int data) {
if (dataList.contains(data)) {
return true;
}
else {
return false;
}
}
public void removeChildren() {
children.clear();
}
public void addChild(Node newNode) {
System.out.println("Parent having children added: " + this);
System.out.println("Children before adding: "+children);
newNode.setParent(this);
if (children.contains(newNode)) {
children.remove(children.indexOf(newNode));
}
children.add(newNode);
this.orderChildren();
System.out.println("Children after adding: "+children);
}
public void orderChildren() {
TreeSet<Node> childrenOrderer = new TreeSet<Node>(children);
children = new ArrayList<Node>(childrenOrderer);
}
public void addData(int data) {
dataList.add(data);
this.sortData();
}
public void sortData() {
TreeSet<Integer> dataSorter = new TreeSet<Integer>();
dataSorter.addAll(dataList);
dataList = new ArrayList<Integer>(dataSorter);
}
public boolean isDataFull() {
if (dataList.size() >= 2) {
return true;
}
else {
return false;
}
}
public boolean isLeaf() {
return children.isEmpty();
}
private Node getLeftChild() {
return children.get(0);
}
private Node getMiddleChild() {
return children.get(1);
}
private Node getRightChild() {
if (children.size() == 2) {
return children.get(1);
}
else {
return children.get(2);
}
}
private Node getParent() {
return parent;
}
private void setParent(Node parent) {
this.parent = parent;
}
private int getLeftData() {
return dataList.get(0);
}
private int getRightData() {
if (dataList.size() <= 1) {
return Integer.MAX_VALUE;
}
if (dataList.size() <= 2) {
return dataList.get(1);
}
else {
return dataList.get(2);
}
}
private int getMiddleData() {
return dataList.get(1);
}
public int numberOfChildren() {
return children.size();
}
public String toString() {
if (this.isDataFull()) {
return Integer.toString(this.getLeftData()) + " "+ Integer.toString(this.getRightData());
}
else {
return Integer.toString(this.getLeftData());
}
}
public int compareTo(Node n) {
return this.getLeftData() - n.getLeftData();
}
public boolean equals(Object other) {
Node n = (Node)other;
return this.compareTo(n) == 0;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.