Binärer Suchbaum in Java

binary search tree java implementation code examples

Versuchen Sie Unser Instrument, Um Probleme Zu Beseitigen

Wählen Sie Das Betriebssystem Aus Wählen Sie Ein Projektionsprogramm (Optional)

Beschreiben Sie Ihr Problem

Dieses Tutorial behandelt den binären Suchbaum in Java. Sie lernen, eine BST zu erstellen, ein Element einzufügen, zu entfernen und zu suchen, eine BST in Java zu durchlaufen und zu implementieren:

Ein binärer Suchbaum (im Folgenden als BST bezeichnet) ist eine Art binärer Baum. Es kann auch als knotenbasierter Binärbaum definiert werden. BST wird auch als 'Bestellter Binärbaum' bezeichnet. In BST haben alle Knoten im linken Teilbaum Werte, die kleiner als der Wert des Stammknotens sind.

In ähnlicher Weise haben alle Knoten des rechten Teilbaums der BST Werte, die größer als der Wert des Wurzelknotens sind. Diese Reihenfolge der Knoten muss auch für die jeweiligen Teilbäume gelten.

=> Besuchen Sie hier für die exklusive Java Training Tutorial-Reihe.

Was du lernen wirst:

Binärer Suchbaum in Java
Fazit
- Literatur-Empfehlungen

Eine BST erlaubt keine doppelten Knoten.

Das folgende Diagramm zeigt eine BST-Darstellung:

Oben gezeigt ist ein Beispiel BST. Wir sehen, dass 20 der Wurzelknoten dieses Baumes ist. Der linke Teilbaum enthält alle Knotenwerte, die kleiner als 20 sind. Der rechte Teilbaum enthält alle Knoten, die größer als 20 sind. Wir können sagen, dass der obige Baum die BST-Eigenschaften erfüllt.

Die BST-Datenstruktur wird im Vergleich zu Arrays und verknüpften Listen beim Einfügen / Löschen und Suchen von Elementen als sehr effizient angesehen.

BST benötigt O (log n) Zeit, um nach einem Element zu suchen. Bei der Reihenfolge der Elemente wird bei jedem Schritt bei der Suche nach einem Element die Hälfte des Teilbaums verworfen. Dies wird möglich, weil wir leicht die grobe Position des zu durchsuchenden Elements bestimmen können.

In ähnlicher Weise sind Einfüge- und Löschvorgänge in BST effizienter. Wenn wir ein neues Element einfügen möchten, wissen wir ungefähr, in welchen Teilbaum (links oder rechts) wir das Element einfügen werden.

Erstellen eines binären Suchbaums (BST)

Bei einer Reihe von Elementen müssen wir eine BST erstellen.

Gehen wir wie folgt vor:

Gegebenes Array: 45, 10, 7, 90, 12, 50, 13, 39, 57

Betrachten wir zunächst das oberste Element, d. H. 45, als Wurzelknoten. Von hier aus werden wir die BST unter Berücksichtigung der bereits besprochenen Eigenschaften erstellen.

Um einen Baum zu erstellen, vergleichen wir jedes Element im Array mit dem Stamm. Dann platzieren wir das Element an einer geeigneten Position im Baum.

Der gesamte Erstellungsprozess für BST ist unten dargestellt.

BST abgeschlossen

Binäre Suchbaumoperationen

BST unterstützt verschiedene Operationen. Die folgende Tabelle zeigt die von BST in Java unterstützten Methoden. Wir werden jede dieser Methoden separat diskutieren.

Methode / Operation	Beschreibung
Einfügen	Fügen Sie der BST ein Element hinzu, indem Sie die BST-Eigenschaften nicht verletzen.
Löschen	Entfernen Sie einen bestimmten Knoten aus der BST. Der Knoten kann der Wurzelknoten, der Nicht-Blatt- oder der Blattknoten sein.
Suche	Suchen Sie die Position des angegebenen Elements in der BST. Diese Operation prüft, ob der Baum den angegebenen Schlüssel enthält.

Fügen Sie ein Element in BST ein

