🥇Binary Tree oder wie man einen binären Suchbaum erstellt

Einleitung

Dieser Artikel widmet sich Binärsuchbäumen. Kürzlich habe ich einen Artikel über Datenkompression mit dem Huffman-Verfahren geschrieben. Dabei habe ich nicht viel Aufmerksamkeit auf Binärbäume gelegt, da die Methoden für Suche, Einfügen und Löschen nicht relevant waren. Jetzt habe ich beschlossen, einen Artikel genau über Bäume zu schreiben. Fangen wir an.

Ein Baum ist eine Datenstruktur, die aus Knoten besteht, die durch Kanten verbunden sind. Man kann sagen, dass ein Baum eine spezielle Form eines Graphen ist. Hier ist ein Beispiel für einen Baum:

Das ist kein Binärsuchbaum! Alle Details im weiterhin genannten Text!

Terminologie

Wurzel

Die Wurzel des Baums ist der oberste Knoten. Im Beispiel ist das der Knoten A. Im Baum kann es von der Wurzel zu jedem anderen Knoten nur einen einzigen Pfad geben! Tatsächlich kann jeder Knoten als Wurzel des entsprechenden Teilbaums betrachtet werden.

Eltern/Kinder

Alle Knoten, außer der Wurzel, haben genau eine Kante, die nach oben zu einem anderen Knoten führt. Der Knoten, der sich über dem aktuellen befindet, wird als Elternteil dieses Knotens bezeichnet. Der Knoten, der sich unter dem aktuellen befindet und mit ihm verbunden ist, wird als Kind dieser Knoten. Lassen Sie uns ein Beispiel nehmen. Nehmen wir Knoten B, dann wird sein Elternteil Knoten A sein, und die Nachkommen sind die Knoten D, E und F.

Blatt

Ein Knoten, der keine Nachkommen hat, wird als Blatt des Baumes bezeichnet. In diesem Beispiel sind die Blätter die Knoten D, E, F, G, I, J, K.

Das ist die grundlegende Terminologie. Weitere Konzepte werden später behandelt. Ein binärer Baum ist ein Baum, in dem jeder Knoten nicht mehr als zwei Nachkommen hat. Wie Sie sich denken können, ist der Baum aus dem Beispiel kein binärer Baum, da die Knoten B und H mehr als zwei Nachkommen haben. Hier ist ein Beispiel für einen binären Baum:

In den Knoten des Baumes kann jede Art von Informationen gespeichert werden. Ein binärer Suchbaum ist ein binärer Baum, der folgende Eigenschaften hat:

Beide Teilbäume – der linke und der rechte – sind binäre Suchbäume.
Für alle Knoten des linken Teilbaums eines beliebigen Knotens X sind die Werte der Schlüsseldaten kleiner als der Wert des Schlüssels selbst von Knoten X.
Für alle Knoten des rechten Teilbaums eines beliebigen Knotens X sind die Werte der Schlüsseldaten größer oder gleich dem Wert des Schlüssels selbst von Knoten X.

Der Schlüssel — eine Eigenschaft des Knotens (zum Beispiel eine Zahl). Der Schlüssel wird benötigt, um das entsprechende Element des Baumes zu finden. Beispiel eines binären Suchbaums:

Darstellung des Baumes

Im Verlauf werde ich einige (möglicherweise unvollständige) Code-Schnipsel anführen, um Ihr Verständnis zu verbessern. Den vollständigen Code finden Sie am Ende des Artikels.

Ein Baum besteht aus Knoten. Die Struktur eines Knotens:

public class Node<T> {
    private T data;
    private int key;
    private Node<T> leftChild;
    private Node<T> rightChild;

    public Node(T data, int key) {
        this.data = data;
        this.key = key;
    }
    public Node<T> getLeftChild() {
        return leftChild;
    }

    public Node<T> getRightChild() {
        return rightChild;
    }
//...weitere Methoden des Knotens
}

Jeder Knoten hat zwei Nachkommen (es ist durchaus möglich, dass die Nachkommen leftChild und/oder rightChild den Wert null enthalten). Sie haben wahrscheinlich verstanden, dass in diesem Fall die Zahl data — die Daten sind, die im Knoten gespeichert sind; key — der Schlüssel des Knotens.

Jetzt, wo wir den Knoten behandelt haben, sprechen wir über aktuelle Probleme im Zusammenhang mit Bäumen. Hier und im Folgenden beziehe ich mich auf den Begriff des binären Suchbaums. Die Struktur eines binären Baums:

public class BinaryTree<T> {
     private Node<T> root;

