Exemple de code d'arbre de recherche binaire d'algorithme javascript

Cet article présente principalement l'exemple de code de l'arbre de recherche binaire de l'algorithme javascript. Il a certaines références et valeurs pour l'apprentissage de JavaScript. Les amis intéressés par JavaScript peuvent se référer à cet article. >

Qu'est-ce qu'un arbre binaire

Un arbre binaire signifie que chaque nœud de l'arbre ne peut avoir qu'au plus deux nœuds enfants

Qu'est-ce que un arbre de recherche binaire

Basé sur l'arbre binaire, l'arbre de recherche binaire a une condition supplémentaire, c'est-à-dire 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 , il est inséré dans le nœud gauche, sinon il est inséré dans le nœud droit ; Si pendant le processus d'insertion, le nœud gauche ou 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, qu'il s'agisse d'ajout, de suppression ou de recherche (. h), 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;
 }
}

Ensuite, construisez un arbre de recherche binaire

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

Ici this.root est l'arborescence de l'objet

actuel .

Le de l'arbre de recherche binaire est nouvellement ajouté

Le sous-arbre gauche de l'arbre de recherche binaire est plus petit que le nœud, et le sous-arbre droit Le sous-arbre est plus grand que le nœud Fonctionnalités, vous pouvez facilement écrire l'algorithme pour ajouter un nouvel arbre de recherche binaire, 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}
  }
 }
}

Le code ci-dessus détermine d'abord la taille de la nouvelle clé et la clé de. le nœud actuel. S'il est petit, il traverse récursivement les nœuds enfants gauches jusqu'à ce qu'un nœud enfant gauche nul soit trouvé ; la même chose s'applique s'il est supérieur au nœud actuel. La raison pour laquelle le code ci-dessus {1}{2}{3}{4} peut modifier la valeur de this.root est que la fonction JavaScript est passée par valeur et que lorsque le paramètre est un type non basique, tel que object ici, la valeur de l'objet est la mémoire, donc le contenu de this.root sera directement modifié à chaque fois.

Parcours d'arbre de recherche binaire

Les arbres de recherche binaires sont divisés en trois méthodes de parcours : pré-commande, mi-commande et post-commande.

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

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

La chose qu'il faut 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 à partir de 11, exécutera {1} sur la pile, puis entrera 7, puis exécutera {1} sur la pile, puis ira. à 5, exécutez {1} pour insérer la pile, puis à 3, exécutez {1} pour pousser dans la pile. À ce moment, on constate que le nœud enfant gauche du nœud 3 est nul, il commence donc à apparaître. .À ce moment, l'environnement d'exécution du nœud 3 apparaît, exécutez {2}, {3} et trouvez 3 Le nœud enfant droit de est également nul, l'exécution récursive de {3} est terminée, puis le nœud 5 apparaît. , exécutez {2}{3}, puis faites apparaître 7, exécutez {2}{3} et poussez-le sur la pile, lorsque {3} est exécuté, il s'avère que le nœud 7 a un nœud droit, nous continuons donc à exécutez {1}, accédez au nœud 8, puis exécutez {1} n'a plus de nœud enfant gauche. Après l'exécution de {1}, {2}{3} est exécuté, et ainsi de suite.

La différence entre la précommande et la commande intermédiaire est qu'il accède d'abord au nœud lui-même, c'est-à-dire que l'ordre d'exécution du code est 2 1 3.

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

Il n'est pas difficile de constater que peu importe la précommande, le milieu ou après la commande, le nœud gauche est toujours récursif en premier, et lorsque le nœud gauche lorsque le parcours est terminé, ouvrez la pile et parcourez les nœuds. La seule différence entre eux est le moment d’accès au nœud lui-même.

Recherche dans l'arbre de recherche binaire

La recherche est très simple. Le jugement de boucle est effectué sur la base du principe selon lequel le nœud enfant gauche est plus petit que le nœud et le nœud droit. Le nœud enfant est plus grand que le nœud 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);
 }
}

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 S'il y 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

S'il y en a, remplacez le nœud supprimé par ; le plus petit nœud du sous-arbre droit ;

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

Résumé

En général, grâce à cette simple étude des arbres de recherche binaires, j'ai réappris ma compréhension. ne sont que quelques concepts théoriques simples. Cette pratique approfondie a beaucoup approfondi ma compréhension de la récursivité.

Cela me rappelle l'étude des mathématiques. Les formules théoriques des mathématiques sont faciles à retenir et à maîtriser. Si le score total pour maîtriser un point de connaissance est de dix points, alors jusqu'à ce que vous le pratiquiez réellement, Le simple fait de regarder la maîtrise de la formule ne peut vous donner que 2 points, car la formule est très simple, juste quelques phrases et quelques principes, mais les problèmes rencontrés sont en constante évolution Seulement en mettant réellement la théorie en pratique et en la peaufinant. à travers diverses pratiques, pouvons-nous vraiment en comprendre le mystère.

Recommandations associées :

Partage des différences entre trois méthodes d'encapsulation d'implémentation de simulation JavaScript et leur écriture

Explication détaillée des fonctions auto-exécutables JavaScript et des méthodes d'extension jQuery

Explication des exemples d'appels Require js en JavaScript

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!