Erstellen eines Binärer Baum [Lib]

Da ich gerade etwas Zeit habe und in einem Anderen Forum jemand einen Binären Baum erstellen wollte, hab ich mir gedacht: Ich schreibe mal ein kleines Tutorial. Ich bin mir zwar noch nicht Sicher ob das ein Tutorial wird oder eine offene Lib... Sollte sich ein Mod dran stören kann er es ja grad verschieben.... Auch habe ich den Programmcode, dem das zugrundeliegt, in ein paar Stunden geschrieben, somit bin ich verbesserungsvorschläge immer offen. Achja nochwas: Ich bin Rechtschreib mäßig nicht der Beste, somit bitte ich dies zu verzeihen.

So fangen wir an: Was ist ein Binärer Baum? Hier zu verweise ich zu Wikipedia: http://de.wikipedia.org/wiki/Bin%C3%A4rbaum

Warum sollte ich das Nutzen ? Wenn man im Ram Datenspeichern möchte, kann man das auf verschiedene Arten tun. Mann kann es zum Beispiel in eine Liste schreiben. Wenn man jedoch einen Bestimmten Eintrag in der Liste sucht, muss man die Liste von Anfang bis zu gesuchten element durchlaufen. Nutzt man für die Selben Daten ein Baum, verliert man keine Vorteile und findet gesuchte elemente Schneller. Der Hier gezeigte Baum ist noch nicht perfekt. Ich werde ihn jedoch von Zeit zu Zeit optimieren.

Welche Klassen gibt es und wie hängen die zusammen?

Dazu muss ich noch sagen, das SortAble Generisch ist.

Für was sind die einzelenen Klassen/Schnittstellen da? BinarTree: Ist der Eigentliche Baum mit dieser Klasse kommuniziert man. Node: Diese Klasse stellt genau einen Knoten da. Dabei hat sie immer die Beiden Nachfolger, die auch von der Klasse Node sind. SortAble: Diese Schnittstelle sind für die Eigentlichen Elemente. Somit wird sichergestellt das jedes Komplexe Objekt in dem baum gespeichert werden kann.

Wie sehen die Klassen aus: Node:

import java.util.List;


public class Node {

    private SortAble value;
    private Node nextRight = null, nextLeft = null;

    public Node(SortAble value){
        this.value = value;

    }

    public SortAble getValue(){
        return this.value;
    }

    public void setNext(Node next){
        if (next != null){
            if (next.getValue().isBigger(getValue())){
                if (nextRight != null){
                    nextRight.setNext(next) ;
                }else{
                    nextRight = next;
                }
            }else if (next.getValue().isSmaller(getValue())){
                if (nextLeft != null){
                    nextLeft.setNext(next);
                }else{
                    nextLeft = next;
                }
            }
        }
    }


    public SortAble findValue(SortAble value){
        if (getValue().isSame(value)){
            return getValue();
        }
        if (value.isBigger(getValue())){
            if (nextRight== null){
                return null;
            }
            SortAble valueRight = nextRight.findValue(value);
            if (valueRight != null){
                return valueRight;
            }   
        }else if (value.isSmaller(getValue())){
            if (nextLeft == null){
                return null;
            }
            SortAble valueLeft = nextLeft.findValue(value);
            if (valueLeft != null){
                return valueLeft;
            }
        }


        return null;
    }


    public int getCount(){
        int right=0, left = 0;
        if (nextRight != null){
            right = nextRight.getCount();
        }
        if (nextLeft != null){
            left = nextLeft.getCount();
        }
        return left+right + 1; 
    }

    public void showNodeRekurive(){
        System.out.print(""+value);
        if (nextLeft != null){
            System.out.print("\r\n");
            System.out.print("Links:");
            nextLeft.showNodeRekurive();    
        }
        if (nextRight != null){
            System.out.print("\r\n");
            System.out.print("Rechts:");
            nextRight.showNodeRekurive();   
        }

    }

    public void fillValueToList(List<SortAble> list){
        list.add(getValue());
        if (nextLeft != null){
            nextLeft.fillValueToList(list);
        }
        if (nextRight != null){
            nextRight.fillValueToList(list);
        }
    }
} 

BinarTree:

import java.util.Iterator;
import java.util.List;
import java.util.Vector;