    // Methoden des Baumes
}

Als Klassenfeld benötigen wir nur die Wurzel des Baumes, da wir über die Methoden getLeftChild() und getRightChild() von der Wurzel zu jedem Knoten im Baum gelangen können.

Algorithmen im Baum

Поиск

Angenommen, Sie haben einen aufgebauten Baum. Wie finden Sie das Element mit dem Schlüssel key? Sie müssen sich schrittweise von der Wurzel nach unten bewegen und den Wert key mit dem Schlüssel des aktuellen Knotens vergleichen: Ist key kleiner als der Schlüssel des aktuellen Knotens, wechseln Sie zum linken Kind dieses Knotens; ist er größer, zum rechten; wenn die Schlüssel gleich sind, wurde der gesuchte Knoten gefunden! Der entsprechende Code lautet:

public Node<T> find(int key) {
    Node<T> current = root;
    while (current.getKey() != key) {
        if (key < current.getKey())
            current = current.getLeftChild();
        else
            current = current.getRightChild();
        if (current == null)
            return null;
    }
    return current;
}

Wenn current null wird, bedeutet das, dass die Durchsuchung das Ende des Baumes erreicht hat (auf konzeptioneller Ebene befinden Sie sich an einem nicht existierenden Ort im Baum – einem Nachkommen des Blattes).

Betrachten wir die Effizienz des Suchalgorithmus in einem balancierten Baum (einem Baum, in dem die Knoten mehr oder weniger gleichmäßig verteilt sind). Die Sucheffizienz beträgt dann O(log(n)), wobei der Logarithmus zur Basis 2 verwendet wird. Sehen Sie: Wenn ein balancierter Baum n Elemente hat, bedeutet das, dass es log(n) Ebenen im Baum gibt, die zur Basis 2 berechnet werden. Bei der Suche steigen Sie in jedem Schritt der Schleife eine Ebene hinunter.

Einfügen

Wenn Sie das Prinzip der Suche verstanden haben, wird es Ihnen leichtfallen, das Einfügen zu verstehen. Sie müssen einfach zum Blatt des Baumes hinuntersteigen (den Regeln des Abstiegs folgen, die in der Suche beschrieben sind) und dort Nachkommen werden – entweder links oder rechts, je nach Schlüssel. Implementierung:

   public void insert(T insertData, int key) {
        Node current = root;
        Node parent;
        Node newNode = new Node(insertData, key);
        if (root == null)
            root = newNode;
        else {
            while (true) {
                parent = current;
                if (key < current.getKey()) {
                    current = current.getLeftChild();
                    if (current == null) {
                         parent.setLeftChild(newNode);
                         return;
                    }
                }
                else {
                    current = current.getRightChild();
                    if (current == null) {
                        parent.setRightChild(newNode);
                        return;
                    }
                }
            }
        }
    }

In diesem Fall müssen wir neben dem aktuellen Knoten auch Informationen über den Elternknoten speichern. Wenn 'current' null ist, wird die benötigte Liste in der Variablen 'parent' gespeichert.
Die Effizienz der Einfügung wird offensichtlich die gleiche sein wie die Suche — O(log(n)).

Entfernen

Das Löschen ist die komplizierteste Operation, die wir mit dem Baum durchführen müssen. Zunächst müssen wir das Element finden, das wir löschen möchten. Aber was kommt danach? Wenn wir seiner Referenz einfach den Wert null zuweisen, verlieren wir die Informationen über den Teilbaum, dessen Wurzel dieser Knoten ist. Die Methoden zum Löschen in einem Baum werden in drei Fälle unterteilt.

Erster Fall. Der zu löschende Knoten hat keine Nachfolger.

Wenn der zu löschende Knoten keine Nachfolger hat, bedeutet das, dass er ein Blatt ist. Folglich können wir einfach den Feldern 'leftChild' oder 'rightChild' seines Elternteils den Wert null zuweisen.

Zweiter Fall. Der zu löschende Knoten hat einen Nachfolger.

Dieser Fall ist ebenfalls nicht sehr kompliziert. Lassen Sie uns zu unserem Beispiel zurückkehren. Angenommen, wir müssen das Element mit dem Schlüssel 14 entfernen. Sie stimmen zu, dass es, da es das rechte Kind des Knotens mit dem Schlüssel 10 ist, jedes seiner Nachkommen (in diesem Fall das rechte) einen Schlüssel haben wird, der größer als 10 ist. Daher können wir es leicht aus dem Baum «herausnehmen» und den Elternknoten direkt mit dem Nachkommen des zu löschenden Knotens verbinden, d. h. den Knoten mit dem Schlüssel 10 mit dem Knoten 13 verbinden. Eine ähnliche Situation würde auftreten, wenn wir einen Knoten löschen müssten, der das linke Kind seines Elternteils ist. Denken Sie selbst darüber nach — die genaue Analogie.

