Datenstrukturen: Binärbaum in Java

Hallo Hallo! Ohne Grundkenntnisse ist es schwierig, ein guter Programmierer zu sein. Und damit meinen wir nicht nur Kenntnisse der Syntax der nativen Programmiersprache, sondern auch die Grundlagen und Konzepte der Programmierung im Allgemeinen. Eine dieser Grundlagen sind Algorithmen und Datenstrukturen. In der Regel kennen sich einige in diesem Thema besser aus, andere weniger, aber es gibt einige grundlegende Informationen, die jeder kennen sollte. Unter den Datenbanken für Datenstrukturen lohnt es sich auf jeden Fall, binäre Suchbäume zu verstehen. Eigentlich werden wir uns heute die Struktur selbst mit ihren Funktionen ansehen und herausfinden, wie Sie einen Binärbaum in Java implementieren können . Lassen Sie uns zunächst herausfinden, was ein Binärbaum ist. Ein Binärbaum ist eine Datenstruktur, in der jeder Knoten (Elternknoten) höchstens zwei Kinder (rechter und linker Erbe) hat. In der Praxis werden üblicherweise zwei Arten von Binärbäumen verwendet: binärer Suchbaum und Pyramide (Heap). Heute schauen wir uns einen binären Suchbaum an.

Vorteile des Binärbaums

Welchen Vorteil bietet die Speicherung von Daten als binärer Suchbaum? Stellen Sie sich vor, wir haben ein 100-seitiges Nachschlagewerk und müssen eine bestimmte Seite finden, die die benötigten Daten enthält. Wir wissen auch anhand des Inhalts, welche konkrete Seite wir benötigen. Wenn wir dem üblichen Weg folgen, müssen wir eine Seite nach der anderen umblättern, bis wir zu der Seite gelangen, die wir brauchen. Das heißt, wir gehen 1 bis 100 Seiten durch, bis wir am richtigen Ort sind. Wenn wir beispielsweise Seite 77 benötigen, haben wir 77 Suchanfragen. Wenn wir über Zeitkomplexität sprechen, dann ist es O(N) . Aber das geht doch effizienter, oder? Versuchen wir, dasselbe zu tun, aber mit der binären Suche :

1. Wir teilen das Verzeichnis in zwei Teile, den ersten - von 1 bis 50, den zweiten - 51-100. Wir wissen genau, in welchem ​​dieser Teile sich unsere Seite befindet: Wenn wir noch einmal Seite 77 nehmen, ist sie im zweiten Teil des Buches.
2. Als nächstes betrachten wir den zweiten Teil und teilen ihn in zwei Teile – von 51 bis 75, von 76 bis 100. In diesem Fall befindet sich unsere Seite wieder in der zweiten Hälfte, im Bereich von 76 bis 100.
3. Als nächstes teilen wir dieses Intervall durch 2 und erhalten 76-88 und 89-100. Die Seite passt in die erste Lücke, also verwerfen wir die zweite.
4. Als nächstes folgen die Intervalle: 76-81 und 82-88, nehmen Sie das erste.
5. 76-78 und 79-81, nimm den ersten.
6. 76 und 77-78, nimm den zweiten.
7. 77 und 78, nehmen Sie die erste und erhalten Sie unsere Seite - 77.

Statt 77 Schritten brauchten wir nur 7! Die zeitliche Komplexität dieser Suche beträgt O(log(N)) .

Regeln zum Aufbau eines binären Suchbaums

Der binäre Suchbaum wird nach bestimmten Regeln aufgebaut:

• jeder Knoten hat höchstens zwei Kinder;
• Jeder Wert, der kleiner als der Wert des Knotens ist, wird zum linken Kind oder zum Kind des linken Kindes.
• Jeder Wert, der größer oder gleich dem Wert des Knotens ist, wird zum richtigen Kind oder zum Kind des richtigen Kindes.

Wir haben zum Beispiel eine Zahlenreihe von 1 bis 10. Mal sehen, wie der binäre Suchbaum für diese Reihe aussehen wird: Überlegen wir, ob hier alle Bedingungen eines Binärbaums erfüllt sind:

