Detaillierte Erläuterung der Verwendung des binären JS-Suchbaums

Dieses Mal erkläre ich Ihnen ausführlich die Verwendung des JS-Binärsuchbaums . Was sind die Vorsichtsmaßnahmen bei der Verwendung des JS-Binärsuchbaums? Das Folgende sind praktische Fälle, einer Stehen Sie auf und schauen Sie nach.

Was ist ein Binärbaum?

Ein binärer Baum bedeutet, dass jeder Knoten des Baums höchstens zwei untergeordnete Knoten haben kann

Was ist ein binärer Suchbaum?

Basierend auf dem Binärbaum verfügt der binäre Suchbaum über eine zusätzliche Bedingung: Wenn beim Einfügen eines Werts in den Binärbaum der eingefügte Wert kleiner als der aktuelle Knoten ist, wird er in den linken Knoten eingefügt Es wird 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 Zeitkomplexität von O(h), unabhängig davon, ob er hinzufügt, löscht oder sucht. 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.

Aufbau 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, sodass die Knotenklassen wie folgt lauten:

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 .

Binäre Suchbäumeneu hinzugefügt

Aufgrund der Eigenschaften des binären Suchbaums, dass der linke Teilbaum kleiner als der Knoten und der rechte Teilbaum größer als der Knoten ist, kann der neue Algorithmus für den binären Suchbaum einfach wie folgt geschrieben werden:

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 neu hinzugefügten Schlüssels und den Schlüssel des aktuellen Knotens. Wenn er kleiner ist, durchläuft er rekursiv den linken untergeordneten Knoten, bis er einen leeren linken untergeordneten Knoten findet. Es gilt das gleiche Prinzip. Der Grund, warum der obige Code {1}{2}{3}{4} den Wert von this.root ändern kann, liegt darin, dass die Funktion

JavaScript als Wert übergeben wird und wenn der Parameter kein Wert ist. Grundtyp, wie hier Objekt, der Wert seines Objekts ist Speicher, sodass der Inhalt von this.root jedes Mal direkt geändert wird.

Durchquerung des binären Suchbaums

Binäre Suchbäume sind in drei Durchlaufmethoden unterteilt: Preorder, Inorder und Postorder.

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.

Hier gilt es Rekursion zu verstehen. 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, geht dann zu 7, führt dann {1} auf dem Stapel aus, geht dann zu 5, führt {1} auf dem Stapel aus und geht dann zu 3, führt {1 aus } zum Stapel. Zu diesem Zeitpunkt wird festgestellt, dass der linke untergeordnete Knoten von Knoten 3 null ist. Zu diesem Zeitpunkt wird die Ausführungsumgebung von Knoten 3 angezeigt. Führen Sie {2} aus. {3} und stellen Sie fest, dass der rechte untergeordnete Knoten von 3 ebenfalls null ist und die rekursive Ausführung von {3} abgeschlossen ist. Öffnen Sie dann Knoten 5, führen Sie {2}{3} aus und rufen Sie dann Knoten 7 auf {2}{3} auf den Stapel. Bei der Ausführung von {3} wird festgestellt, dass Knoten 7 einen rechten Knoten hat. Führen Sie also weiterhin {1} aus, bis Knoten 8, und führen Sie {1} erneut aus. 8 hat kein linkes Kind Knoten, {1} wird ausgeführt, {2}{3} wird ausgeführt und so weiter.

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

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

Es ist nicht schwer herauszufinden, dass unabhängig von der Reihenfolge vorher, während oder nachher der linke Knoten immer zuerst rekursiv ist. Wenn der linke Knoten durchlaufen wird, wird der Stapel entfernt und alle Knoten werden durchlaufen. Der einzige Unterschied zwischen ihnen besteht im Zeitpunkt des Zugriffs auf den Knoten selbst.

Binäre Suchbaumsuche

Die Suche ist sehr einfach. Führen Sie einfach eine Schleifenbeurteilung durch, die auf dem Prinzip basiert, dass der linke untergeordnete Knoten kleiner als der Knoten und der rechte untergeordnete Knoten größer als der Knoten ist.

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öschung des binären Suchbaums

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

Stellen Sie zunächst fest, ob der Knoten einen linken Teilbaum hat. Ersetzen Sie den gelöschten Knoten direkt durch den Wurzelknoten des rechten Teilbaums Wenn ja, ersetzen Sie den gelöschten Knoten durch den kleinsten 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);
  }
 }
}

总结

总的来说，通过这次简单的二叉搜索树的学习，让我重新认识了递归，以前对于递归的理解只是一些简单的理论概念，这次深入实践让我对递归的理解又加深了许多。

这让我想到了数学的学习，数学的理论公式是很容易记住掌握的，如果说对一个知识点的掌握满分是十分，那么直到真正去实践它之前，只看公式的掌握只能是2分，因为公式很简单，就几句话几个原则，但是遇到的问题是千变万化的，只有真正将理论付诸实践，经过各种实践的打磨蹂躏，才能真正理解它其中的奥秘。          

相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！

推荐阅读：

react-native-fs插件使用案列详解

js实现字符限制中文汉字=两个字符

优化页面加载速度插件InstantClick

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Verwendung des binären JS-Suchbaums. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!