BinarySearch Tree

02 Mar 2018 • Datenstrukturen • Beiträge

Eine Erweiterung des binären Baumes stellt der Binäre Suchbaum dar. Er dient ähnlich zu der SortedList dazu Werte sortiert abzuspeichern.

BinarySearchTree Quelle: Wikipedia

Im obigen Bild ist ein solcher BinarySearch Tree abgebildet. Dabei ist zu erkennen, dass für jeden Teilbaum die Werte, die kleiner als der Inhalt sind, im linken Teilbaum sind, und alle Werte, die größer sind, im rechten Teilbaum zu finden sind. Da das für jeden Teilbaum gilt, ist es natürlich relativ einfach in diesem Baum einen speziellen Wert zu finden. Es darf jedoch nicht ein Wert doppelt im Binären Baum vorhanden sein!

Methoden

Die Klasse BinarySearch Tree wird drei wichtige Methoden haben. Im folgenden sollen diese näher erläutert werden.

Um zu überprüfen, ob ein Element in einem Baum enthalten ist, wird die Methode search aufgerufen. Sollte das gesuchte Element im Baum vorhanden sein, so wird es zurückgegeben.

func search(g):
    WENN Element = Inhalt:
        GIB Inhalt zurück
    WENN Element < Inhalt:
        GIB search() für linken Teilbaum zurück
    WENN Element > Inhalt:
        GIB search() für rechten Teilbaum zurück

Bei der search() Methode kommt die rekursive Struktur des Baumes zum Nutzen.

public ContentType search(ContentType pContent) {
    if (pContent != null && !isEmpty()) {
        if (content != null && content.isEqual(pContent)){ 
            return content;
        } else {

            if (leftTree != null && pContent.isLess(content)){
                return leftTree.search(pContent);
            }


            if (rightTree != null && pContent.isGreater(content)){
                return rightTree.search(pContent);
            }

        }
    }

    return null;
}

insert()

Da nicht mehr die Methode setContent() benutzt werden kann, weil sie die Werte nicht sortiert einfügt, wird dafür die neue Methode insert() benutzt.

func insert(Element):
    WENN Baum ist leer:
        FÜGE Element ein
        ERZEUGE linken und rechten Teilbaum
    WENN Element > Inhalt:
        RUFE insert() für rechten Teilbaum auf
    WENN Element < Inhalt:
        RUFE insert() für linken Teilbaum auf.

public void insert(ContentType pContent) {
    if (pContent != null) {
        if (isEmpty()) {
            content = pContent;
            leftTree = new BinarySearchTree<>();
            rightTree = new BinarySearchTree<>();

        } else if (content.isGreater(pContent)) {
            leftTree.insert(pContent);
        } else if (content.isLess(pContent)) {
            rightTree.insert(pContent);
        }
    }
}

remove()

func remove(Element)
    WENN Element = Inhalt:
        WENN Baum ist Blatt:
            LÖSCHE Element und Teilbäume
        SONST:
            Inhalt = größtes Element aus linken Baum

    SONST WENN Element > Inahlt:
        RUFE remove() für rechten Teilbaum auf
    SONST WENN Element < Inhalt:
        RUFE remove() für linken Teilbaum auf

Durch dieses Vorgehen werden folgende Fälle abgedeckt:

  1. Element ist nicht im Baum enthalten, oder der Baum ist leer
  2. Element gefunden und ist Blatt
  3. Element gefunden und mit linken und rechten Teilbaum

Sollte das zu entfernende Element mindestens einen Teilbaum haben, so reicht es nicht, dass man den content auf null setzt, sondern es muss ein anderes Element an die Stelle des zu entfernenden kommen. Deshalb entfernt man das größte Element aus dem linken Teilbaum und fügt es an die Stelle des entfernten Elementes ein.

public void remove(ContentType pContent) {
    if (pContent != null && !isEmpty()) {
        if (this.content.isEqual(pContent)) {

            if (isLeaf()) {
                content = null;
                leftTree = null;
                rightTree = null;
            } else {
                content = leftTree.getAndRemoveBiggest();
            }

        } else if (this.content.isGreater(pContent)) {
            leftTree.remove(pContent);
        } else if (this.content.isLess(pContent)) {
            rightTree.remove(pContent);
        }
    }
}

Die Methoden isLeaf() tested, ob der Baum einen linken und rechten Teilbaum besitzt.

private boolean isLeaf() {
    return leftTree.isEmpty() && rightTree.isEmpty();
}

getAndRemoveBiggest() sucht in einem Baum das Element, welches am größte ist und gibt dieses anschließend zurück.

private ContentType getAndRemoveBiggest() {
    if (isEmpty()) return null;
    if (isLeaf()) {
        ContentType solution = content;
        content = null;
        leftTree = null;
        rightTree = null;

        return solution;
    }

    if (!rightTree.isEmpty()) {
        return rightTree.getAndRemoveBiggest();
    } else if (!leftTree.isEmpty()) {
        return leftTree.getAndRemoveBiggest();
    }

    return null;
}

Architektur

Damit man beliebige Datentypen in den Baum einfügen kann, wird wieder ein generischer Datentyp verwendet, der zusätzlich ein Interface implementieren muss.

Das Interface bestimmt die Methoden, die vorhanden sein müssen.

public interface ComparableContent<ContentType> {
    public boolean isGreater(ContentType pComparableContent);
    public boolean isEqual(ContentType pComparableContent);
    public boolean isLess(ContentType pComparableContent);
}

Die Klasse Item implementiert das Interface und beschreibt die Inhaltsobjekte des Baumes.

public class Item implements ComparableContent<Item> {

    private int wert;

    public Item(int pWert){
        wert = pWert;
    }

    public boolean isLess(Item pContent) {
        return this.getWert() < pContent.getWert();
    }

    public boolean isEqual(Item pContent) {
        return this.getWert() == pContent.getWert();
    }

    public boolean isGreater(Item pContent) {
        return this.getWert() > pContent.getWert();
    }

    public int getWert() {
        return wert;
    }
}

Auch im Baum muss angegeben werden, dass das Inahltsobjekt das Interface implementiert sein muss.

public class BinarySearchTree<ContentType extends ComparableContent<ContentType>>

Related Posts