• alle Knoten haben nicht mehr als zwei Erben, die erste Bedingung ist erfüllt;
• Wenn wir beispielsweise einen Knoten mit dem Wert 7 (oder einem anderen) betrachten, werden wir sehen, dass alle Werte der Elemente im linken Teilbaum kleiner und im rechten Teilbaum größer sind. Dies bedeutet, dass die Bedingungen 2 und 3 erfüllt sind.

Schauen wir uns an, wie die Grundoperationen ablaufen – Einfügen, Löschen, Suchen.

Suchen Sie nach einem Element

Bei der Suche nach einem Element mit einem bestimmten Wert beginnen wir beim Wurzelelement:

1. Wenn es gleich dem gesuchten Wert ist, ist das Wurzelelement das gesuchte; wenn nicht, vergleichen wir die Werte der Wurzel und des gesuchten.
2. Wenn das gesuchte Element größer ist, wechseln wir zum rechten Kind; wenn nicht, gehen wir zum linken Kind.
3. Wenn das Element nicht gefunden wird, wenden Sie die Schritte 1 und 2 an, jedoch auf das untergeordnete Element (rechts oder links), bis das Element gefunden wird.

Im oben gezeigten binären Suchbaum möchten wir beispielsweise das Element mit dem Wert 5 finden:

• Wir vergleichen es mit dem Wurzelelement. Wir sehen, dass das Wurzelelement größer ist, also wechseln wir zum linken untergeordneten Element, das einen Wert von 3 hat.
• Wir vergleichen das gesuchte Element mit dem Element mit dem Wert 3. Wir sehen, dass das gesuchte Element größer ist. Wir benötigen also den rechten Nachkommen des betreffenden Elements, nämlich das Element mit dem Wert 5.
• Wir vergleichen diesen Nachkommen mit dem gesuchten und stellen fest, dass die Werte gleich sind – das Element ist gefunden.

Einfügen eines Elements

Auch der Einfügealgorithmus ist sehr, sehr einfach:

1. Wir vergleichen das neue mit dem Wurzelelement (wenn es nicht existiert, ist das neue Element das Wurzelelement).

2. Wenn ein neues Element:

   • ist kleiner, dann gehen wir zum linken Erben; wenn es keinen gibt, nimmt das neue Element den Platz des linken Erben ein und der Algorithmus ist abgeschlossen;
   • größer oder gleich der Wurzel ist, dann bewegen wir uns zum rechten Erben. Und wenn dieses Element nicht existiert, ersetzt ein neues Element das richtige Element und der Algorithmus ist abgeschlossen.

3. Wiederholen Sie für das betreffende neue Element, das im vorherigen Schritt rechts oder links war, die Schritte 1 und 2, bis das eingefügte Element an Ort und Stelle ist.

   Als Beispiel wollen wir in den oben betrachteten Baum ein Element mit dem Wert 11 einfügen:

   • wir vergleichen mit dem Wurzelelement 7 und stellen fest, dass das Wurzelelement kleiner ist, also gehen wir zum rechten Erben über;
   • Das nächste betrachtete Element hat einen Wert von 9, was kleiner als der neue 11 ist, also gehen wir zum rechten Erben über;
   • Der rechte Erbe hat einen Wert von 10, was wiederum weniger ist, also gehen wir zum ersten Element, und da es dort nicht vorhanden ist, wird an dieser Stelle ein neues Element mit einem Wert von 11 platziert.
   ↓

Ein Element entfernen

Von allen Operationen mit binären Suchbäumen ist das Löschen vielleicht die schwierigste. Zunächst erfolgt die Suche nach dem zu löschenden Element, anschließend folgt ein Schritt, der drei Varianten haben kann:

1. Der zu löschende Knoten ist ein Blattknoten (hat keine untergeordneten Knoten).

   Vielleicht das einfachste. Es kommt darauf an, dass wir es einfach und ohne unnötige Manipulation vom Baum abschneiden. Aus unserem Baum entfernen wir beispielsweise den Knoten mit dem Wert 8:

   ↓

2. Der gelöschte Knoten hat ein untergeordnetes Element.

   In diesem Fall löschen wir den ausgewählten Knoten und setzen seinen Nachkommen an seine Stelle (im Wesentlichen schneiden wir den ausgewählten Knoten einfach aus der Kette). Als Beispiel entfernen wir einen Knoten mit dem Wert 9 aus dem Baum:

   ↓