Ein Element wird in BST immer als Blattknoten eingefügt.

Im Folgenden sind die Schritte zum Einfügen eines Elements aufgeführt.

Beginnen Sie von der Wurzel.
Vergleichen Sie das einzufügende Element mit dem Wurzelknoten. Wenn es kleiner als root ist, durchlaufen Sie den linken Teilbaum oder den rechten Teilbaum.
Durchqueren Sie den Teilbaum bis zum Ende des gewünschten Teilbaums. Fügen Sie den Knoten als Blattknoten in den entsprechenden Teilbaum ein.

Sehen wir uns eine Illustration der Einfügeoperation von BST an.

Betrachten Sie die folgende BST und fügen Sie Element 2 in den Baum ein.

Abbildung 1

Figur 2

Die Einfügeoperation für BST ist oben gezeigt. In Abb. (1) zeigen wir den Pfad, den wir durchlaufen, um Element 2 in die BST einzufügen. Wir haben auch die Bedingungen gezeigt, die an jedem Knoten überprüft werden. Als Ergebnis des rekursiven Vergleichs wird Element 2 als rechtes Kind von 1 eingefügt, wie in Abb. (2) gezeigt.

Suchvorgang in BST

Um zu suchen, ob ein Element in der BST vorhanden ist, beginnen wir erneut mit der Wurzel und durchlaufen dann den linken oder rechten Teilbaum, je nachdem, ob das zu durchsuchende Element kleiner oder größer als die Wurzel ist.

Nachfolgend sind die Schritte aufgeführt, die wir befolgen müssen.

Vergleichen Sie das zu durchsuchende Element mit dem Stammknoten.
Wenn der Schlüssel (zu durchsuchendes Element) = root ist, geben Sie root node zurück.
Sonst wenn Schlüssel
Andernfalls durchqueren Sie den rechten Teilbaum.
Vergleichen Sie Teilbaumelemente wiederholt, bis der Schlüssel gefunden oder das Ende des Baums erreicht ist.

Lassen Sie uns den Suchvorgang anhand eines Beispiels veranschaulichen. Bedenken Sie, dass wir den Schlüssel = 12 suchen müssen.

In der folgenden Abbildung verfolgen wir den Pfad, dem wir folgen, um nach diesem Element zu suchen.

Wie in der obigen Abbildung gezeigt, vergleichen wir zuerst den Schlüssel mit root. Da der Schlüssel größer ist, durchlaufen wir den rechten Teilbaum. Im rechten Teilbaum vergleichen wir den Schlüssel erneut mit dem ersten Knoten im rechten Teilbaum.

Wir stellen fest, dass der Schlüssel kleiner als 15 ist. Wir bewegen uns also zum linken Teilbaum von Knoten 15. Der unmittelbare linke Knoten von 15 ist 12, der dem Schlüssel entspricht. An diesem Punkt stoppen wir die Suche und geben das Ergebnis zurück.

Element aus der BST entfernen

Wenn wir einen Knoten aus der BST löschen, gibt es drei Möglichkeiten, wie unten erläutert:

Knoten ist ein Blattknoten

Wenn ein zu löschender Knoten ein Blattknoten ist, können wir diesen Knoten direkt löschen, da er keine untergeordneten Knoten hat. Dies ist im folgenden Bild dargestellt.

Wie oben gezeigt, ist der Knoten 12 ein Blattknoten und kann sofort gelöscht werden.

Knoten hat nur ein Kind

Wenn wir den Knoten löschen müssen, der ein Kind hat, kopieren wir den Wert des Kindes in den Knoten und löschen dann das Kind.

Im obigen Diagramm möchten wir den Knoten 90 löschen, der ein Kind 50 hat. Also tauschen wir den Wert 50 mit 90 aus und löschen dann den Knoten 90, der jetzt ein Kindknoten ist.

Knoten hat zwei Kinder

Wenn ein zu löschender Knoten zwei untergeordnete Knoten hat, ersetzen wir den Knoten durch den ungeordneten Nachfolger (links-rechts-rechts) des Knotens oder sagen einfach den minimalen Knoten im rechten Teilbaum, wenn der rechte Teilbaum des Knotens nicht leer ist. Wir ersetzen den Knoten durch diesen Mindestknoten und löschen den Knoten.

