Hallo Leute, hab nen Problem
und zwar soll ich im follgenden Quelltext, den ich soweit fertig habe noch einen Unterlauf einfügen, weiss aber nicht recht wie ich das machen soll. Und zwar soll sich der Baum, nach dem Löschen einzelner Knoten auf der Blattebene neu aufbauen.
Hoffe ihr könnt mir helfen. Vielleicht kann hier jemand, mal die passenden Zeilen mit einsetzten, weiss ja dass das hier sonst nicht üblich ist, aber ihr würdet mir wirklich richtig dolle helfen.
und zwar soll ich im follgenden Quelltext, den ich soweit fertig habe noch einen Unterlauf einfügen, weiss aber nicht recht wie ich das machen soll. Und zwar soll sich der Baum, nach dem Löschen einzelner Knoten auf der Blattebene neu aufbauen.
Hoffe ihr könnt mir helfen. Vielleicht kann hier jemand, mal die passenden Zeilen mit einsetzten, weiss ja dass das hier sonst nicht üblich ist, aber ihr würdet mir wirklich richtig dolle helfen.
Code:
public class Tree234{
private class Tree234Node <T extends Comparable<T>>{
private Comparable[] keys;
private Tree234Node[] children;
private Tree234Node() {
keys = new Comparable[2*order];
children = new Tree234Node[2*order+1];
}
// clonen der Knoten und Kinder
private Tree234Node(Tree234Node copy) {
keys = copy.keys.clone();
children = copy.children.clone();
}
// bestimmt Position der Knoten
private void setKeys(Comparable[] k) {
keys = k;
}
// bestimmt Position der Kinder
private void setChildren(Tree234Node[] c) {
children = c;
}
// Kinder werden auf null gesetzt
private boolean isLeaf() {
return (children[0] == null);
}
// Vergleich des Knoten mit den mögl. Kindern
private boolean find(Comparable key) {
System.out.println(this);
for (int i = 0; i < children.length; i++) {
if (i == keys.length || keys[i] == null)
return children[i].find(key); // Kind Nachfolger vom Knoten
int cmp = keys[i].compareTo(key); // sonst sucht weiter bis Nachfolger gefunden
if (cmp == 0) return true;
else if (cmp > 0 && children[i] != null)
return children[i].find(key);
else if (cmp > 0 && isLeaf()) // wenn kein Nachfolger gefunden, wird Knoten neu eingefügt
return false;
}
return false;
}
// Löschen eines Schlüssels
public boolean delete(Comparable newKey,Tree234Node returnNode){
if (!isLeaf()) {
for (int i = 0; i < children.length; i++) {
if (i == keys.length || keys[i] == null){
newKey = children[i].delete(newKey,returnNode);
newKey=null;
break;
}
int cmp = keys[i].compareTo(newKey);
if (cmp == 0) break;
else if (cmp > 0) {
newKey = children[i].delete(newKey,returnNode);
break;
}
}
}
/*
* wenn das zu löschende Element im Baum vorhanden ist,
* dann ist es in diesem Knoten (new key != null)
*/
if (newKey != null) {
int i=0;
while (i < keys.length
&& keys[i] != null
&& keys[i].compareTo(newKey) < 0)
i++;
if (i < keys.length
&& keys[i] != null
&& keys[i].compareTo(newKey) == 0){
keys[i] = null;//eigentliches löschen
newKey=null;
i++;
/*
* nehmen den nächsten Index, der muss, wenn er
* nicht null ist eine Stelle nach links
*/
}
while (i < keys.length) {
Comparable tmpKey = keys[i];//temporäre speicher variable
if (tmpKey == null) break;
Tree234Node tmpNode = children[i];//key und Inhalt muss verschoben werden
keys[i-1] = tmpKey;//einen nach links
children[i]= tmpNode;// einen nach links
i++;//kann ja noch ein Eintrag drinnen sein
}
}
return false;
}
Comparable insert(Comparable newKey,Tree234Node returnNode) {
// Einfügeknoten suchen
if (!isLeaf()) {
for (int i = 0; i < children.length; i++) {
if (i == keys.length || keys[i] == null){
newKey = children[i].insert(newKey,returnNode);
break;
}
int cmp = keys[i].compareTo(newKey);
if (cmp == 0) return null;
else if (cmp > 0) {
newKey = children[i].insert(newKey,returnNode);
break;
}
}
}
// Einfügeposition in Knoten suchen
if (newKey != null) {
int i=0;
while (i < keys.length
&& keys[i] != null
&& keys[i].compareTo(newKey) < 0)
i++;
if (i < keys.length
&& keys[i] != null
&& keys[i].compareTo(newKey) == 0)
return null;
Comparable tmpKey = null;
Tree234Node tmpNode = null;
Tree234Node newNode = new Tree234Node(returnNode);
// Einfügen und Nachfolger weiterrücken
while (i < keys.length) {
tmpKey = keys[i];
tmpNode = children[i+1];
keys[i] = newKey;
children[i+1] = (newNode == null || isLeaf()) ?
null :
newNode;
newKey = tmpKey;
newNode = tmpNode;
i++;
}
// Überlaufbehandlung
if (newKey != null) {
/*
* neuen Knoten erzeugen, Schluessel kopieren
* und aus altem Knoten loeschen
*/
tmpNode = new Tree234Node();
for (i = 0; i < order-1; i++) {
tmpNode.keys[i] = keys[order+i+1];
tmpNode.children[i] = children[order+i+1];
keys[order+i+1] = null;
children[order+i+1] = null;
}
tmpNode.children[order-1] = children[2*order]; // Ordnung des Baums bestimmt
children[2*order] = null;
tmpNode.keys[order-1] = newKey;
tmpNode.children[order] = (newNode == null || isLeaf()) ?
null :
newNode;
// mittlerer Schluessel als Rueckgabewert
newKey = keys[order];
keys[order] = null;
children[order+1] = null;
// Werte des Rueckgabeknoten setzen
returnNode.setKeys(tmpNode.keys.clone());
returnNode.setChildren(tmpNode.children.clone());
}
}
return newKey;
}
// toString Methode eingesetzt
public String toString() {
String res = "[";
for (int i = 0; i < keys.length; i++)
res = res + " " + keys[i] + " ";
res += "]";
return res;
}
// Niveau des Knotens wird bestimmt
private String toString(int level) {
String res = "";
int i = 0;
for (i = 0; i < level; i++) res += " ";
res = res + this + "\n";
for (i = 0; i < children.length; i ++)
if (children[i] != null)
res += children[i].toString(level+1);
return res;
}
}
int order;
Tree234Node root = null;
// Methoden für den Baum
public Tree234(int o) {
order = o;
root = new Tree234Node();
}
// Vergleich
public boolean find(Comparable key) {
return root.find(key);
}
// Einfügen neuer Schlüssel
public void insert(Comparable newKey) {
Tree234Node returnNode = new Tree234Node();
Comparable newRootKey = root.insert(newKey, returnNode);
if (newRootKey != null) {
Tree234Node newRoot = new Tree234Node();
newRoot.keys[0] = newRootKey;
newRoot.children[0] = root;
newRoot.children[1] = returnNode;
root = newRoot;
}
}
// Methode um Schlüssel zu löschen
public boolean delete(Comparable loeschen){
Tree234Node returnNode = new Tree234Node();
Comparable newRootKey = root.delete(loeschen, returnNode);
if (newRootKey != null) {
Tree234Node newRoot = new Tree234Node();
newRoot.keys[0] = newRootKey;
newRoot.children[0] = root;
newRoot.children[1] = returnNode;
root = newRoot;
}
return false;
}
public String toString() {
String res = "Tree234:\n------\n";
return (res + root.toString(0));
}
// Ausgabe des Baumes
public static void main(String[] args) {
Tree234 tree234 = new Tree234(2);
Integer[] inserts = {7, 19, 23, 4, 12, 17, 8, 11, 2, 9, 13};
for (Integer i : inserts) {
System.out.println("\nInsert: " + i);
tree234.insert(i);
System.out.println(tree234);
}
tree234.delete(23);
System.out.println(tree234+"test");
}
}
