package hw5;

import edu.princeton.cs.algs4.Queue;

public class TwoThreeTree {

private class Node {

private int type; // the node type. Should be 2, 3, or 4

private int[] keys; // the keys in this node. Only slots 0 .. type 2 are valid

private Node[] subtrees; // the children of this node. Only slots 0 .. type -1 are valid

/**

* Construct a new 2-node

* @param k0 the key for the node

* @param st0 the left child (subtree) for the node

* @param st1 the right child (subtree) for the node

*/

public Node(int k0, Node st0, Node st1) {

type = 2;

keys = new int[3];

keys[0] = k0;

subtrees = new Node[4];

subtrees[0] = st0;

subtrees[1] = st1;

}

/**

* Create an empty node

* This constructor can be used if an emtpy node needs to be created

* that whose keys, children, and type will be set later.

* The type is set to -1 to mark it as an invalid node

*/

public Node() {

type = -1;

keys = new int[3];

subtrees = new Node[4];

}

}

/**

* Construct an empty 2-3 tree.

*/

public TwoThreeTree() {

root = null;

}

/**

* Construct a 2-3 tree given when given the keys in level order.

* A comma separates the nodes. A space separates two keys when they appear in the same node.

* For example, the level order "40 50,25,47,61 72" would produce the tree:

*

* (40 50)

* / | \

* (25) (47) (61 72)

* @param s the level order traversal of the tree.

*/

public TwoThreeTree(String s) {

if (s.length() > 0) {

String[] nodeStrings = s.split(",");

Queue q = new Queue();

String[] keys = nodeStrings[0].split(" ");

root = new Node();

root.keys[0] = Integer.parseInt(keys[0]);

root.type = 2;

if (keys.length > 1) {

root.keys[1] = Integer.parseInt(keys[1]);

root.type = 3;

}

q.enqueue(root);

int i = 1;

while (i

Node n = q.dequeue();

for(int k = 0; k

Node newNode = new Node();

keys = nodeStrings[i++].split(" ");

newNode.keys[0] = Integer.parseInt(keys[0]);

newNode.type = 2;

if (keys.length > 1) {

newNode.keys[1] = Integer.parseInt(keys[1]);

newNode.type = 3;

}

q.enqueue(newNode);

n.subtrees[k] = newNode;

}

}

}

}

private Node root; public boolean contains (int k) { / / TODO throw new RuntimeException ("Not implemented" ) ; public void add (int k) / / TODO throw new RuntimeException ("Not implemented" ) ; public int height( ) { / / TODO throw new RuntimeException ("Not implemented" ) ; public int nodeCount( ) { / / TODO throw new RuntimeException ("Not implemented" ) ;* A method for testing. * Returns true if {@code this} tree and {@code otherTree} are identical * (i. e. have the same keys in the same positions). * @param otherTree the tree to compare against * @return {@code true} if {@code this} tree and {@code otherTree} are identical * / public boolean identical (TwoThreeTree otherTree) { return identicalH(this . root, otherTree. root) ; private boolean identicalH(Node thisNode, Node otherNode) { if (thisNode == null && otherNode == null) return true; if ( thisNode == null | | otherNode == null) return false; if ( thisNode. type != otherNode. type) return false; for(int i = 0; i