Vorspiel
In diesem Artikel geht es um binäre Suchbäume. Ich habe kürzlich einen Artikel darüber geschrieben Dort habe ich Binärbäumen nicht wirklich Beachtung geschenkt, da die Methoden Suchen, Einfügen, Löschen nicht relevant waren. Jetzt habe ich beschlossen, einen Artikel über Bäume zu schreiben. Vielleicht fangen wir an.
Ein Baum ist eine Datenstruktur, die aus Knoten besteht, die durch Kanten verbunden sind. Wir können sagen, dass ein Baum ein Sonderfall eines Graphen ist. Hier ist ein Beispielbaum:
Dies ist kein binärer Suchbaum! Alles ist unter dem Strich!
Vocabulary
Wurzel
Baumwurzel ist der oberste Knoten. Im Beispiel ist das Knoten A. Im Baum kann nur ein Pfad von der Wurzel zu jedem anderen Knoten führen! Tatsächlich kann jeder Knoten als Wurzel des diesem Knoten entsprechenden Teilbaums betrachtet werden.
Eltern/Nachkommen
Alle Knoten außer der Wurzel haben genau eine Kante, die zu einem anderen Knoten führt. Der Knoten über dem aktuellen Knoten wird aufgerufen Elternteil Dieser Knoten. Ein Knoten, der unterhalb des aktuellen Knotens liegt und mit diesem verbunden ist, wird aufgerufen Nachfahre Dieser Knoten. Nehmen wir ein Beispiel. Nehmen Sie Knoten B, dann ist sein übergeordneter Knoten Knoten A und seine untergeordneten Knoten sind die Knoten D, E und F.
Blatt
Ein Knoten, der keine Kinder hat, wird als Blatt des Baums bezeichnet. Im Beispiel sind die Knoten D, E, F, G, I, J, K Blätter.
Dies ist die grundlegende Terminologie. Weitere Konzepte werden später besprochen. Ein Binärbaum ist also ein Baum, in dem jeder Knoten nicht mehr als zwei untergeordnete Knoten hat. Wie Sie vermutet haben, wird der Baum aus dem Beispiel nicht binär sein, da die Knoten B und H mehr als zwei untergeordnete Knoten haben. Hier ist ein Beispiel für einen Binärbaum:
Die Knoten des Baums können beliebige Informationen enthalten. Ein binärer Suchbaum ist ein binärer Baum mit den folgenden Eigenschaften:
- Sowohl der linke als auch der rechte Teilbaum sind binäre Suchbäume.
- Alle Knoten des linken Teilbaums eines beliebigen Knotens X haben Datenschlüsselwerte, die kleiner sind als der Datenschlüsselwert des Knotens X selbst.
- Alle Knoten des rechten Teilbaums eines beliebigen Knotens X haben Datenschlüsselwerte, die größer oder gleich dem Wert des Datenschlüssels von Knoten X selbst sind.
Schlüssel - ein Merkmal des Knotens (z. B. eine Zahl). Der Schlüssel wird benötigt, um das Element des Baums finden zu können, dem dieser Schlüssel entspricht. Beispiel für einen binären Suchbaum:
Baumsicht
Im weiteren Verlauf werde ich einige (vielleicht unvollständige) Codeteile einbinden, um Ihr Verständnis zu verbessern. Den vollständigen Code finden Sie am Ende des Artikels.
Der Baum besteht aus Knoten. Knotenstruktur:
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;
}
//...остальные методы узла
}
Jeder Knoten hat zwei untergeordnete Knoten (es ist durchaus möglich, dass die untergeordneten Elemente leftChild und/oder rightChild null sind). Sie haben wahrscheinlich verstanden, dass in diesem Fall die Zahlendaten die im Knoten gespeicherten Daten sind; Schlüssel – Knotenschlüssel.
Wir haben den Knoten herausgefunden, jetzt reden wir über die drängenden Probleme im Zusammenhang mit Bäumen. Im Folgenden bedeutet das Wort „Baum“ das Konzept eines binären Suchbaums. Binärbaumstruktur:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Als Klassenfeld benötigen wir nur die Wurzel des Baums, denn von der Wurzel aus kann man mit den Methoden getLeftChild() und getRightChild() zu jedem Knoten des Baums gelangen.
Baumalgorithmen
Suche
Nehmen wir an, Sie haben einen gebauten Baum. Wie finde ich ein Element mit dem Schlüsselschlüssel? Sie müssen sich nacheinander von der Wurzel im Baum nach unten bewegen und den Wert von key mit dem Schlüssel des nächsten Knotens vergleichen: Wenn key kleiner als der Schlüssel des nächsten Knotens ist, gehen Sie zum linken Nachkommen des Knotens, wenn mehr - nach rechts, wenn die Schlüssel gleich sind, ist der gewünschte Knoten gefunden! Relevanter Code:
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, hat die Iteration das Ende des Baums erreicht (auf konzeptioneller Ebene befinden Sie sich an einer nicht existierenden Stelle im Baum – einem untergeordneten Element eines Blattes).
Betrachten Sie die Effizienz des Suchalgorithmus für einen ausgeglichenen Baum (einen Baum, in dem die Knoten mehr oder weniger gleichmäßig verteilt sind). Dann beträgt die Sucheffizienz O(log(n)) und der Logarithmus zur Basis 2. Siehe: Wenn ein ausgeglichener Baum n Elemente enthält, bedeutet dies, dass es log(n) Ebenen des Baums zur Basis 2 gibt. Und bei der Suche geht man für einen Schritt des Zyklus eine Ebene tiefer.
Einfügen
Wenn Sie den Kern der Suche verstanden haben, wird es Ihnen nicht schwer fallen, die Einfügung zu verstehen. Sie müssen nur zum Blatt des Baums hinuntergehen (gemäß den in der Suche beschriebenen Abstiegsregeln) und dessen Nachkomme werden – links oder rechts, je nach Schlüssel. Implementierung:
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> 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 zusätzlich zum aktuellen Knoten Informationen über den übergeordneten Knoten des aktuellen Knotens gespeichert werden. Wenn current null wird, enthält die übergeordnete Variable das benötigte Blatt.
Die Einfügungseffizienz wird offensichtlich die gleiche sein wie die der Suche – O(log(n)).
Entfernung
Das Löschen ist der komplexeste Vorgang, der mit einem Baum durchgeführt werden muss. Es ist klar, dass es zunächst notwendig sein wird, das Element zu finden, das wir entfernen möchten. Aber was dann? Wenn wir seine Referenz einfach auf Null setzen, verlieren wir Informationen über den Teilbaum, dessen Wurzel dieser Knoten ist. Baumfällungsmethoden werden in drei Fälle unterteilt.
Erster Fall. Der zu entfernende Knoten hat keine untergeordneten Knoten.
Wenn der zu löschende Knoten keine untergeordneten Knoten hat, bedeutet dies, dass es sich um ein Blatt handelt. Daher können Sie einfach die Felder leftChild oder rightChild des übergeordneten Elements auf null setzen.
Zweiter Fall. Der zu entfernende Knoten hat ein Kind
Auch dieser Fall ist nicht sehr schwierig. Kehren wir zu unserem Beispiel zurück. Angenommen, wir müssen ein Element mit Schlüssel 14 löschen. Stimmen Sie zu, dass, da es das rechte Kind des Knotens mit Schlüssel 10 ist, jeder seiner Nachkommen (in diesem Fall der rechte) einen Schlüssel größer als 10 haben wird, also Sie kann ihn leicht aus dem Baum „ausschneiden“ und den übergeordneten Knoten direkt mit dem untergeordneten Knoten des zu löschenden Knotens verbinden, d. h. Verbinden Sie den Knoten mit Schlüssel 10 mit Knoten 13. Die Situation wäre ähnlich, wenn wir einen Knoten löschen müssten, der das linke Kind seines Elternknotens ist. Denken Sie selbst darüber nach – eine genaue Analogie.
Dritter Fall. Knoten hat zwei Kinder
Der schwierigste Fall. Schauen wir uns ein neues Beispiel an.
Suche nach einem Nachfolger
Nehmen wir an, wir müssen den Knoten mit dem Schlüssel 25 entfernen. Wen sollen wir an seine Stelle setzen? Einer seiner Anhänger (Nachkommen oder Nachkommen von Nachkommen) muss werden Nachfolger(derjenige, der den Platz des entfernten Knotens einnehmen wird).
Woher wissen Sie, wer der Nachfolger sein soll? Intuitiv ist dies der Knoten im Baum, dessen Schlüssel der nächstgrößte des zu entfernenden Knotens ist. Der Algorithmus ist wie folgt. Sie müssen zu seinem rechten Kind gehen (immer zum rechten, da bereits gesagt wurde, dass der Schlüssel des Nachfolgers größer ist als der Schlüssel des zu löschenden Knotens) und dann die Kette der linken Kinder dieses rechten Knotens durchlaufen Kind. Im Beispiel müssen wir zum Knoten mit Schlüssel 35 gehen und dann die Kette seiner linken Kinder zum Blatt hinuntergehen – in diesem Fall besteht diese Kette nur aus dem Knoten mit Schlüssel 30. Genau genommen suchen wir Der kleinste Knoten in der Knotenmenge ist größer als der gewünschte Knoten.
Code der Nachfolgersuchmethode:
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;//родитель преемника
Node<T> successor = deleteNode;//преемник
Node<T> 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;
}
Der vollständige Code der Löschmethode:
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;//В зависимости от того, является ли удаляемый узел левым или правым потомком своего родителя, булевская переменная isLeftChild будет принимать значение true или 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<T> 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)) angenähert werden.
Finden des Maximums/Minimums in einem Baum
Wie man den Minimal-/Maximalwert im Baum findet, ist offensichtlich, dass man nacheinander die Kette der linken bzw. rechten Elemente des Baums durchgehen muss; Wenn Sie das Blatt erreichen, 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;
}
Komplexität - O(log(n))
Symmetrischer Bypass
Beim Durchlaufen wird jeder Knoten des Baums besucht, um etwas damit zu tun.
Rekursiver symmetrischer Traversalalgorithmus:
- Führen Sie eine Aktion für das linke Kind durch
- Machen Sie eine Aktion mit sich selbst
- Führen Sie eine Aktion für das richtige Kind durch
Code:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Abschluss
Endlich! Wenn ich etwas nicht erklärt habe oder Kommentare habe, dann warte ich in den Kommentaren. Wie versprochen gibt es hier den vollständigen Code.
Node.java:
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 void setLeftChild(Node<T> newNode) {
leftChild = newNode;
}
public void setRightChild(Node<T> newNode) {
rightChild = newNode;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
public T getData() {
return data;
}
public int getKey() {
return key;
}
}
BinaryTree.java:
public class BinaryTree<T> {
private Node<T> root;
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;
}
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> 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<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;
}
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;
Node<T> successor = deleteNode;
Node<T> 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<T> current = root;
Node<T> 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<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");
inOrder(current.getRightChild());
}
}
}
PS
Degeneration zu O(n)
Viele von Ihnen haben es vielleicht bemerkt: Was passiert, wenn der Baum aus dem Gleichgewicht gerät? Platzieren Sie beispielsweise Knoten mit aufsteigenden Schlüsseln im Baum: 1,2,3,4,5,6... Dann ähnelt der Baum ein wenig einer verknüpften Liste. Und ja, der Baum verliert seine Baumstruktur und damit die Effizienz des Datenzugriffs. Die Komplexität der Such-, Einfüge- und Löschvorgänge entspricht der einer verknüpften Liste: O(n). Dies ist meiner Meinung nach einer der wichtigsten Nachteile von Binärbäumen.
An der Umfrage können nur registrierte Benutzer teilnehmen. bitte.
Ich bin schon lange nicht mehr auf Habré und würde gerne wissen, welche Artikel zu welchen Themen Sie gerne mehr sehen würden?
-
Datenstrukturen
-
Algorithmen (DP, Rekursion, Datenkomprimierung usw.)
-
Anwendung von Datenstrukturen und Algorithmen im wirklichen Leben
-
Android-Anwendungen in Java programmieren
-
Java-Webanwendungsprogrammierung
2 Benutzer haben abgestimmt. 1 Benutzer enthielt sich der Stimme.
Quelle: www.habr.com