hi,
anyone can help with the insertion
- when insert into a 2-node -> become 3-node, then if insert again in the 3-node, how it will pass/split up the parent
- then, when the parent/root become the 3-node,how can it split up again?
Below is what i got:
public class TwoThreeNode<E extends Comparable<E>> {
protected TwoThreeNode<E> left, middle, right,parent;
protected E data1, data2;
public TwoThreeNode(E data1, E data2) {
this.data1 = data1;
this.data2 = data2;
}
public TwoThreeNode(E data1) {
this(data1, null);
}
// node type
public boolean is2Node() {
return data1 != null && data2 == null;
}
public boolean is3Node() {
return data1 != null && data2 != null && data1.compareTo(data2) < 0;
}
public boolean isLeafNode() {
return left == null && middle == null && right == null;
}
// getters
public TwoThreeNode<E> getLeft() {
return left;
}
public TwoThreeNode<E> getMiddle() {
return middle;
}
public TwoThreeNode<E> getRight() {
return right;
}
public TwoThreeNode<E> getParent() {
return parent;
}
public E getData1() {
return data1;
}
public E getData2() {
return data2;
}
// setters
public void setLeft(TwoThreeNode<E> n) {
left = n;
left.setParent(this);
}
public void setMiddle(TwoThreeNode<E> n) {
middle = n;
middle.setParent(this);
}
public void setRight(TwoThreeNode<E> n) {
right = n;
right.setParent(this);
}
public void setParent(TwoThreeNode<E> p) {
parent = p;
}
public void setData1(E d) {
data1 = d;
}
public void setData2(E d) {
data2 = d;
}
public String toString() {
return "[" + data1.toString() + data2.toString() + "]";
}
}
//**************** 2-3 TREE class:
public class TwoThreeTree<E extends Comparable<E>> {
TwoThreeNode<E> root = null;
public TwoThreeTree() {
root = null;
}
public TwoThreeTree(TwoThreeNode<E> root) {
this.root = root;
}
public TwoThreeTree(E data1, E data2, TwoThreeTree<E> leftTree,
TwoThreeTree<E> middleTree, TwoThreeTree<E> rightTree) {
if (data1 != null) {
// A general Tree (2 or 3), children are still NULL
TwoThreeNode<E> root = new TwoThreeNode<E>(data1, data2);
// Now set the children
if (data2 != null && data1.compareTo(data2) < 0) {// A 3-tree
root.left = (leftTree == null ? null : leftTree.root);
root.middle = (middleTree == null ? null : middleTree.root);
root.right = (rightTree == null ? null : rightTree.root);
} else {// A 2-Tree
root.left = (leftTree == null ? null : leftTree.root);
root.right = (rightTree == null ? null : rightTree.root);
}
}
}
// Get sub trees
public TwoThreeTree<E> getLeftSubTree() {
if (isLeaf() || root.left == null)
return null;
else
return new TwoThreeTree<E>(root.left);
}
public TwoThreeTree<E> getRightSubTree() {
if (isLeaf() || root.right == null)
return null;
else
return new TwoThreeTree<E>(root.right);
}
public TwoThreeTree<E> getMiddleSubTree() {
if (!is3Tree() || root.middle == null)
return null;
else
return new TwoThreeTree<E>(root.middle);
}
// tree types
boolean is3Tree() {
return root.data1 != null && root.data2 != null
&& root.data1.compareTo(root.data2) < 0;
}
boolean is2Tree() {
return root.data1 != null
&& (root.data2 == null || root.data1.compareTo(root.data2) >= 0);
}
boolean isLeaf() {
return root.data1 == null;
}
// Traverse
private void preOrderTraverse(TwoThreeNode<E> node, int depth,
StringBuilder sb) {
for (int i = 1; i < depth; i++)
sb.append(" ");
if (node == null)
sb.append("null\n");
else {
sb.append(node.toString());
sb.append("\n");
preOrderTraverse(node.left, depth + 1, sb);
preOrderTraverse(node.middle, depth + 1, sb);
preOrderTraverse(node.right, depth + 1, sb);
}
}
public String toString() {
StringBuilder sb = new StringBuilder();
preOrderTraverse(root, 1, sb);
return sb.toString();
}
/*************************************************************************/
/** SEARCH **/
/*************************************************************************/
public E search(E data) {
return search(root, data);
}
private E search(TwoThreeNode<E> r, E item) {
if (r == null) {
return null;
} else if (r.is2Node()) {
if (item.compareTo(r.data1) < 0)
return search(r.left, item);
else if (r.data1.compareTo(item) == 0)
return item;
else
return search(r.right, item);
} else if (r.is3Node()) {
if (item.compareTo(r.data1) < 0)
return search(r.left, item);
else if (item.compareTo(r.data1) == 0)
return item;
else if (item.compareTo(r.data2) < 0)
return search(r.middle, item);
else if (item.compareTo(r.data2) == 0)
return item;
else
return search(r.right, item);
}
return null;
}
/*************************************************************************/
/** INSERT **/
/*************************************************************************/
public TwoThreeNode<E> insert(E data) {
return insert(root, data);
}
private TwoThreeNode<E> insert(TwoThreeNode<E> r, E item) {
if (r == null) {
r = new TwoThreeNode<E>(item);
return r;
} else if (item.compareTo(r.data1) == 0 || item.compareTo(r.data2) == 0) {
return null;
} else if (r.isLeafNode()) {
// *************left,middle,right are NULL ********//
if (r.is2Node()) {// r(d1)
// expand to 3-Node
if (item.compareTo(r.data1) > 0) {// case 01: d1<item
r.data2 = item;
} else {// case 02: item<d1
r.data2 = r.data1;
r.data1 = item;
}
return r;
} else if (r.is3Node()) {
// SPLITING IS HERE
// r(d1<d2):
// case 01: i<d1<d2 ==> split to r(i ,d2)+ pass back middle-d1
// to r.parent
// case 02: d1<i<d2 ==> split to r(d1,d2)+ pass back middle-i to
// r.parent (of course r is unchanged )
// case 03: d1<d2<i ==> split to r(d1, i)+ pass back middle-d2
// to r.parent
E toPassBack = null;
if (item.compareTo(r.data1) < 0) {// case 01
toPassBack = r.data1;
r.data1 = item;
} else if (item.compareTo(r.data2) < 0) {// case 02
toPassBack = item;
} else {// case 03
toPassBack = r.data2;
r.data2 = item;
}
if (r.parent == root) {
//??? what here....
} else
return insert(r.parent, toPassBack);
}
} else {// r is NOT a leaf
// *************left,middle,right might be NOT NULL ********//
// ==> recursively insert into appropriate child tree
if (item.compareTo(r.data1) < 0)
return insert(r.left, item);
else if (item.compareTo(r.data2) < 0)
return insert(r.middle, item);
else
return insert(r.right, item);
}
}
}thanks