Der dritte Fall. Der Knoten hat zwei Nachkommen

Der komplizierteste Fall. Lassen Sie uns ein neues Beispiel durchgehen.

Nachfolger suchen

Angenommen, wir müssen den Knoten mit dem Schlüssel 25 entfernen. Wen setzen wir an seine Stelle? Jemand aus seinen Nachkommen (Nachkommen oder Nachkommen von Nachkommen) muss Nachfolger(die Person, die den Platz des zu löschenden Knotens einnimmt).

Wie ermitteln Sie den Nachfolger? Es ist intuitiv klar, dass dies der Knoten im Baum ist, dessen Schlüssel der nächstgrößere vom zu entfernenden Knoten ist. Der Algorithmus sieht wie folgt aus: Sie müssen zu seinem rechten Nachkommen gehen (immer zum rechten, denn, wie bereits erwähnt, ist der Schlüssel des Nachfolgers größer als der des zu entfernenden Knotens) und dann die Kette der linken Nachkommen dieses rechten Nachkommen durchlaufen. Im Beispiel müssen wir zum Knoten mit dem Schlüssel 35 gehen und dann nach unten die Kette seiner linken Nachkommen bis zum Blatt durchlaufen — in diesem Fall besteht diese Kette nur aus dem Knoten mit dem Schlüssel 30. Streng genommen suchen wir das kleinste Element in der Menge der Knoten, die größer als der gesuchte Knoten sind.

Code zur Methode der Nachfolgersuche:

    public Node getSuccessor(Node deleteNode) {
        Node parentSuccessor = deleteNode; // Elternteil des Nachfolgers
        Node successor = deleteNode; // Nachfolger
        Node current = successor.getRightChild(); // einfach "laufender" Knoten
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }
        // beim Verlassen der Schleife haben wir den Nachfolger und den Elternteil des Nachfolgers
        if (successor != deleteNode.getRightChild()) { // wenn der Nachfolger nicht mit dem rechten Kind des zu löschenden Knotens übereinstimmt
            parentSuccessor.setLeftChild(successor.getRightChild()); // dann übernimmt der Elternteil den Nachfolger, um dessen Kind nicht zu verlieren
            successor.setRightChild(deleteNode.getRightChild()); // verbinden den Nachfolger mit dem rechten Kind des zu löschenden Knotens
        }
        return successor;
    }

Der vollständige Code der Methode delete:

public boolean delete(int deleteKey) {
        Node current = root;
        Node parent = current;
        boolean isLeftChild = false; // Je nach dem, ob der zu löschende Knoten ein linkes oder rechtes Kind seines Elternteils ist, wird die boolesche Variable isLeftChild entsprechend true oder false sein.
        while (current.getKey() != deleteKey) {
            parent = current;
            if (deleteKey < current.getKey()) {
                current = current.getLeftChild();
                isLeftChild = true;
            } else {
                isLeftChild = false;
                current = current.getRightChild();
            }
            if (current == null)
                return false;
        }

        if (current.getLeftChild() == null && current.getRightChild() == null) { // erster Fall
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        }
        else if (current.getRightChild() == null) { // zweiter Fall
            if (current == root)
                root = current.getLeftChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getLeftChild());
            else
                current.setRightChild(current.getLeftChild());
        } else if (current.getLeftChild() == null) {
            if (current == root)
                root = current.getRightChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getRightChild());
            else
                parent.setRightChild(current.getRightChild());
        } 
        else { // dritter Fall
            Node successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

Die Komplexität kann durch O(log(n)) approximiert werden.

Suche nach dem Maximum/Minimum im Baum

Um den minimalen/maximalen Wert im Baum zu finden, muss man gemäß der Kette der linken/rechten Elemente des Baums nacheinander vorgehen; wenn man ein Blatt erreicht, ist es das minimale/maximale Element.

    public Node<T> getMinimum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getLeftChild();
        }
        return parent;
    }

    public Node<T> getMaximum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getRightChild();
        }
        return parent;
    }

Die Komplexität beträgt O(log(n)).

Symmetrische Traversierung

Traversierung bedeutet, jeden Knoten im Baum zu besuchen, um eine bestimmte Aktion mit ihm durchzuführen.

