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 kannWas 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;
}
}class Tree{
constructor(param = null) {
if (param) {
this.root = new Node(param);
} else {
this.root = null;
}
}
}-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}
}
}
}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);
}
}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 Teilbaumsremove(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中文网其它相关文章！
推荐阅读：
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!