Im obigen Diagramm möchten wir den Knoten 45 löschen, der der Wurzelknoten von BST ist. Wir stellen fest, dass der rechte Teilbaum dieses Knotens nicht leer ist. Dann durchlaufen wir den rechten Teilbaum und stellen fest, dass der Knoten 50 hier der minimale Knoten ist. Also ersetzen wir diesen Wert anstelle von 45 und löschen dann 45.

Wenn wir den Baum überprüfen, sehen wir, dass er die Eigenschaften einer BST erfüllt. Somit war der Knotenaustausch korrekt.

Implementierung des binären Suchbaums (BST) in Java

Das folgende Programm in Java demonstriert alle oben genannten BST-Operationen anhand des gleichen Baums, der in der Abbildung als Beispiel verwendet wird.

SQL Query Interview Fragen und Antworten für erfahrene PDF

class BST_class { //node class that defines BST node class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } // BST root node Node root; // Constructor for BST =>initial empty tree BST_class(){ root = null; } //delete a node from BST void deleteKey(int key) { root = delete_Recursive(root, key); } //recursive delete function Node delete_Recursive(Node root, int key) { //tree is empty if (root == null) return root; //traverse the tree if (key root.key) //traverse right subtree root.right = delete_Recursive(root.right, key); else { // node contains only one child if (root.left == null) return root.right; else if (root.right == null) return root.left; // node has two children; //get inorder successor (min value in the right subtree) root.key = minValue(root.right); // Delete the inorder successor root.right = delete_Recursive(root.right, root.key); } return root; } int minValue(Node root) { //initially minval = root int minval = root.key; //find minval while (root.left != null) { minval = root.left.key; root = root.left; } return minval; } // insert a node in BST void insert(int key) { root = insert_Recursive(root, key); } //recursive insert function Node insert_Recursive(Node root, int key) { //tree is empty if (root == null) { root = new Node(key); return root; } //traverse the tree if (key root.key) //insert in the right subtree root.right = insert_Recursive(root.right, key); // return pointer return root; } // method for inorder traversal of BST void inorder() { inorder_Recursive(root); } // recursively traverse the BST void inorder_Recursive(Node root) { if (root != null) { inorder_Recursive(root.left); System.out.print(root.key + ' '); inorder_Recursive(root.right); } } boolean search(int key) { root = search_Recursive(root, key); if (root!= null) return true; else return false; } //recursive insert function Node search_Recursive(Node root, int key) // Base Cases: root is null or key is present at root if (root==null } class Main{ public static void main(String() args) { //create a BST object BST_class bst = new BST_class(); /* BST tree example 45 /  10 90 /  / 7 12 50 */ //insert data into BST bst.insert(45); bst.insert(10); bst.insert(7); bst.insert(12); bst.insert(90); bst.insert(50); //print the BST System.out.println('The BST Created with input data(Left-root-right):'); bst.inorder(); //delete leaf node System.out.println('
The BST after Delete 12(leaf node):'); bst.deleteKey(12); bst.inorder(); //delete the node with one child System.out.println('
The BST after Delete 90 (node with 1 child):'); bst.deleteKey(90); bst.inorder(); //delete node with two children System.out.println('
The BST after Delete 45 (Node with two children):'); bst.deleteKey(45); bst.inorder(); //search a key in the BST boolean ret_val = bst.search (50); System.out.println('
Key 50 found in BST:' + ret_val ); ret_val = bst.search (12); System.out.println('
Key 12 found in BST:' + ret_val ); } }

Ausgabe:

BST-Traversal (Binary Search Tree) in Java

Ein Baum ist eine hierarchische Struktur, daher können wir ihn nicht wie andere Datenstrukturen wie Arrays linear durchlaufen. Jeder Baumtyp muss auf besondere Weise durchlaufen werden, damit alle seine Teilbäume und Knoten mindestens einmal besucht werden.

Abhängig von der Reihenfolge, in der der Wurzelknoten, der linke Teilbaum und der rechte Teilbaum in einem Baum durchlaufen werden, gibt es bestimmte Durchläufe, wie unten gezeigt:

Inorder Traversal
Traversal vorbestellen
PostOrder Traversal

Alle obigen Durchquerungen verwenden die Tiefentechnik, d. H. Der Baum wird in der Tiefe durchlaufen.

Die Bäume verwenden auch die Breitentechnik zum Durchqueren. Der Ansatz mit dieser Technik heißt 'Level Order' Durchquerung.

In diesem Abschnitt werden wir jede der Durchquerungen anhand des folgenden BST als Beispiel demonstrieren.

Bei der im obigen Diagramm gezeigten BST beträgt die Durchquerung der Ebenenreihenfolge für den obigen Baum:

Level Order Traversal: 10 6 12 4 8

Inorder Traversal

Der Inorder-Traversal-Ansatz durchlief die BST in der Reihenfolge, Linker Teilbaum => RootNode => Rechter Teilbaum . Die Inorder Traversal liefert eine abnehmende Folge von Knoten einer BST.

Der Algorithmus InOrder (bstTree) für InOrder Traversal ist unten angegeben.

Durchlaufen Sie den linken Teilbaum mit InOrder (left_subtree).
Besuchen Sie den Stammknoten.
Durchlaufe den rechten Teilbaum mit InOrder (right_subtree)

Die Inorder Traversal des obigen Baums ist:

4 6 8 10 12

Wie zu sehen ist, ist die Reihenfolge der Knoten als Ergebnis der Inorder Traversal in absteigender Reihenfolge.

Traversal vorbestellen

Bei der Vorbestellungsdurchquerung wird zuerst die Wurzel besucht, gefolgt vom linken Teilbaum und dem rechten Teilbaum. Durch die Vorbestellungsdurchquerung wird eine Kopie des Baums erstellt. Es kann auch in Ausdrucksbäumen verwendet werden, um Präfixausdrücke zu erhalten.

Der Algorithmus für das Durchlaufen von PreOrder (bst_tree) ist unten angegeben:

Besuchen Sie den Stammknoten
Durchqueren Sie den linken Teilbaum mit PreOrder (left_subtree).
Durchqueren Sie den rechten Teilbaum mit PreOrder (right_subtree).

Die oben angegebene Vorbestellungsdurchquerung für die BST lautet:

10 6 4 8 12

PostOrder Traversal

Die PostOrder-Durchquerung durchläuft die BST in der folgenden Reihenfolge: Linker Teilbaum-> Rechter Teilbaum-> Wurzelknoten . PostOrder-Traversal wird verwendet, um den Baum zu löschen oder den Postfix-Ausdruck bei Ausdrucksbäumen abzurufen.

Der Algorithmus für das Durchlaufen von postOrder (bst_tree) lautet wie folgt:

Durchqueren Sie den linken Teilbaum mit postOrder (left_subtree).
Durchqueren Sie den rechten Teilbaum mit postOrder (right_subtree).
Besuchen Sie den Stammknoten

Die PostOrder-Durchquerung für das obige Beispiel BST lautet:

4 8 6 12 10

Als Nächstes werden wir diese Durchquerungen mithilfe der Deep-First-Technik in einer Java-Implementierung implementieren.

//define node of the BST class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } //BST class class BST_class { // BST root node Node root; BST_class(){ root = null; } //PostOrder Traversal - Left:Right:rootNode (LRn) void postOrder(Node node) { if (node == null) return; // first traverse left subtree recursively postOrder(node.left); // then traverse right subtree recursively postOrder(node.right); // now process root node System.out.print(node.key + ' '); } // InOrder Traversal - Left:rootNode:Right (LnR) void inOrder(Node node) { if (node == null) return; //first traverse left subtree recursively inOrder(node.left); //then go for root node System.out.print(node.key + ' '); //next traverse right subtree recursively inOrder(node.right); } //PreOrder Traversal - rootNode:Left:Right (nLR) void preOrder(Node node) { if (node == null) return; //first print root node first System.out.print(node.key + ' '); // then traverse left subtree recursively preOrder(node.left); // next traverse right subtree recursively preOrder(node.right); } // Wrappers for recursive functions void postOrder_traversal() { postOrder(root); } void inOrder_traversal() { inOrder(root); } void preOrder_traversal() { preOrder(root); } } class Main{ public static void main(String() args) { //construct a BST BST_class tree = new BST_class(); /* 45 // \ 10 90 // \ 7 12 */ tree.root = new Node(45); tree.root.left = new Node(10); tree.root.right = new Node(90); tree.root.left.left = new Node(7); tree.root.left.right = new Node(12); //PreOrder Traversal System.out.println('BST => PreOrder Traversal:'); tree.preOrder_traversal(); //InOrder Traversal System.out.println('
BST => InOrder Traversal:'); tree.inOrder_traversal(); //PostOrder Traversal System.out.println('
BST => PostOrder Traversal:'); tree.postOrder_traversal(); } }

Ausgabe:

Häufig gestellte Fragen

F # 1) Warum brauchen wir einen binären Suchbaum?

Antworten : Die Art und Weise, wie wir nach Elementen in der linearen Datenstruktur wie Arrays mithilfe der binären Suchtechnik suchen, wobei der Baum eine hierarchische Struktur ist, benötigen wir eine Struktur, mit der Elemente in einem Baum lokalisiert werden können.

Hier kommt der binäre Suchbaum ins Spiel, der uns bei der effizienten Suche nach Elementen im Bild hilft.

F # 2) Was sind die Eigenschaften eines binären Suchbaums?

Antworten :: Ein binärer Suchbaum, der zur Kategorie binärer Baum gehört, hat die folgenden Eigenschaften:

Die in einem binären Suchbaum gespeicherten Daten sind eindeutig. Es sind keine doppelten Werte zulässig.
Die Knoten des linken Teilbaums sind kleiner als der Wurzelknoten.
Die Knoten des rechten Teilbaums sind größer als der Wurzelknoten.

F # 3) Was sind die Anwendungen eines binären Suchbaums?

Antworten : Wir können binäre Suchbäume verwenden, um einige kontinuierliche Funktionen in der Mathematik zu lösen. Das Suchen von Daten in hierarchischen Strukturen wird mit binären Suchbäumen effizienter. Mit jedem Schritt reduzieren wir die Suche um die Hälfte des Teilbaums.

F # 4) Was ist der Unterschied zwischen einem Binärbaum und einem Binärsuchbaum?

Antworten: Ein Binärbaum ist eine hierarchische Baumstruktur, in der jeder als übergeordneter Knoten bekannte Knoten höchstens zwei untergeordnete Knoten haben kann. Ein binärer Suchbaum erfüllt alle Eigenschaften des binären Baums und hat auch seine eindeutigen Eigenschaften.

In einem binären Suchbaum enthalten die linken Teilbäume Knoten, die kleiner oder gleich dem Wurzelknoten sind, und der rechte Teilbaum enthält Knoten, die größer als der Wurzelknoten sind.

F # 5) Ist der binäre Suchbaum einzigartig?

Antworten : Ein binärer Suchbaum gehört zu einer binären Baumkategorie. Es ist einzigartig in dem Sinne, dass es keine doppelten Werte zulässt und auch alle seine Elemente nach einer bestimmten Reihenfolge sortiert sind.

Fazit

Binäre Suchbäume sind Teil der Kategorie der binären Bäume und werden hauptsächlich zum Suchen hierarchischer Daten verwendet. Es wird auch zur Lösung einiger mathematischer Probleme verwendet.

In diesem Tutorial haben wir die Implementierung eines binären Suchbaums gesehen. Wir haben auch verschiedene Operationen an BST mit ihrer Darstellung gesehen und auch die Durchquerungen für BST untersucht.

=> Sehen Sie sich hier die einfache Java-Schulungsreihe an.

Binärer Suchbaum in Java - Implementierungs- und Codebeispiele