3. Der zu löschende Knoten hat zwei untergeordnete Knoten.

   Der interessanteste Teil. Denn wenn der zu löschende Knoten zwei Kinder gleichzeitig hat, können Sie ihn nicht einfach durch eines dieser Kinder ersetzen (insbesondere, wenn das Kind seine eigenen Kinder hat).

   Beispiel: Welcher Knoten im obigen Baum sollte das linke untergeordnete Element von Knoten 3 sein?

   Wenn man ein wenig darüber nachdenkt, wird klar, dass dies ein Knoten mit einem Wert von 4 sein sollte. Was aber, wenn der Baum nicht so einfach ist? Wenn es Hunderte von Werten enthält, wird es dann so einfach sein, herauszufinden, wer der Nachfolger sein wird?

   Es ist klar, dass nein. Daher benötigen wir unseren eigenen Suchalgorithmus für kleine Empfänger:

   1. Zuerst müssen wir zum rechten Kind des ausgewählten Knotens gehen, dessen Wert größer als der Wert des Knotens sein muss.
   2. Dann gehen wir zum linken Kind des rechten Kindes (sofern vorhanden), dann zum linken Kind des linken Kindes usw. und folgen der Kette der linken Kinder nach unten.
   3. Dementsprechend ist das letzte verbleibende Kind auf diesem Pfad der Nachfolger des ursprünglichen Knotens.

   Lassen Sie uns diesen kleinen Algorithmus ein wenig verallgemeinern: Im Unterbaum des rechten untergeordneten Knotens des Quellknotens sind alle Knoten größer als der zu löschende, was aus den Grundregeln des binären Suchbaums verstanden werden kann. In diesem Teilbaum suchen wir nach dem kleinsten Wert.

   Mit anderen Worten: Wir suchen nach dem kleinsten Knoten in einer Menge von Knoten, die größer als der ursprüngliche Knoten sind. Dieser kleinste Knoten unter den größeren wird der am besten geeignete Nachfolger sein.

   So sieht der Baum aus, nachdem der Knoten mit dem Wert 3 entfernt wurde:

   ↓

Jetzt ist es an der Zeit, von der Praxis zur Theorie überzugehen. Schauen wir uns an, wie wir diese Datenstruktur in Java abbilden können. Einzelknotenklasse:

class Node {
   private int value; // ключ узла
   private Node leftChild; // Левый узел потомок
   private Node rightChild; // Правый узел потомок

   public void printNode() { // Вывод значения узла в консоль
       System.out.println(" Выбранный узел имеет Bedeutung :" + value);
   }

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

   public void setValue(final int value) {
       this.value = value;
   }

   public Node getLeftChild() {
       return this.leftChild;
   }

   public void setLeftChild(final Node leftChild) {
       this.leftChild = leftChild;
   }

   public Node getRightChild() {
       return this.rightChild;
   }

   public void setRightChild(final Node rightChild) {
       this.rightChild = rightChild;
   }

   @Override
   public String toString() {
       return "Node{" +
               "value=" + value +
               ", leftChild=" + leftChild +
               ", rightChild=" + rightChild +
               '}';
   }
}

Nichts allzu Kompliziertes: Jedes Element hat einen Link zu seinem linken und rechten untergeordneten Element. Und jetzt ist vielleicht die Baumklasse die wichtigste Klasse:

class Tree {
   private Node rootNode; // корневой узел

   public Tree() { // Пустое дерево
       rootNode = null;
   }

   public Node findNodeByValue(int value) { // поиск узла по значению
       Node currentNode = rootNode; // начинаем поиск с корневого узла
       while (currentNode.getValue() != value) { // поиск покуда не будет найден элемент oder не будут перебраны все
           if (value < currentNode.getValue()) { // движение влево?
               currentNode = currentNode.getLeftChild();
           } else { //движение вправо
               currentNode = currentNode.getRightChild();
           }
           if (currentNode == null) { // если потомка нет,
               return null; // возвращаем null
           }
       }
       return currentNode; // возвращаем найденный элемент
   }

