Question: This is 2-3 tree java code Here is my code. It's working now. But if we don't use left, middle, right for children as the
This is 2-3 tree java code
Here is my code. It's working now. But if we don't use left, middle, right for children as the demand below
Your Node class should have, at a minimum, an array of children (of type Node), and an array of keys. Do not use left, center, right for your children, or smallKey, largeKey for your keys. Even though a legal node can only have 2 keys and 3 children max, I would actually recommend letting yourself have one extra of each, for temporary storage. If you use arrays, you might also need to keep a size variable (like numKeys or something). With an ArrayList, you won't need that, because they keep their own size, but they also seem to bring in a lot of machinery for such a small group of keys. Notice: if your items are in arrays (or ArrayLists), treat them as such: do not merely replace the string left with child[0] everywhere in your code. If you do that, even if your children are technically stored in arrays, within the code, logically, they are just stored in regular variables with weird names like child[0], where that variable name never takes advantage of the fact that it is an array.
Even if you have everything set into arrays, it doesn't really help if you treat them like normal variables. That is, if you started with left, middle, and right child variables, and then just replaced those strings with child[0], child[1], child[2], but keep the same code, it isn't very helpful. Also note, if you are just using 2 children, don't use 0 and 2, use 0 and 1. Why? That way, you can easily use loops and indices to do what you need to do. Your inner node class should probably have 3 variables: int[] key, Node[] child, and int numKeys, which will keep track of how many keys are in the current node. If you use ArrayLists, you won't need that last count. Some will also have a Node parent reference, but it isn't actually needed for what is requested here.
import java.util.ArrayList;
import java.util.TreeSet;
public class TwoThreeTree {
private Node root;
private ArrayList
public TwoThreeTree() {
root = null;
tree = new ArrayList
}
public boolean insert(int x) {
//root = null, root gets the insertion value
if (root == null) {
root = new Node(x);
return true;
}
//traverse the node
Node nodeNewPoint = traverseNodeFor(root, x);
if (tree.contains(x))
//return false if the value already in the tree
{
return false;
}
//If node is a 2-node, insert data into node.
if (!nodeNewPoint.isDataFull()) {
nodeNewPoint.addData(x); }
//Split if node is a 3-node.
else {
nodeNewPoint.addData(x);
split(nodeNewPoint);
}
tree.add(x);
return true;
}
public void split(Node n) {
n.sortData();
//Case: root
if (n == root) {
root = new Node(n.getMiddle()); //root is the middle value
//left and right node will be the children of the new root
root.addChild(new Node(n.getLeft()));
root.addChild(new Node(n.getRight()));
root.orderChildren();
}
else {
//Split 3-nodes
Node parentOfN = n.getParent();
parentOfN.addData(n.getMiddle()); //middle value is the new parent
//Set children value for the new
Node leftSplitOfN = new Node(n.getLeft());
Node rightSplitOfN = new Node(n.getRight());
parentOfN.addChild(leftSplitOfN);
parentOfN.addChild(rightSplitOfN);
//split the nodes have 3 value and 4 children
if (parentOfN.numberOfChildren() == 4) {
//split the node first
Node leftSplitOfParent = new Node(parentOfN.getLeft());
Node rightSplitOfParent = new Node(parentOfN.getRight());
Node parentParentOfN = new Node(parentOfN.getMiddle()); //new root is middle value
//get value of children
leftSplitOfParent.addChild(parentOfN.children.get(0));
leftSplitOfParent.addChild(parentOfN.children.get(1));
rightSplitOfParent.addChild(parentOfN.children.get(2));
rightSplitOfParent.addChild(parentOfN.children.get(3));
//Add left child to left split parent, right to right
parentParentOfN.addChild(leftSplitOfParent);
parentParentOfN.addChild(rightSplitOfParent);
root = parentParentOfN;
}
}
}
//Search method
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)) {
return currentNode;
}
else if (data < currentNode.getLeft()) {
return traverseNodeFor(currentNode.getLeftChild(), data);
}
else if (data > currentNode.getRight()) {
return traverseNodeFor(currentNode.getRightChild(), data);
}
else {
return traverseNodeFor(currentNode.getMiddleChild(), data);
}
}
private class Node implements Comparable
private ArrayList
private Node parent;
private ArrayList
public Node(int data) {
parent = null;
dataList = new ArrayList
dataList.add(data);
children = new ArrayList
}
public boolean contains(int data) {
if (dataList.contains(data)) {
return true;
}
else {
return false;
}
}
public void addChild(Node newNode) {
newNode.setParent(this);
if (children.contains(newNode)) {
children.remove(children.indexOf(newNode));
}
children.add(newNode);
this.orderChildren();
}
public void orderChildren() {
TreeSet
children = new ArrayList
}
public void addData(int data) {
dataList.add(data);
this.sortData();
}
public void sortData() {
TreeSet
dataSorter.addAll(dataList);
dataList = new ArrayList
}
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 getLeft() {
return dataList.get(0);
}
private int getRight() {
if (dataList.size() <= 1) {
return Integer.MAX_VALUE;
}
if (dataList.size() <= 2) {
return dataList.get(1);
}
else {
return dataList.get(2);
}
}
private int getMiddle() {
return dataList.get(1);
}
public int numberOfChildren() {
return children.size();
}
public String toString() {
if (this.isDataFull()) {
return Integer.toString(this.getLeft()) + " "+ Integer.toString(this.getRight());
}
else {
return Integer.toString(this.getLeft());
}
}
public int compareTo(Node n) {
return this.getLeft() - n.getLeft();
}
public boolean equals(Object other) {
Node n = (Node)other;
return this.compareTo(n) == 0;
}
}
}
import static org.junit.Assert.*;
import org.junit.Test;
public class Tests {
@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));
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help