public class BinarTree implements Iterable<SortAble> {
private int maxFastFound = 20;
private Node rootNode = null;
private List<SortAble> fastFound = new Vector<SortAble>();


public BinarTree(){}

public BinarTree(int maxFastFound){
    this.maxFastFound = maxFastFound;
}


public void insert(SortAble g){
    if (rootNode == null){
        rootNode = new Node(g);
    }else{
        rootNode.setNext(new Node(g));
    }

}


public void showTree(){
    rootNode.showNodeRekurive();
}


private SortAble lookInFastFound(SortAble value){
    for(SortAble one : fastFound){
        if (one.isSame(value)){
            return one;
        }
    }
    return null;
}

private void saveToFastFound(SortAble value){
    if (value == null){
        return;
    }
    if (fastFound.size() ==  maxFastFound){
        fastFound.remove(0);
    }
    fastFound.add(value);
}

public SortAble getValue(SortAble value){
    SortAble foundValue = lookInFastFound(value);
    if (foundValue == null){
        foundValue = rootNode.findValue(value);
        saveToFastFound(foundValue);
    }
    return foundValue;
}

public int getCount(){
    return rootNode.getCount();
}


@Override
public Iterator<SortAble> iterator() {
    Vector<SortAble> result = new Vector<SortAble>();
    rootNode.fillValueToList(result);
    return result.iterator();
}

}

SortAble:

public interface SortAble<G> {
public boolean isBigger(G other);
public boolean isSmaller(G other);
public boolean isSame(G other);

}

Hier noch ein kleines Bespiel der Nutzung:

Nimmt als Bespiel, einen Klasse die die Schnittstelle SortAble implementiert:

 public class TreeExample implements SortAble<TreeExample>{

private int value;
private String text ;
public TreeExample (int value, String text){
    this.value = value;
    this.text = text;
}

public int getValue(){
    return value;
}

@Override
public boolean isBigger(TreeExample other) {
    return value > other.getValue();
}

@Override
public boolean isSmaller(TreeExample other) {
    return value < other.getValue();
}

@Override
public boolean isSame(TreeExample other) {
    return value == other.getValue();
}

public String toString(){
    return value+"|"+text;

}

}

Und noch die Main Methode:

public static void main(String[] args) {
    BinarTree tree = new BinarTree();


    Random r = new Random();
    for(int i = 0 ; i < 10000000; i++){
        tree.insert(new TreeExample(r.nextInt(10000000),"A"));  
    }
    System.out.println("---------------------------------- LISTE GEFüllt------------------------------------");
    Random r2 = new Random();
    System.out.println("Anzahl: "+tree.getCount());

     GregorianCalendar now = new GregorianCalendar(); 

    System.err.println(tree.getValue(new TreeExample(r2.nextInt(10000000), "B")));
     GregorianCalendar after = new GregorianCalendar();
     long time = after.getTimeInMillis()-now.getTimeInMillis();
     System.err.println(time);


} 

Das Beispiel füllt die Datenbank mit 10 000 000 Zufälligen Datensätzen vom Type TreeExample und sucht im Anschluss eine Zufällige Zahl. Dabei wird die Zeit gestoppt, die Benötigt wird, um den Datensatz zu finden.

2 Dinge sollten noch optimiert werden.

Der Baum ist immoment unausgeglichen, das heißt manche suchen können längerdauern als Andere. Jedoch habe ich noch keine Suche gehabt die Länger als 2 millisekunden gedauert hat.

Nun ist der Baum noch ein Iterator und kann bei Suchen außerhalb des Index noch normal mit foreach duchsucht werden. (Wie jede andere Liste auch) Auch gibt es nun eine "FastFound" Liste. Diese Steht standartmäßig auf 20 Elementen. Das heißt es werden die Letzten 20 Abfragen die Im Baum vorkamen hier zwischen gespeichert. Das ganze könnte man noch dahin optimieren, das die Top suchen mit einem Ranking versehen werden.

Oh jetzt ist es doch ehere eine LIB als ein Tutorial geworden. Bei Zeiten werde ich es noch verbessern

Zur Info: Ab ca 10000 Werte schauckelt sich die Suche ein. Das heißt : Ob ich 500 Werte in einer Liste mit 10000 oder 100000 elementen Suche, die Dauer bleibt immer gleich. Jedoch ist sie bei 200 möglichen Werten in der FastSuch-Liste wieder langsamer.

— geändert am 15.04.2014, 10:58:16