Computer Science/61b/Homework/hw7/dict/Tree234.java
< Computer Science | 61b | Homework | hw7 | dict(Redirected from CS/61b/Homework/hw7/dict/Tree234.java)
- This page contains computer code. Unlike all articles on the lensowiki, which are released under the GFDL, this code is released under the GPL.
Copyright 2006, 2007 Paul Borokhov. All rights reserved.
This code is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.
The code is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
/* Tree234.java */
package dict;
/**
* A Tree234 implements an ordered integer dictionary ADT using a 2-3-4 tree.
* Only int keys are stored; no object is associated with each key. Duplicate
* keys are not stored in the tree.
*
* @author Jonathan Shewchuk, lensovet
**/
public class Tree234 extends IntDictionary {
/**
* (inherited) size is the number of keys in the dictionary.
* root is the root of the 2-3-4 tree.
*
* You may add fields if you wish, but don't change anything that
* would prevent toString() or find() from working correctly.
**/
Tree234Node root;
public Tree234() {
root = null;
size = 0;
}
/**
* toString() prints this Tree234 as a String. Each node is printed
* in the form such as (for a 3-key node)
*
* (child1)key1(child2)key2(child3)key3(child4)
*
* where each child is a recursive call to toString, and null children
* are printed as a space with no parentheses. Here's an example.
* ((1)7(11 16)22(23)28(37 49))50((60)84(86 95 100))
*
* DO NOT CHANGE THIS METHOD.
*
* @return a String representation of the 2-3-4 tree.
**/
public String toString() {
if (root == null) {
return "";
} else {
return root.toString();
}
}
/**
* printTree() prints this Tree234 as a tree, albeit sideways.
*
* You're welcome to change this method if you like. It won't be tested.
**/
public void printTree() {
if (root != null) {
root.printSubtree(0);
}
}
/**
* find() prints true if "key" is in this 2-3-4 tree; false otherwise.
*
* @param key is the key sought.
* @return true if "key" is in the tree; false otherwise.
**/
public boolean find(int key) {
Tree234Node node = root;
while (node != null) {
if (key < node.key1) {
node = node.child1;
} else if (key == node.key1) {
return true;
} else if ((node.keys == 1) || (key < node.key2)) {
node = node.child2;
} else if (key == node.key2) {
return true;
} else if ((node.keys == 2) || (key < node.key3)) {
node = node.child3;
} else if (key == node.key3) {
return true;
} else {
node = node.child4;
}
}
return false;
}
/**
* insert() inserts the key "key" into this 2-3-4 tree. If "key" is
* already present, a duplicate copy is NOT inserted.
*
* @param key is the key sought.
**/
public void insert(int key) {
Tree234Node node = root;
if (root == null) {
root = new Tree234Node(key);
size++;
return;
}
if (node.keys == 3) { // check to see if root needs breaking up
Tree234Node par = new Tree234Node(node.key2);
Tree234Node left = node; // for convenience, we will reuse the old node for keeping the first key
Tree234Node right = new Tree234Node(par, node.key3);
par.child1 = left;
par.child2 = right;
if (node.child1 != null) {
par.child2.child1 = node.child3;
par.child2.child2 = node.child4;
par.child2.child1.parent = right;
par.child2.child2.parent = right;
}
par.child1.keys = 1;
par.child1.key2 = 0;
par.child1.key3 = 0;
par.child1.child3 = null;
par.child1.child4 = null;
par.child1.parent = par;
root = par;
// reset node
node = root;
}
while (node.child1 != null) { // try to find the key, or a place to insert it
if (key < node.key1) {
node = node.child1;
} else if (key == node.key1) {
// found the same key as trying to insert - do nothing
return;
} else if ((node.keys == 1) || (key < node.key2)) {
node = node.child2;
} else if (key == node.key2) {
// do nothing
return;
} else if ((node.keys == 2) || (key < node.key3)) {
node = node.child3;
} else if (key == node.key3) {
// do nothing
return;
} else {
node = node.child4;
}
if (node.keys == 3) {
Tree234Node left = node; // we will reuse the old node for keeping the first key
Tree234Node par = node.parent;
Tree234Node right = new Tree234Node(node.key3);
right.child1 = node.child3;
right.child2 = node.child4;
if (par.keys == 1) { // unfortunately there's some duped code here, but i don't see a way around this...
if (node.key2 < par.key1) {
par.key2 = par.key1;
par.key1 = node.key2;
par.child3 = par.child2;
par.child2 = right;
par.child2.parent = par;
par.child1 = left;
par.child1.parent = par;
} else {
par.key2 = node.key2;
par.child2 = left;
par.child2.parent = par;
par.child3 = right;
par.child3.parent = par;
}
} else {
if (node.key2 < par.key1) {
par.key3 = par.key2;
par.key2 = par.key1;
par.key1 = node.key2;
par.child4 = par.child3;
par.child3 = par.child2;
par.child2 = right;
par.child2.parent = par;
par.child1 = left;
par.child1.parent = par;
} else if (node.key2 > par.key2) {
par.key3 = node.key2;
par.child3 = left;
par.child3.parent = par;
par.child4 = right;
par.child4.parent = par;
} else { // we used to be in the middle
par.key3 = par.key2;
par.key2 = node.key2;
par.child4 = par.child3;
par.child2 = left;
par.child2.parent = par;
par.child3 = right;
par.child3.parent = par;
}
}
par.keys++;
// clear remaining pointers on the old node
node.keys = 1;
node.key2 = 0;
node.key3 = 0;
node.child3 = null;
node.child4 = null;
// recheck the parent;
node = par;
}
}
if (node.keys == 1) {
if (key < node.key1) {
node.key2 = node.key1;
node.key1 = key;
} else {
node.key2 = key;
}
} else {
if (key < node.key1) {
node.key3 = node.key2;
node.key2 = node.key1;
node.key1 = key;
} else if (key > node.key2) {
node.key3 = key;
} else {
node.key3 = node.key2;
node.key2 = key;
}
}
node.keys++;
size++;
}
/**
* testHelper() prints the String representation of this tree, then
* compares it with the expected String, and prints an error message if
* the two are not equal.
*
* @param correctString is what the tree should look like.
**/
public void testHelper(String correctString) {
String treeString = toString();
System.out.println(treeString);
if (!treeString.equals(correctString)) {
System.out.println("ERROR: Should be " + correctString);
}
}
/**
* main() is a bunch of test code. Feel free to add test code of your own;
* this code won't be tested or graded.
**/
public static void main(String[] args) {
Tree234 t = new Tree234();
System.out.println("\nInserting 84.");
t.insert(84);
t.testHelper("84");
System.out.println("\nInserting 7.");
t.insert(7);
t.testHelper("7 84");
System.out.println("\nInserting 22.");
t.insert(22);
t.testHelper("7 22 84");
System.out.println("\nInserting 95.");
t.insert(95);
t.testHelper("(7)22(84 95)");
System.out.println("\nInserting 50.");
t.insert(50);
t.testHelper("(7)22(50 84 95)");
System.out.println("\nInserting 11.");
t.insert(11);
t.testHelper("(7 11)22(50 84 95)");
System.out.println("\nInserting 37.");
t.insert(37);
t.testHelper("(7 11)22(37 50)84(95)");
System.out.println("\nInserting 60.");
t.insert(60);
t.testHelper("(7 11)22(37 50 60)84(95)");
System.out.println("\nInserting 1.");
t.insert(1);
t.testHelper("(1 7 11)22(37 50 60)84(95)");
System.out.println("\nInserting 23.");
t.insert(23);
t.testHelper("(1 7 11)22(23 37)50(60)84(95)");
System.out.println("\nInserting 16.");
t.insert(16);
t.testHelper("((1)7(11 16)22(23 37))50((60)84(95))");
System.out.println("\nInserting 100.");
t.insert(100);
t.testHelper("((1)7(11 16)22(23 37))50((60)84(95 100))");
System.out.println("\nInserting 28.");
t.insert(28);
t.testHelper("((1)7(11 16)22(23 28 37))50((60)84(95 100))");
System.out.println("\nInserting 86.");
t.insert(86);
t.testHelper("((1)7(11 16)22(23 28 37))50((60)84(86 95 100))");
System.out.println("\nInserting 49.");
t.insert(49);
t.testHelper("((1)7(11 16)22(23)28(37 49))50((60)84(86 95 100))");
System.out.println("\nInserting 81.");
t.insert(81);
t.testHelper("((1)7(11 16)22(23)28(37 49))50((60 81)84(86 95 100))");
System.out.println("\nInserting 51.");
t.insert(51);
t.testHelper("((1)7(11 16)22(23)28(37 49))50((51 60 81)84(86 95 100))");
System.out.println("\nInserting 99.");
t.insert(99);
t.testHelper("((1)7(11 16)22(23)28(37 49))50((51 60 81)84(86)95(99 100))");
System.out.println("\nInserting 75.");
t.insert(75);
t.testHelper("((1)7(11 16)22(23)28(37 49))50((51)60(75 81)84(86)95" +
"(99 100))");
System.out.println("\nInserting 66.");
t.insert(66);
t.testHelper("((1)7(11 16)22(23)28(37 49))50((51)60(66 75 81))84((86)95" +
"(99 100))");
System.out.println("\nInserting 4.");
t.insert(4);
t.testHelper("((1 4)7(11 16))22((23)28(37 49))50((51)60(66 75 81))84" +
"((86)95(99 100))");
System.out.println("\nInserting 80.");
t.insert(80);
t.testHelper("(((1 4)7(11 16))22((23)28(37 49)))50(((51)60(66)75" +
"(80 81))84((86)95(99 100)))");
System.out.println("\nFinal tree:");
t.printTree();
}
}