   public void insertNode(int value) { // метод вставки нового Element
       Node newNode = new Node(); // создание нового узла
       newNode.setValue(value); // вставка данных
       if (rootNode == null) { // если корневой узел не существует
           rootNode = newNode;// то новый элемент и есть корневой узел
       }
       else { // корневой узел занят
           Node currentNode = rootNode; // начинаем с корневого узла
           Node parentNode;
           while (true) // мы имеем внутренний выход из цикла
           {
               parentNode = currentNode;
               if(value == currentNode.getValue()) {   // если такой элемент в дереве уже есть, не сохраняем его
                    return;    // просто выходим из метода
                }
                else  if (value < currentNode.getValue()) {   // движение влево?
                   currentNode = currentNode.getLeftChild();
                   if (currentNode == null){ // если был достигнут конец цепочки,
                       parentNode.setLeftChild(newNode); //  то вставить слева и выйти из методы
                       return;
                   }
               }
               else { // Или направо?
                   currentNode = currentNode.getRightChild();
                   if (currentNode == null) { // если был достигнут конец цепочки,
                       parentNode.setRightChild(newNode);  //то вставить справа
                       return; // и выйти
                   }
               }
           }
       }
   }

   public boolean deleteNode(int value) // Удаление узла с заданным ключом
   {
       Node currentNode = rootNode;
       Node parentNode = rootNode;
       boolean isLeftChild = true;
       while (currentNode.getValue() != value) { // начинаем поиск узла
           parentNode = currentNode;
           if (value < currentNode.getValue()) { // Определяем, нужно ли движение влево?
               isLeftChild = true;
               currentNode = currentNode.getLeftChild();
           }
           else { // oder движение вправо?
               isLeftChild = false;
               currentNode = currentNode.getRightChild();
           }
           if (currentNode == null)
               return false; // yзел не найден
       }

       if (currentNode.getLeftChild() == null && currentNode.getRightChild() == null) { // узел просто удаляется, если не имеет потомков
           if (currentNode == rootNode) // если узел - корень, то дерево очищается
               rootNode = null;
           else if (isLeftChild)
               parentNode.setLeftChild(null); // если нет - узел отсоединяется, от родителя
           else
               parentNode.setRightChild(null);
       }
       else if (currentNode.getRightChild() == null) { // узел заменяется левым поддеревом, если правого потомка нет
           if (currentNode == rootNode)
               rootNode = currentNode.getLeftChild();
           else if (isLeftChild)
               parentNode.setLeftChild(currentNode.getLeftChild());
           else
               parentNode.setRightChild(currentNode.getLeftChild());
       }
       else if (currentNode.getLeftChild() == null) { // узел заменяется правым поддеревом, если левого потомка нет
           if (currentNode == rootNode)
               rootNode = currentNode.getRightChild();
           else if (isLeftChild)
               parentNode.setLeftChild(currentNode.getRightChild());
           else
               parentNode.setRightChild(currentNode.getRightChild());
       }
       else { // если есть два потомка, узел заменяется преемником
           Node heir = receiveHeir(currentNode);// поиск преемника для удаляемого узла
           if (currentNode == rootNode)
               rootNode = heir;
           else if (isLeftChild)
               parentNode.setLeftChild(heir);
           else
               parentNode.setRightChild(heir);
       }
       return true; // элемент успешно удалён
   }

   // метод возвращает узел со следующим Bedeutungм после передаваемого аргументом.
   // для этого он сначала переходим к правому потомку, а затем
   // отслеживаем цепочку левых потомков этого узла.
   private Node receiveHeir(Node node) {
       Node parentNode = node;
       Node heirNode = node;
       Node currentNode = node.getRightChild(); // Переход к правому потомку
       while (currentNode != null) // Пока остаются левые потомки
       {
           parentNode = heirNode;// потомка задаём Wie текущий узел
           heirNode = currentNode;
           currentNode = currentNode.getLeftChild(); // переход к левому потомку
       }
       // Если преемник не является
       if (heirNode != node.getRightChild()) // правым потомком,
       { // создать связи между узлами
           parentNode.setLeftChild(heirNode.getRightChild());
           heirNode.setRightChild(node.getRightChild());
       }
       return heirNode;// возвращаем приемника
   }

