Explication détaillée de l'utilisation de l'arbre de recherche binaire JS-js tutoriel-php.cn

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 enfants

Qu'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;
 }
}

Copier après la connexion

Construisez ensuite un arbre de recherche binaire

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

Copier après la connexion

Ici this.root est l'arborescence de l'

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}
  }
 }
}

Copier après la connexion

Le code ci-dessus détermine d'abord la taille de la clé nouvellement ajoutée et la clé du nœud actuel si elle est plus petite, il parcourt récursivement le nœud enfant gauche jusqu'à ce qu'il trouve un nœud enfant gauche nul s'il est plus grand que le nœud actuel ; le même principe s’applique. La raison pour laquelle le code ci-dessus {1}{2}{3}{4} peut changer la valeur de this.root est que la fonction

JavaScript est passée par valeur, et lorsque le paramètre est un non- type de base, comme ici Object, la valeur de son objet est la mémoire, donc le contenu de this.root sera directement modifié à chaque fois.

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);
 }
}

Copier après la connexion

Ce qui précède est un parcours dans l’ordre.

La chose à comprendre ici est la récursivité. Vous savez, l'exécution d'une fonction peut être résumée dans une structure de données - une pile. Pour l'exécution de la fonction, une pile est maintenue pour stocker l'exécution de la fonction. Chaque fois que la fonction réapparaît, elle poussera l'environnement d'exécution actuel sur la pile et enregistrera l'emplacement d'exécution. En prenant le code ci-dessus comme exemple, il y a les données suivantes

Il commencera à 11, exécutera {1} sur la pile, puis entrera 7, puis exécutera {1} sur la pile, puis passera à 5, exécutera {1} sur la pile, puis passera à 3, exécutera {1} à la pile. À ce moment, on constate que le nœud enfant gauche du nœud 3 est nul, il commence donc à sortir de la pile. À ce moment, l'environnement d'exécution du nœud 3 apparaît, exécutez {2}, {. 3}, et constatez que le nœud enfant droit de 3 est également nul et que l'exécution récursive de {3} est terminée, puis faites apparaître le nœud 5, exécutez {2}{3}, puis faites apparaître le nœud 7, exécutez {. 2}{3} sur la pile, lors de l'exécution de {3}, on constate que le nœud 7 a un nœud droit, continuez donc à exécuter {1}, jusqu'au nœud 8, exécutez à nouveau {1}, 8 n'a pas de nœud enfant gauche , {1} est exécuté, {2}{3} est exécuté, et ainsi de suite.

La différence entre la précommande et la commande intermédiaire est que le nœud lui-même est visité en premier, c'est-à-dire que l'ordre d'exécution du code est 2 1 3.

Il en va de même pour le post-ordre, l'ordre d'exécution est le 1 3 2

Il n'est pas difficile de constater que quel que soit l'ordre avant, pendant ou après, le nœud gauche est toujours récursif en premier. Lorsque le nœud gauche est traversé, la pile est sautée et tous les nœuds sont parcourus. La seule différence entre eux est le moment d’accès au nœud lui-même.

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);
 }
}

Copier après la connexion

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);
  }
 }
}

Copier après la connexion

总结

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

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

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