EinfĂŒhrung
Dieser Artikel befasst sich mit binĂ€ren SuchbĂ€umen. KĂŒrzlich habe ich einen Artikel ĂŒber Dabei habe ich nicht viel auf binĂ€re BĂ€ume geachtet, da die Methoden zum Suchen, 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 ein Spezialfall eines Grafen ist. Hier ist ein Beispiel fĂŒr einen Baum:
Das ist kein binÀrer Suchbaum! Alles unter dem Cut!
Terminologie
Wurzel
Die Wurzel des Baumes ist der oberste Knoten. In unserem Beispiel ist das der Knoten A. Im Baum kann von der Wurzel zu jedem anderen Knoten nur ein Weg fĂŒhren! 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 ĂŒber dem aktuellen Knoten liegt, wird Elternteil dieses Knotens genannt. Der Knoten, der unter dem aktuellen Knoten liegt und mit diesem verbunden ist, wird Kind dieses Knotens genannt. Lassen Sie uns ein Beispiel nehmen. Nehmen wir den Knoten B, dann wird sein Elternteil der Knoten A sein, und seine Kinder sind die Knoten D, E und F.
Blatt
Ein Knoten, der keine Kinder hat, wird als Blatt des Baumes bezeichnet. In unserem Beispiel sind die BlÀtter die Knoten D, E, F, G, I, J, K.
Das ist die grundlegende Terminologie. Weitere Begriffe werden spĂ€ter behandelt. Ein binĂ€rer Baum ist ein Baum, in dem jeder Knoten nicht mehr als zwei Kinder haben kann. Wie Sie erraten haben, wird der Baum aus dem Beispiel kein binĂ€rer Baum sein, da die Knoten B und H mehr als zwei Kinder haben. Hier ist ein Beispiel fĂŒr einen binĂ€ren Baum:
In den Knoten eines Baumes kann jede Art von Information gespeichert werden. Ein binÀrer Suchbaum ist ein binÀrer Baum, der die folgenden Eigenschaften aufweist:
- Beide TeilbĂ€ume â der linke und der rechte â sind binĂ€re SuchbĂ€ume.
- Bei allen Knoten des linken Teilbaums eines beliebigen Knotens X sind die Werte der SchlĂŒsseldaten kleiner als der Wert des SchlĂŒssels des Knotens X selbst.
- Bei allen Knoten des rechten Teilbaums eines beliebigen Knotens X sind die Werte der SchlĂŒsseldaten gröĂer oder gleich dem Wert des SchlĂŒssels des Knotens X selbst.
SchlĂŒssel - eine bestimmte Eigenschaft des Knotens (zum Beispiel eine Zahl). Der SchlĂŒssel ist nötig, um das Element des Baumes zu finden, das diesem SchlĂŒssel entspricht. Beispiel fĂŒr einen binĂ€ren Suchbaum:
Baumdarstellung
Im Verlauf werde ich einige (möglicherweise unvollstĂ€ndige) Codeabschnitte anfĂŒhren, um Ihr VerstĂ€ndnis zu verbessern. Der vollstĂ€ndige Code wird am Ende des Artikels zu finden sein.
Ein Baum besteht aus Knoten. Die Struktur eines Knotens:
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 Node getLeftChild() {
return leftChild;
}
public Node getRightChild() {
return rightChild;
}
//... weitere Methoden des Knotens
}
Jeder Knoten hat zwei Nachkommen (es ist durchaus möglich, dass der Nachfolger leftChild und/oder rightChild den Wert null enthalten). Sie haben wahrscheinlich verstanden, dass in diesem Fall die Zahl data â die Daten, die im Knoten gespeichert sind; key â der SchlĂŒssel des Knotens ist.
Mit dem Knoten haben wir uns beschĂ€ftigt, jetzt lassen Sie uns ĂŒber drĂ€ngende Probleme von BĂ€umen sprechen. Hier und im Folgenden wird unter dem Begriff âBaumâ das Konzept eines binĂ€ren Suchbaums verstanden. Die Struktur eines binĂ€ren Baumes:
public class BinaryTree {
private Node root;
// Methoden des Baumes
}
Als Klassenfeld benötigen wir nur die Wurzel des Baumes, denn von der Wurzel aus kann man mit Hilfe der Methoden getLeftChild() und getRightChild() zu jedem Knoten des Baumes gelangen.
Algorithmen im Baum
Die Suche
Angenommen, Sie haben einen Baum konstruiert. Wie finden Sie ein Element mit dem SchlĂŒssel key? Sie mĂŒssen nacheinander vom Wurzelknoten nach unten durch den Baum gehen und den Wert key mit dem SchlĂŒssel des aktuellen Knotens vergleichen: wenn key kleiner ist als der SchlĂŒssel des aktuellen Knotens, gehen Sie zum linken Nachkommen des Knotens, wenn gröĂer â zum rechten, wenn die SchlĂŒssel gleich sind â der gesuchte Knoten ist gefunden! Der entsprechende Code lautet:
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;
}
Wenn current gleich null wird, bedeutet dies, dass die Durchsuchung das Ende des Baumes erreicht hat (auf konzeptioneller Ebene befinden Sie sich an einem nicht existierenden Ort des Baumes â dem Nachkommen eines Blattes).
Betrachten wir die Effizienz des Suchalgorithmus in einem ausgewogenen Baum (einem Baum, in dem die Knoten mehr oder weniger gleichmĂ€Ăig verteilt sind). Dann betrĂ€gt die Effizienz der Suche O(log(n)), wobei der Logarithmus zur Basis 2 ist. Siehe: Wenn der ausgewogene Baum n Elemente hat, bedeutet das, dass es log(n) zur Basis 2 Ebenen im Baum geben wird. Und bei der Suche steigen Sie in einem Schritt der Schleife um ein Level ab.
EinfĂŒgen
Wenn Sie das Wesen der Suche verstanden haben, wird es Ihnen leichtfallen, die EinfĂŒgung zu verstehen. Sie mĂŒssen einfach zum Blatt des Baumes hinuntergehen (nach den in der Suche beschriebenen Absteigregeln) und dessen Nachkomme werden â links oder rechts, je nach SchlĂŒssel. Implementierung:
public void insert(T insertData, int key) {\n Node current = root;\n Node parent;\n Node newNode = new Node(insertData, key);\n if (root == null)\n root = newNode;\n else {\n while (true) {\n parent = current;\n if (key < current.getKey()) {\n current = current.getLeftChild();\n if (current == null) {\n parent.setLeftChild(newNode);\n return;\n }\n }\n else {\n current = current.getRightChild();\n if (current == null) {\n parent.setRightChild(newNode);\n return;\n }\n }\n }\n }\n }
In diesem Fall mĂŒssen wir, neben dem aktuellen Knoten, Informationen ĂŒber den Elter des aktuellen Knotens speichern. Wenn current null wird, wird in der Variable parent das benötigte Blatt liegen.
Die Effizienz der EinfĂŒgung wird offensichtlich die gleiche sein wie die der Suche â O(log(n)).
Löschen
Das Löschen ist die komplexeste Operation, die mit dem Baum durchgefĂŒhrt werden muss. ZunĂ€chst muss das Element gefunden werden, das wir löschen möchten. Aber was dann? Wenn wir einfach den Wert null zu seiner Referenz zuweisen, verlieren wir die Informationen ĂŒber den Teilbaum, dessen Wurzel dieser Knoten ist. Die Methoden zum Löschen von BĂ€umen unterscheiden sich in drei FĂ€lle.
Erster Fall. Der zu löschende Knoten hat keine Nachkommen.
Wenn der zu löschende Knoten keine Nachkommen 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 Nachkommen.
Dieser Fall ist auch nicht sehr kompliziert. Kehren wir zu unserem Beispiel zurĂŒck. Angenommen, wir mĂŒssen das Element mit dem SchlĂŒssel 14 löschen. Sie werden zustimmen, dass, da es ein rechter Nachkomme des Knotens mit dem SchlĂŒssel 10 ist, jeder seiner Nachkommen (in diesem Fall der rechte) einen SchlĂŒssel gröĂer als 10 haben wird. Daher können wir es leicht aus dem Baum 'heraus schneiden', 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 gĂ€be es, wenn wir einen Knoten löschen mĂŒssten, der ein linker Nachkomme seines Elternteils ist. Denken Sie selbst darĂŒber nach â es ist eine genaue Analogie.
Dritter Fall. Der Knoten hat zwei Nachkommen.
Der komplizierteste Fall. Lassen Sie uns an einem neuen Beispiel untersuchen.
Suche nach dem Nachfolger.
Angenommen, wir mĂŒssen einen Knoten mit dem SchlĂŒssel 25 löschen. Wen setzen wir an seine Stelle? Jemand aus seinen Nachfolgern (Nachkommen oder Nachkommen von Nachkommen) muss der Nachfolger(derjenige, der den Platz des gelöschten Knotens einnimmt).
Wie versteht man, wer Nachfolger werden soll? Intuitiv ist klar, dass dies ein Knoten im Baum ist, dessen SchlĂŒssel der nĂ€chstgröĂere vom gelöschten Knoten ist. Der Algorithmus besteht darin, dass wir zu seinem rechten Nachkommen (immer zum rechten, da bereits gesagt wurde, dass der SchlĂŒssel des Nachfolgers gröĂer als der SchlĂŒssel des gelöschten Knotens ist) wechseln und dann die Kette der linken Nachkommen dieses rechten Nachkommens durchlaufen. In unserem Beispiel mĂŒssen wir zum Knoten mit dem SchlĂŒssel 35 wechseln und dann bis zum Blatt der Kette seiner linken Nachkommen hinuntergehen â in diesem Fall besteht diese Kette nur aus dem Knoten mit dem SchlĂŒssel 30. Streng genommen suchen wir den kleinsten Knoten in der Menge der Knoten, die gröĂer sind als der gesuchte Knoten.
Code des Nachfolgerfindungsalgorithmus:
public Node getSuccessor(Node deleteNode) {
Node parentSuccessor = deleteNode; // Elternteil des Nachfolgers
Node successor = deleteNode; // Nachfolger
Node current = successor.getRightChild(); // einfach ein "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 Nachkommen des gelöschten Knotens ĂŒbereinstimmt
parentSuccessor.setLeftChild(successor.getRightChild()); // dann ĂŒbernimmt sein Elternteil den Nachkommen des Nachfolgers, um ihn nicht zu verlieren
successor.setRightChild(deleteNode.getRightChild()); // verbinden den Nachfolger mit dem rechten Nachkommen des gelöschten Knotens
}
return successor;
}
VollstÀndiger Code der Methode delete:
public boolean delete(int deleteKey) {
Node current = root;
Node parent = current;
boolean isLeftChild = false; // AbhÀngig davon, ob der zu löschende Knoten ein linkes oder rechtes Kind seines Elternteils ist, wird die boolesche Variable isLeftChild entweder true oder false annehmen.
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 auf O(log(n)) abgeschÀtzt werden.
Suche nach dem Maximum/Minimum im Baum
Offensichtlich, um den minimalen/maximalen Wert im Baum zu finden â man muss der Reihe nach die Kette der linken/rechten Elemente des Baums durchlaufen; wenn man den Blatt erreicht, ist dieser der minimale/maximale Element.
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;
}
Die KomplexitÀt ist O(log(n))
Symmetrische Traversierung
Traversal â jeder Knoten des Baumes wird besucht, um eine Aktion mit ihm durchzufĂŒhren.
Algorithmus der rekursiven symmetrischen Traversierung:
- Aktion mit dem linken Kind durchfĂŒhren
- Aktion mit sich selbst durchfĂŒhren
- Aktion mit dem rechten Kind durchfĂŒhren
Code:
public void inOrder(Node 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 unklar ausgedrĂŒckt habe oder es Anmerkungen gibt, erwarte ich diese in den Kommentaren. 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<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());
}
}
}
P.S.
Degeneration bis O(n)
Viele von Ihnen haben vielleicht bemerkt: Was wĂ€re, wenn das Baumstruktur unausgewogen wird? Zum Beispiel, indem man Knoten mit aufsteigenden SchlĂŒsseln in den Baum einfĂŒgt: 1,2,3,4,5,6⊠Dann Ă€hnelt der Baum etwas einer verketteten Liste. Und ja, der Baum verliert seine baumartige Struktur, was zu einer Verringerung der Effizienz beim Datenzugriff fĂŒhrt. Die KomplexitĂ€t von Such-, EinfĂŒge- und Löschoperationen wird gleich der einer verketteten Liste sein: O(n). Dies ist einer der wichtigsten, meiner Meinung nach, Nachteile von binĂ€ren BĂ€umen.
Nur registrierte Benutzer können an der Umfrage teilnehmen. .
Ich bin noch nicht lange auf HabrĂ©, und ich wĂŒrde gerne wissen, ĂŒber welche Themen Sie mehr Artikel sehen möchten?
Datenstrukturen
Algorithmen (DP, Rekursion, Datenkompression usw.)
Anwendung von Datenstrukturen und Algorithmen im echten Leben
Programmierung von Android-Anwendungen in Java
Programmierung von Webanwendungen in Java
2 Benutzer haben abgestimmt. 1 Benutzer hat sich enthalten.
Quelle: habr.com
