Beispielcode für den binären Suchbaum des Javascript-Algorithmus

Dieser Artikel stellt hauptsächlich den Beispielcode des Javascript-Algorithmus vor. Er hat bestimmte Referenzen und ist für das Erlernen von JavaScript von Nutzen >

Was ist ein Binärbaum?

Ein Binärbaum bedeutet, dass jeder Knoten des Baums höchstens zwei untergeordnete Knoten haben kann.

Was ist? ein binärer Suchbaum

Basierend auf dem Binärbaum hat der binäre Suchbaum eine zusätzliche Bedingung, nämlich beim Einfügen eines Werts in den Binärbaum, wenn der eingefügte Wert kleiner als der aktuelle Knoten ist , wird es in den linken Knoten eingefügt, andernfalls wird es in den rechten Knoten eingefügt. Wenn während des Einfügevorgangs der linke Knoten oder der rechte Knoten bereits vorhanden ist, fahren Sie mit dem Vergleich gemäß den oben genannten Regeln fort, bis ein neuer Knoten gefunden wird.

Eigenschaften binärer Suchbäume

Aufgrund seiner einzigartigen Datenstruktur hat der binäre Suchbaum eine zeitliche Komplexität von O, unabhängig davon, ob er hinzufügt, löscht oder sucht (. h), h ist die Höhe des Binärbaums. Daher sollte der Binärbaum so kurz wie möglich sein, dh der linke und der rechte Knoten sollten so ausgeglichen wie möglich sein.

Konstruktion eines binären Suchbaums

Um einen binären Suchbaum zu erstellen, müssen Sie zunächst die Knotenklasse des Binärbaums erstellen. Aus den Eigenschaften von Binärbäumen ist ersichtlich, dass jede Knotenklasse einen linken Knoten, einen rechten Knoten und den Wert selbst hat. Die Knotenklassen lauten also wie folgt:

class Node {
 constructor(key) {
  this.key = key;
  this.left = null;
  this.right = null;
 }
}

Erstellen Sie dann einen binären Suchbaum

class Tree{
 constructor(param = null) {
  if (param) {
   this.root = new Node(param);
  } else {
   this.root = null;
  }
 }
}

Hier ist this.root der Baum des aktuellen

Objekts .

Das des binären Suchbaums wurde neu hinzugefügt

Der linke Teilbaum des binären Suchbaums ist kleiner als der Knoten und der rechte Wenn der Teilbaum größer als der Knoten ist, können Sie den Algorithmus zum Hinzufügen eines neuen binären Suchbaums einfach wie folgt schreiben:

insert(key) {
 if (this.root === null) {
  this.root = new Node(key);
 } else {
  this._insertNode(this.root, key);
 }
}
_insertNode(node, key) {
 if (key < node.key) {
  if (node.left === null) {
   node.left = new Node(key);{1}
  } else {
   this._insertNode(node.left, key);{2}
  }
 } else if (key > node.key) {
  if (node.right === null) {
   node.right = new Node(key);{3}
  } else {
   this._insertNode(node.right, key);{4}
  }
 }
}

Der obige Code bestimmt zunächst die Größe des neuen Schlüssels und den Schlüssel von Wenn er klein ist, durchläuft er rekursiv die linken untergeordneten Knoten, bis ein linker untergeordneter Nullknoten gefunden wird. Das Gleiche gilt, wenn er größer als der aktuelle Knoten ist. Der Grund, warum der obige Code {1}{2}{3}{4} den Wert von this.root ändern kann, liegt darin, dass die JavaScript-Funktion als Wert übergeben wird und wenn der Parameter ein nicht grundlegender Typ ist, wie z Objekt hier, der Wert des Objekts ist Speicher, daher wird der Inhalt von this.root jedes Mal direkt geändert.

Durchquerung des binären Suchbaums

Binäre Suchbäume sind in drei Durchquerungsmethoden unterteilt: Vorbestellung, Mittelbestellung und Nachbestellung.

inOrderTraverse(callback) {
 this._inOrderTraverse(this.root, callback);
}
_inOrderTraverse(node, callback) {
 if (node) {
  this._inOrderTraverse(node.left, callback);
  callback(node.key);
  this._inOrderTraverse(node.right, callback);
 }
}

Das Obige ist eine Durchquerung in der richtigen Reihenfolge.

Das, was hier verstanden werden muss, ist Rekursion. Sie wissen, dass die Ausführung einer Funktion in einer Datenstruktur – einem Stapel – abstrahiert werden kann. Für die Ausführung der Funktion wird ein Stapel verwaltet, um die Ausführung der Funktion zu speichern. Bei jeder Rekursion der Funktion wird die aktuelle Ausführungsumgebung auf den Stapel verschoben und der Ausführungsort aufgezeichnet. Am Beispiel des obigen Codes gibt es die folgenden Daten:

