Bestimmen Sie die Höhe des binären Suchbaums in Java

1. der binäre Suchbaum
2. Anwendung des binären Suchbaums
3. Bestimmen Sie die Höhe des binären Suchbaums

In diesem ausführlichen Artikel lernen wir die Grundlagen eines binären Suchbaums kennen, bevor wir ein rekursives Suchprogramm implementieren, um die Höhe eines Baums in unserem Java-Programm zu bestimmen. Um dieses Tutorial zu verstehen, empfehlen wir Ihnen, über ein grundlegendes Verständnis der Datenstrukturkonzepte von Bäumen zu verfügen.

der binäre Suchbaum

Halten wir es einfach. Wir werden Sie nicht mit dem langwierigen theoretischen Konzept langweilen. Im Folgenden sind jedoch die Kernkonzepte aufgeführt, mit denen Sie vertraut sein sollten:

1. Eine einzelne Referenz auf den Wurzelknoten einer hierarchischen Datenstruktur.
2. Für jeden Knoten existieren maximal zwei Kindknoten (ein linkes und ein rechtes Kind).
3. Die Funktion Binäre Suche organisiert Knoten:
   • Jeder Knoten ist nach einem oder mehreren Schlüsseldatenfeldern sortiert.
   • Der Schlüssel jedes Knotens im Baum ist größer als der Schlüssel seines linken Kindes und muss kleiner sein als der Schlüssel seines rechten Kindes.
   • Abbildung: Binärer Suchbaum:

Anwendung des binären Suchbaums

Halten wir es einfach. Wir werden Sie nicht mit dem langwierigen theoretischen Konzept langweilen.

Im Folgenden sind jedoch die Kernkonzepte aufgeführt, mit denen Sie vertraut sein sollten:

1. Sie können auch ein BST verwenden, bei dem der Fluss und die Struktur von Daten ständig ein- oder austreten, wie z. B. die Methoden map und set in den meisten Programmiersprachen, einschließlich Java.

2. Wir können BST auch in dreidimensionalen Videospielen verwenden, um die Position von Objekten und den Rendering-Prozess zu bestimmen. Lesen Sie mehr über die Speicherplatzpartition mit BST: Binäre Speicherplatzpartition.

3. Wenn wir hauptsächlich über Netzwerke sprechen, können wir diese Bäume in fast jedem Router mit hoher Bandbreite zum Speichern von Router-Tabellen verwenden; Binäre Versuche.

4. Wenn Sie sich für Torrents und die einzigartige Generierung von Bildsignaturen interessieren. Angenommen, Sie möchten die Hash-Anforderungen überprüfen, aber die gesamte Datei ist nicht verfügbar.

   Dort können Sie auch BST verwenden. Weiterlesen: Hash Trees

Kurz gesagt, wir können binäre Suchbäume in verschiedenen Anwendungen verwenden, dank ihrer Fähigkeit, die gewünschten Daten zu ordnen. Wir können eine mehrstufige Indizierung mit einem binären Suchbaum durchführen.

Darüber hinaus können wir sie auch zur Implementierung verschiedener Suchalgorithmen verwenden. Da BSTs helfen können, einen sortierten Datenstrom zu halten.

Bestimmen Sie die Höhe des binären Suchbaums

Die Bestimmung der Höhe eines binären Suchbaums ist keine schwierige Aufgabe, wenn Sie diesen einfachen Schritten folgen:

1. Die Länge des längsten Pfads von der Wurzel zu einem Blattknoten bestimmt die Höhe eines Binärbaums. Sie wird auch als Tiefe eines Binärbaums bezeichnet.

   Die Höhe der Wurzel entspricht der Höhe des Baumes.

2. Die Tiefe eines Knotens ist die Länge des Pfades zu seiner Wurzel.

3. Um die Höhe des Baumes zu berechnen, müssen wir die Anzahl der Kanten zwischen der Wurzel und dem am weitesten entfernten Blatt zählen.

Wie Sie in der obigen Grafik sehen, beträgt die Anzahl der Kanten zwischen der Wurzel und dem am weitesten entfernten Blatt 3. Daher beträgt die Höhe des Baums auch 3.

Suchen Sie nach einem bestimmten Schlüssel im binären Suchbaum