Algorithmus für die rekursive symmetrische Traversierung:

Aktion mit dem linken Nachkommen durchführen
Aktion mit sich selbst durchführen
Aktion mit dem rechten Nachkommen durchführen

Code:

    public void inOrder(Node<T> current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");//Hier kann alles Mögliche stehen
            inOrder(current.getRightChild());
        }
    }

Fazit

Endlich! Wenn ich etwas nicht klar genug erklärt habe oder Sie Anmerkungen haben, lassen Sie es mich in den Kommentaren wissen. Wie versprochen, hier ist der vollständige Code.

Node.java:

public class Node {
    private T data;
    private int key;
    private Node leftChild;
    private Node rightChild;

    public Node(T data, int key) {
        this.data = data;
        this.key = key;
    }

    public void setLeftChild(Node newNode) {
        leftChild = newNode;
    }

    public void setRightChild(Node newNode) {
        rightChild = newNode;
    }

    public Node getLeftChild() {
        return leftChild;
    }

    public Node getRightChild() {
        return rightChild;
    }

    public T getData() {
        return data;
    }

    public int getKey() {
        return key;
    }
}

BinaryTree.java:

public class BinaryTree {
    private Node root;

    public Node find(int key) {
        Node current = root;
        while (current.getKey() != key) {
            if (key < current.getKey())
                current = current.getLeftChild();
            else
                current = current.getRightChild();
            if (current == null)
                return null;
        }
        return current;
    }

    public void insert(T insertData, int key) {
        Node current = root;
        Node parent;
        Node newNode = new Node(insertData, key);
        if (root == null)
            root = newNode;
        else {
            while (true) {
                parent = current;
                if (key < current.getKey()) {
                    current = current.getLeftChild();
                    if (current == null) {
                         parent.setLeftChild(newNode);
                         return;
                    }
                }
                else {
                    current = current.getRightChild();
                    if (current == null) {
                        parent.setRightChild(newNode);
                        return;
                    }
                }
            }
        }
    }

    public Node getMinimum(Node startPoint) {
        Node current = startPoint;
        Node parent = current;
        while (current != null) {
            parent = current;
            current = current.getLeftChild();
        }
        return parent;
    }

    public Node getMaximum(Node startPoint) {
        Node current = startPoint;
        Node parent = current;
        while (current != null) {
            parent = current;
            current = current.getRightChild();
        }
        return parent;
    }

    public Node getSuccessor(Node deleteNode) {
        Node parentSuccessor = deleteNode;
        Node successor = deleteNode;
        Node current = successor.getRightChild();
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }

        if (successor != deleteNode.getRightChild()) {
            parentSuccessor.setLeftChild(successor.getRightChild());
            successor.setRightChild(deleteNode.getRightChild());
        }
        return successor;
    }

    public boolean delete(int deleteKey) {
        Node current = root;
        Node parent = current;
        boolean isLeftChild = false;
        while (current.getKey() != deleteKey) {
            parent = current;
            if (deleteKey < current.getKey()) {
                current = current.getLeftChild();
                isLeftChild = true;
            } else {
                isLeftChild = false;
                current = current.getRightChild();
            }
            if (current == null)
                return false;
        }

        if (current.getLeftChild() == null && current.getRightChild() == null) {
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        }
        else if (current.getRightChild() == null) {
            if (current == root)
                root = current.getLeftChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getLeftChild());
            else
                current.setRightChild(current.getLeftChild());
        } else if (current.getLeftChild() == null) {
            if (current == root)
                root = current.getRightChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getRightChild());
            else
                parent.setRightChild(current.getRightChild());
        } 
        else {
            Node successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

    public void inOrder(Node current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");
            inOrder(current.getRightChild());
        }
    }
}

P.S.

Degeneration zu O(n)

Viele von Ihnen haben vielleicht bemerkt: Was wäre, wenn wir das Baum unbalanciert machen? Zum Beispiel, indem wir Knoten mit aufsteigenden Schlüsseln einfügen: 1, 2, 3, 4, 5, 6… Dann ähnelt der Baum eher einer verketteten Liste. Ja, der Baum verliert seine baumartige Struktur und damit die Effizienz beim Datenzugriff. Die Komplexität der Such-, Einfüge- und Löschoperationen wird die gleiche wie bei einer verketteten Liste sein: O(n). Das ist einer der wichtigsten Nachteile von binären Bäumen aus meiner Sicht.

Nur registrierte Benutzer können an der Umfrage teilnehmen. Bitte melden Sie sich an.Sind Sie an Contour interessiert?