   public void printTree() { // метод для вывода дерева в консоль
       Stack globalStack = new Stack(); // общий стек для значений дерева
       globalStack.push(rootNode);
       int gaps = 32; // начальное Bedeutung расстояния между Elementми
       boolean isRowEmpty = false;
       String separator = "-----------------------------------------------------------------";
       System.out.println(separator);// черта для указания начала нового дерева
       while (isRowEmpty == false) {
           Stack localStack = new Stack(); // локальный стек для задания потомков Element
           isRowEmpty = true;

           for (int j = 0; j < gaps; j++)
               System.out.print(' ');
           while (globalStack.isEmpty() == false) { // покуда в общем стеке есть элементы
               Node temp = (Node) globalStack.pop(); // берем следующий, при этом удаляя его из стека
               if (temp != null) {
                   System.out.print(temp.getValue()); // выводим его Bedeutung в консоли
                   localStack.push(temp.getLeftChild()); // соохраняем в локальный стек, наследники текущего Element
                   localStack.push(temp.getRightChild());
                   if (temp.getLeftChild() != null ||
                           temp.getRightChild() != null)
                       isRowEmpty = false;
               }
               else {
                   System.out.print("__");// - если элемент пустой
                   localStack.push(null);
                   localStack.push(null);
               }
               for (int j = 0; j < gaps * 2 - 2; j++)
                   System.out.print(' ');
           }
           System.out.println();
           gaps /= 2;// при переходе на следующий уровень расстояние между Elementми каждый раз уменьшается
           while (localStack.isEmpty() == false)
               globalStack.push(localStack.pop()); // перемещаем все элементы из локального стека в глобальный
       }
       System.out.println(separator);// подводим черту
   }
}

Auch hier ist nichts zu kompliziert. Es sind die zuvor beschriebenen binären Suchbaumoperationen sowie eine Methode zum Anzeigen des Baums in der Konsole vorhanden. Schauen wir uns nun den Baum in Aktion an:

public class Application {
   public static void main(String[] args) {
       Tree tree = new Tree();
       // вставляем узлы в дерево:
       tree.insertNode(6);
       tree.insertNode(8);
       tree.insertNode(5);
       tree.insertNode(8);
       tree.insertNode(2);
       tree.insertNode(9);
       tree.insertNode(7);
       tree.insertNode(4);
       tree.insertNode(10);
       tree.insertNode(3);
       tree.insertNode(1);
       // отображение дерева:
       tree.printTree();

       // удаляем один узел и выводим оставшееся дерево в консоли
       tree.deleteNode(5);
       tree.printTree();

       // находим узел по значению и выводим его в консоли
       Node foundNode = tree.findNodeByValue(7);
       foundNode.printNode();
   }
}

Such-/Einfüge-/Löschvorgänge in einem binären Suchbaum haben eine zeitliche Komplexität von O(log(N)) . Aber das ist das beste Szenario. Im Allgemeinen reicht die zeitliche Komplexität von Operationen von O(log(N)) bis O(N) . Dies hängt vom Grad der Degeneration des Baumes ab.

Was ist ein entarteter Baum?

Dies ist der Baum, in dem die Elemente abgelegt werden, wenn sie an der Position des äußersten linken Knotens (kleinste Zahl) oder des größten Knotens (größte) hinzugefügt werden. Dies kann beispielsweise passieren, wenn der gesamte linke Baum auf jeder Ebene leer ist und es nur rechte Bäume gibt. In diesem Fall degeneriert der Baum zu einer Liste (nach rechts gehend). Ja, auf diese Weise wird ein degenerierter Baum effektiv zu einer einfach verknüpften Liste, in der jedes Element nur das daneben liegende Element kennt. In diesem Fall nähern sich alle Operationen an dieser Struktur der Zeitkomplexität von O(N) an .

In welchem ​​Fall kann ein Baum degenerieren?

Wenn Sie beispielsweise eine Liste sortierter Elemente hinzufügen. Wenn die Liste aufsteigend sortiert ist, ist die Wurzel die erste bzw. die kleinste. Der nächste nach ihm wird die Position des richtigen Kindes einnehmen. Und das darauffolgende wird größer als das zweite sein und die Position seines rechten Nachfolgers einnehmen, und so weiter ... Wenn die Liste in absteigender Reihenfolge vorliegt, passiert dasselbe, jedoch mit den Elementen ganz links. Um dies zu vermeiden, können Sie nach Erhalt mehrerer Elemente diese einfach mischen. Dann verschwindet die Sortierung und die Zahlen werden mehr oder weniger gleichmäßig im Baum verteilt. Das ist alles für heute, vielen Dank für Ihre Aufmerksamkeit!