N
nody
Gast
Hallo, habe ein Problem mit der Programmierung eines 2-3 Baums
Hänge bei der Einfügeoperation und weiss nichtmehr weiter(habe schon endlos gegoogled aber kriegs echt nicht hin
)
Also das was Ich bis jetzt habe funktioniert grundsätzlich, aber sobald ein Knoten nach oben hin "durchgereicht" werden muss weil eine Aufteilung des Elternknotens notwendig ist, verliere Ich alle darunterliegenden Referenzen.
Hier ein Beispiel dass Ich ebenfalls als Testfall benutze:
http://www.maths.lse.ac.uk/Courses/MA407/23trees.html
Im Beispiel versagt mein Baum beim einfügen von "e" da dass splitten nach oben durchgereicht werden müsste
bin schon ziemlich durch nun, hoffe wirklich mir kann jemand helfen (mir bleibt dann noch c-k-t)
Habe bisher dass hier:
Die Knotenklasse
Der Baum:
Hänge bei der Einfügeoperation und weiss nichtmehr weiter(habe schon endlos gegoogled aber kriegs echt nicht hin
)Also das was Ich bis jetzt habe funktioniert grundsätzlich, aber sobald ein Knoten nach oben hin "durchgereicht" werden muss weil eine Aufteilung des Elternknotens notwendig ist, verliere Ich alle darunterliegenden Referenzen.
Hier ein Beispiel dass Ich ebenfalls als Testfall benutze:
http://www.maths.lse.ac.uk/Courses/MA407/23trees.html
Im Beispiel versagt mein Baum beim einfügen von "e" da dass splitten nach oben durchgereicht werden müsste
bin schon ziemlich durch nun, hoffe wirklich mir kann jemand helfen (mir bleibt dann noch c-k-t)
Habe bisher dass hier:
Die Knotenklasse
Code:
public class TreeNode{
TreeNode parent;
TreeNode leftChild;
TreeNode middleChild;
TreeNode rightChild;
Integer item1;
Integer item2;
public TreeNode(){
}
boolean isEmpty(){
return item1 == null && item2 == null;
}
boolean isTwoNode(){
return (item1 != null && item2 == null);
}
boolean isThreeNode(){
return(item1 != null && item2 != null);
}
public TreeNode(TreeNode parent){
this.parent = parent;
}
public TreeNode(int value, TreeNode parent){
this.item1 = value;
this.parent = parent;
}
public TreeNode(int minValue, int maxValue, TreeNode parent){
this.item1 = minValue;
this.item2 = maxValue;
this.parent = parent;
}
boolean hasLeftChild(){
return (leftChild != null);
}
boolean hasMiddleChild(){
return (middleChild != null);
}
boolean hasRightChild(){
return (rightChild != null);
}
boolean hasParent(){
return parent != null;
}
boolean isLeaf(){
return (this.leftChild == null && this.middleChild == null && this.rightChild == null);
}
void insert(int value){
if(item1 == null){
item1 = value;
return;
}
if(value < item1 && item2 == null){
item2 = item1.intValue();
item1 = value;
return;
}
if(value >= item1 && item2 == null){
item2 = value;
return;
}
}
@Override
public String toString(){
String sItem1 = null;
String sItem2 = null;
try{
sItem1 = ""+(char)item1.intValue();
sItem2 = ""+(char)item2.intValue();
}catch(Exception e){
}
return new String("( "+sItem1+" | "+sItem2+" )");
}
}Der Baum:
Code:
public class Tree {
public TreeNode root;
public Tree() {
root = new TreeNode();
}
public void insert(char c){
insert((int)c);
}
public void insert(int key){
//Blattknoten finden in den eingefügt werden muss:
TreeNode node = root;
while(!node.isLeaf()){
node = traverse(node, key);
}
if(!node.isThreeNode()){
node.insert(key);
}else{
split(node, key);
}
}
public void split(TreeNode node, int key){
TreeNode parent;
if(node.hasParent()){
parent = node.parent;
}else{
parent = new TreeNode();
root = parent;
}
//kleinsten, mittleren und größten wert ermitteln:
int[] arr = { node.item1, node.item2, key };
Arrays.sort(arr);
TreeNode nodemin = new TreeNode(arr[0], parent);
TreeNode nodemax = new TreeNode(arr[2], parent);
if(parent.isTwoNode()){
if(parent.item1 < nodemin.item1){
parent.middleChild = nodemin;
parent.rightChild = nodemax;
}
if(parent.item1 > nodemin.item1){
parent.leftChild = nodemin;
parent.middleChild = nodemax;
}
}else if(parent.isThreeNode()) {
}else {
parent.leftChild = nodemin;
parent.rightChild = nodemax;
}
if(!node.isLeaf()){
}
if(parent.isThreeNode()){
split(parent, arr[1]);
}else{
parent.insert(arr[1]);
}
}
private TreeNode traverse(TreeNode tmp, int newItem) {
if(tmp.isTwoNode()){
if(newItem < tmp.item1){
return tmp.leftChild;
}
if(newItem > tmp.item1){
return tmp.rightChild;
}
}else{
if(newItem < tmp.item1){
return tmp.leftChild;
}
if(newItem > tmp.item1 && newItem < tmp.item2){
return tmp.middleChild;
}
if(newItem > tmp.item2){
return tmp.rightChild;
}
}
return null;
}
public void inorder (TreeNode cur){
System.out.println(cur);
if (cur != null){
inorder(cur.leftChild);
inorder(cur.middleChild);
inorder(cur.rightChild);
}
}
}