Sie können rekursiv oder iterativ nach einem bestimmten Schlüssel in einem binären Suchbaum suchen. Beide Methoden sind beliebte Wahlen für verschiedene Datenstrukturoperationen.

Wenn wir über das rekursive Suchverfahren sprechen, beginnt der Suchprozess mit einer Untersuchung des Wurzelknotens. Nehmen wir in diesem Zusammenhang an, dass der Baum null ist, dann existiert der gesuchte Schlüssel nicht im Baum.

Wenn das Suchergebnis erfolgreich ist, wird der Knoten zurückgegeben, wenn der Schlüssel mit der Wurzel übereinstimmt. Angenommen, der Schlüssel ist kleiner als die Wurzel, und die Programmsuche bewegt sich dann zum linken Teilbaum.

Rekursive Schritte zum Ermitteln der Höhe des binären Suchbaums

Sie sollten beachten, dass die Höhe eines leeren Baums 0 ist. Im Gegenteil, Sie müssen vom obersten Knoten nach unten beginnen.

Angenommen, wir wollen die maximale Tiefe des linken Teilbaums rekursiv bestimmen. Die maximale Tiefe dieser beiden ist die Höhe des Binärbaums (linker und rechter Teilbaum).

Schauen Sie sich den folgenden Pseudocode an.

BinarySearchTree(a, k)
   if a = NIL or k = a.key then
     return a
   if k < a.key then
     return Tree-Search(a.L, k)
   else
     return Tree-Search(a.R, k)
   end if

Lassen Sie uns unser Programm rekursiv implementieren, um die Höhe innerhalb einer BST zu suchen.

Beispiel:

package heightofbinarysearchBSTree.delftstack;
// Java program to find the height of BSTree
// A binary BSTree BSTreeNode
public class DetHeight {
  int BSTreedata;
  DetHeight BSTreeNodeLeft, BSTreeNoderight;
  DetHeight(int i) {
    BSTreedata = i;
    BSTreeNodeLeft = BSTreeNoderight = null;
  }
}
class BST {
  DetHeight BSTreeroot;
  /* Compute the "MaximumHeight" of a BSTree -- the number of
  BSTreeNodes along the longest path from the BSTreeroot BSTreeNode
  down to the farthest leaf BSTreeNode.*/
  int MaximumHeight(DetHeight BSTreeNode) {
    if (BSTreeNode == null)
      return -1;
    else {
      /* compute the depth of each subBSTree */
      int LeftHeight = MaximumHeight(BSTreeNode.BSTreeNodeLeft);
      int Rightheight = MaximumHeight(BSTreeNode.BSTreeNoderight);

      /* use the larger one */
      if (LeftHeight > Rightheight)
        return (LeftHeight + 1);
      else
        return (Rightheight + 1);
    }
  }
  /* Driver program to test above functions */
  public static void main(String[] args) {
    BST BSTree = new BST();
    BSTree.BSTreeroot = new DetHeight(12);
    BSTree.BSTreeroot.BSTreeNodeLeft = new DetHeight(25);
    BSTree.BSTreeroot.BSTreeNoderight = new DetHeight(35);
    BSTree.BSTreeroot.BSTreeNodeLeft.BSTreeNodeLeft = new DetHeight(47);
    BSTree.BSTreeroot.BSTreeNodeLeft.BSTreeNoderight = new DetHeight(26);
    BSTree.BSTreeroot.BSTreeNoderight.BSTreeNodeLeft = new DetHeight(29);
    BSTree.BSTreeroot.BSTreeNoderight.BSTreeNoderight = new DetHeight(53);
    BSTree.BSTreeroot.BSTreeNoderight.BSTreeNodeLeft.BSTreeNoderight = new DetHeight(31);
    System.out.println("Height of BSTree is : " + BSTree.MaximumHeight(BSTree.BSTreeroot));
  }
}

Ausgang:

The height of this tree : 3

Komplexität des Suchprogramms

In diesem speziellen Fall ist es linear, da wir alle Knoten des Binärbaums unter Beibehaltung der Höhe rekursiv durchlaufen. Daher ist die Zeitkomplexität O(N), wobei N die Anzahl der Knoten im Baum ist.