This is the 2-3-tree: There may be still mistakes in the insert-method, but the one I mentioned ocurred after insertion of the third element.
/*
* KundenTreeIndex.java
*
* Created on 6. September 2004, 19:14
*/
package Fahrtenverwaltung;
/**
*
* @author Juergen Warias
*/
public class KundenTreeIndex{
private KundenNode root = new KundenNode();
private int greatestIndex = 0;
KundenTreeStack stack = new KundenTreeStack();
/** Creates a new instance of KundenTreeIndex */
public KundenTreeIndex() {
}
public KundenTreeIndex(Kunde k){
root.setData(0,k);
}
// *********************
// ***** Die Suche *****
// *********************
public Kunde search (int i){
stack = new KundenTreeStack();
KundenNode x = root;
int d = 0;
boolean lessZero = false; // ff = p2; ft = p1; tt = p0; tf = p0;
boolean lessOne = false;
Kunde k = x.gibData(d);
if(x == root){
if(x.gibData(0)==null){
System.out.println("root ist null");
return null;
}
}
while(x != null){
stack.push(x);
k = x.gibData(0);
if(k.getNr() == i){ // i im Knoten x an Pos 0 enthalten ?
return k;// Ja !!
}
if(k.getNr() > i){ // Nein ?!Hole Info aus 0;
System.out.println("Search: Gehe links");
x = x.gibNext(0);
if(x==null){
System.out.println(".. aber x ist null");
}
continue;
}
else{
lessZero = false;
}
k = x.gibData(1);// i im Knoten enthalten an 1 ?
if(k != null){ // k(1) existiert ?
if(k.getNr() == i){ // Ja!!
return k;// gefunden !!
}
else{
if(k.getNr() > i){
x = x.gibNext(1);
continue;
}
else{
x = x.gibNext(2);
continue;
}
}
}
else{
x = x.gibNext(1);// Waehle Mittelzeiger als Rechten bei 1facher Besetzung
continue;
}
}
// *********** erfolglose Suche !!!
return null;
}
// **************
// *** INSERT ***
// **************
public void Insert(Kunde k){
greatestIndex++;// erster vergebener Index ist 1 !!!
int Index = greatestIndex;
Kunde s = search(Index);
k.setNummer(Index);
boolean nWurzel = false;
KundenNode n = stack.pop();
if(n == null){
if(root.gibData(0)==null){
System.out.println("eingefuegt an pos 0 in root");
root.setData(0,k);
return;
}
}
KundenNode m = stack.pop();
Kunde k1 = n.gibData(0);
Kunde k2 = n.gibData(1);
KundenNode[] neu = new KundenNode[3];
neu[0] = new KundenNode();
neu[1] = new KundenNode();
neu[2] = new KundenNode();
int oben = 0;
int herkunft = 0;
if(s != null){
System.out.println("Fataler Fehler beim einfuegen ! Nr bereits vorhanden ! (Klasse: KundenTreeIndex)");
System.exit(0);
}
while(!nWurzel){ // n ist aktueller Knoten n2 sein Vorg齨ger, k1,k2, k gesetzt und neu[]
if(k2 == null){ // 1.1: n enth nur 1 Datum
if(k1.getNr() > Index){
n.setData(1,k1);
n.setData(0,k);
n.setNext(2,n.gibNext(1));
n.setNext(1,neu[2].gibNext(1));
n.setNext(0,neu[2].gibNext(0));
// 2 nachfolger
break;
}
else{
System.out.println("Eingefuegt in root an 1");
n.setData(1,k);
System.out.println("n(0) ist "+n.gibData(0).getNr());
n.setNext(1,neu[2].gibNext(0));
n.setNext(2,neu[2].gibNext(1));
// 2 NAchfolger
break;
}
}
else{// ******** 2.x: n enthaelt 2 Daten ********
neu[0].setData(0,k1);
neu[1].setData(0,k2);
neu[2].setData(0,k);
if(k1.getNr() > k.getNr()){ //2.1
neu[0].setNext(0,neu[2]);
neu[0].setNext(1,neu[1]);
neu[1].setNext(0,n.gibNext(1));
neu[1].setNext(1,n.gibNext(2));
oben = 0;
}
else{
if(k2.getNr() < k.getNr()){//2.3
System.out.println("rechteste Pos");
neu[1].setNext(0,neu[0]);
neu[1].setNext(1,neu[2]);
neu[0].setNext(0,n.gibNext(0));
neu[0].setNext(1,n.gibNext(1));
oben = 1;
}
else{//2.2
neu[0].setNext(0,n.gibNext(0));
neu[0].setNext(1,neu[2].gibNext(0));
neu[1].setNext(0,neu[2].gibNext(1));
neu[1].setNext(1,n.gibNext(2));
neu[2].setNext(0,neu[0]);
neu[2].setNext(1,neu[1]);
oben = 2;
}
}
if(m != null){
System.out.println("Hier bin ich falsch");
if(n == root){
root = neu[oben];
break;
}
else if(n == m.gibNext(0)){
m.setNext(0,neu[oben]);
}
else if (n == m.gibNext(1)){
m.setNext(1,neu[oben]);
}
else{
m.setNext(2,neu[oben]);
}
n = m;
m=stack.pop();
k1 = n.gibData(0);
k2 = n.gibData(1);
k = neu[oben].gibData(0);
}
else{
root = neu[oben];// After this line in the debugger everything齭 still alright, but on request
System.out.println("neu Wurzel "+root.gibData(0).getNr()+" "); // pointer[0] becomes suddenly
System.out.println(root.gibNext(0)==null); //null.
nWurzel = true; /
}
}
}
}
}
/************************** That齭 the node-class:******/
/*
* KundenNode.java
*
* Created on 4. September 2004, 13:41
*/
package Fahrtenverwaltung;
import java.io.*;
/**
*
* @author Juergen Warias
*/
public class KundenNode implements Serializable{
private KundenNode [] pointer = new KundenNode[3];
private Kunde [] data = new Kunde [2];
/** Creates a new instance of KundenNode */
public KundenNode(){
}
public Kunde gibData(int i){// i muss zw 0 und 1 liegen
if(i<2){
return data;
}
else{
System.out.println("class node : Arrayindex out of bounds (data["+i+"])");
return null;
}
}
public KundenNode gibNext(int i){// i muss zw 0 und 2 liegen (0 links,1 mitte,2 rechts)
if (i<3){
return pointer;
}
else{
System.out.println("class node : Arrayindex out of bounds (pointer["+i+"])");
return null;
}
}
public void setData(int i, Kunde k){
if (i<2){
data = k;
}
else{
}
}
public void setNext(int i, KundenNode n){
if (i < 3){
pointer = n;
}
else{
}
}
}