Es beginnt bei 11, führt {1} auf dem Stapel aus, gibt dann 7 ein, führt dann {1} auf dem Stapel aus und geht dann Führen Sie bei 5 {1} aus, um den Stapel einzufügen, und führen Sie dann bei 3 {1} aus, um ihn in den Stapel zu verschieben. Zu diesem Zeitpunkt wird festgestellt, dass der linke untergeordnete Knoten von Knoten 3 null ist, sodass er angezeigt wird . Zu diesem Zeitpunkt wird die Ausführungsumgebung von Knoten 3 angezeigt. Führen Sie {2} und {3} aus. Der rechte untergeordnete Knoten von ist ebenfalls null. Dann ist die rekursive Ausführung von Knoten 5 abgeschlossen up und {2}{3} wird ausgeführt. Dann wird 7 angezeigt und {2}{3} auf den Stapel geschoben. Wenn {3} ausgeführt wird, wird festgestellt, dass Knoten 7 einen rechten Knoten hat, also fahren wir fort Um {1} auszuführen, gehen Sie zu Knoten 8 und führen Sie dann {1} aus. Nachdem {1} ausgeführt wurde, wird {2}{3} ausgeführt und so weiter.

Der Unterschied zwischen Vorbestellung und Mittelbestellung besteht darin, dass zuerst auf den Knoten selbst zugegriffen wird, dh die Ausführungsreihenfolge des Codes ist 2 1 3.

Dasselbe gilt für die Nachbestellung, die Ausführungsreihenfolge ist 1 3 2

Es ist nicht schwer zu finden, dass es egal ist, ob vorne, in der Mitte oder nach- In dieser Reihenfolge wird immer zuerst der linke Knoten rekursiert, und wenn der linke Knoten nach Abschluss der Durchquerung den Stapel öffnet und die Knoten durchläuft. Der einzige Unterschied zwischen ihnen besteht im Zeitpunkt des Zugriffs auf den Knoten selbst.

Binäre Suchbaumsuche

Die Suche ist sehr einfach und basiert auf dem Prinzip, dass der linke untergeordnete Knoten kleiner ist als der rechte Der untergeordnete Knoten ist größer als der Knoten Can.

search(value) {
 if (this.root) {
  if (value === this.root.key) {
   return true;
  } else {
   return this._searchNode(value, this.root);
  }
 }
 throw new Error('this.root 不存在');
}
_searchNode(value, node) {
 if (!node) {
  return false;
 }
 if (value === node.key) {
  return true;
 }
 if (value > node.key) {
  return this._searchNode(value, node.right);
 } else if (value < node.key) {
  return this._searchNode(value, node.left);
 }
}

Löschen des binären Suchbaums

Das Löschen ist komplizierter und muss je nach Situation beurteilt werden

Zuerst feststellen ob der Knoten Wenn es einen linken Teilbaum gibt, ersetzen Sie den gelöschten Knoten direkt durch den Wurzelknoten des rechten Teilbaums.

Wenn ja, ersetzen Sie den gelöschten Knoten durch der kleinste Knoten des rechten Teilbaums ;

remove(key) {
 this._removeNode(this.root, key);
}
_removeNode(node, value) {
 if (!node) {
  return null;
 }
 if (value > node.key) {
  node.right = this._removeNode(node.right, value);
 } else if (value < node.key) {
  node.left = this._removeNode(node.left, value);
 } else {
  // 如果没有左子树，那么将右子树根节点作为替换节点
  if (!node.left) {
   return node.right;
   // 如果存在左子树，那么取右子树最小节点作为替换节点
  } else if (node.left) {
   return this._minNode(node.right);
  }
 }
}

Zusammenfassung

Im Allgemeinen habe ich durch dieses einfache Studium binärer Suchbäume wieder etwas über Rekursion gelernt sind nur einige einfache theoretische Konzepte. Diese tiefgreifende Praxis hat mein Verständnis der Rekursion erheblich vertieft.

Das erinnert mich an das Studium der Mathematik. Die theoretischen Formeln der Mathematik sind leicht zu merken und zu beherrschen. Wenn die volle Punktzahl für das Beherrschen eines Wissenspunktes zehn Punkte beträgt, dann gilt, bis man es tatsächlich übt. Sie können nur 2 Punkte erhalten, wenn Sie nur auf die Beherrschung der Formel achten, denn die Formel ist sehr einfach, nur ein paar Sätze und ein paar Prinzipien, aber die auftretenden Probleme ändern sich ständig. Nur wenn Sie die Theorie wirklich in die Praxis umsetzen und wenn wir es durch verschiedene Praktiken verfeinern, können wir das Geheimnis dahinter wirklich verstehen.

Verwandte Empfehlungen:

Erklären Sie die Unterschiede zwischen drei Methoden zur Kapselung der JavaScript-Simulationsimplementierung und ihrer Schreibweise

Detaillierte Erläuterung der selbstausführenden JavaScript-Funktionen und jQuery-Erweiterungsmethoden

Erklärung der Require call js-Beispiele in JavaScript

Das obige ist der detaillierte Inhalt vonBeispielcode für den binären Suchbaum des Javascript-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!