Cette fois, je vous apporte une explication détaillée de l'utilisation de l'arbre de recherche binaire JS, quelles sont les précautions lors de l'utilisation de l'arbre de recherche binaire JS, voici des cas pratiques, un Levez-vous et jetez un œil.
Qu'est-ce qu'un arbre binaire
Un arbre binaire signifie que chaque nœud de l'arbre ne peut avoir qu'un maximum de deux nœuds enfantsQu'est-ce qu'un arbre de recherche binaire
Sur la base de l'arbre binaire, l'arbre de recherche binaire a une condition supplémentaire, c'est-à-dire que lors de l'insertion d'une valeur dans l'arbre binaire, si la valeur insérée est plus petite que le nœud actuel, elle sera insérée dans le nœud gauche, sinon il sera inséré dans le nœud droit ; si pendant le processus d'insertion, le nœud gauche ou si le nœud droit existe déjà, continuez à comparer selon les règles ci-dessus jusqu'à ce qu'un nouveau nœud soit rencontré.Caractéristiques des arbres de recherche binaires
En raison de sa structure de données unique, l'arbre de recherche binaire a une complexité temporelle de O(h), qu'il s'agisse d'ajout, de suppression ou de recherche, h est la hauteur de l'arbre binaire. Par conséquent, l’arbre binaire doit être aussi court que possible, c’est-à-dire que les nœuds gauche et droit doivent être aussi équilibrés que possible.Construction d'un arbre de recherche binaire
Pour construire un arbre de recherche binaire, vous devez d'abord construire la classe de nœuds de l'arbre binaire. Il ressort des caractéristiques des arbres binaires que chaque classe de nœuds a un nœud gauche, un nœud droit et la valeur elle-même, donc les classes de nœuds sont les suivantes :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; } } }
objet actuel.
Arbre de recherche binaireNouveau
En raison des caractéristiques de l'arbre de recherche binaire selon lesquelles le sous-arbre de gauche est plus petit que le nœud et le sous-arbre de droite est plus grand que le nœud, le nouvel algorithme de l'arbre de recherche binaire peut être facilement écrit comme suit :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} } } }
Parcours de l'arbre de recherche binaire
Les arbres de recherche binaires sont divisés en trois méthodes de parcours : précommande, inordre et post-ordre.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); } }
Recherche dans l'arborescence de recherche binaire
La recherche est très simple, il suffit de faire un jugement de boucle basé sur le principe selon lequel le nœud enfant gauche est plus petit que le nœud et le nœud enfant droit est plus grand que le nœud.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); } }
Suppression de l'arbre de recherche binaire
La suppression est plus compliquée et doit être jugée en fonction de différentes situations Déterminez d'abord si le nœud a un sous-arbre gauche. S'il n'y a pas de sous-arbre gauche, remplacez directement le nœud supprimé par le nœud racine du sous-arbre droit ; Si tel est le cas, remplacez le nœud supprimé par le plus petit nœud du sous-arbre de droite;
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中文网其它相关文章!
推荐阅读:
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!