Maison > Article > interface Web > Explication détaillée des étapes de déduplication et d'optimisation pour la construction d'un tableau d'arbres binaires à l'aide de js
Cette fois, je vais vous donner une explication détaillée des étapes de déduplication et d'optimisation pour la construction d'un tableau d'arbres binaires avec js. Quelles sont les précautions pour construire un tableau d'arbres binaires avec js pour la déduplication et l'optimisation ? Voici des cas pratiques, jetons un oeil.
Avant-propos
Cet article présente principalement le contenu pertinent sur la construction d'un arbre binaire avec js pour dédupliquer et optimiser des tableaux numériques. Il est partagé pour. votre référence. Learning, je n'en dirai pas plus ci-dessous, jetons un œil à l'introduction détaillée.
Boucle commune à deux couches pour implémenter la déduplication de tableau
let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2] let newArr = [] for (let i = 0; i < arr.length; i++) { let unique = true for (let j = 0; j < newArr.length; j++) { if (newArr[j] === arr[i]) { unique = false break } } if (unique) { newArr.push(arr[i]) } } console.log(newArr)
Créer une arborescence binaire pour réaliser la déduplication ( applicable uniquement à Un tableau de type numérique )
Construire les éléments précédemment parcourus dans un arbre binaire Chaque nœud de l'arbre satisfait : la valeur de l'enfant de gauche. node< ; La valeur du nœud actuel< La valeur du nœud enfant droit
Cela optimise le processus de jugement si l'élément est apparu auparavant
Si l'élément est plus grand que le nœud actuel, il vous suffit de juger si l'élément Il doit uniquement apparaître dans le sous-arbre droit du nœud
Si l'élément est plus petit que le nœud actuel, il vous suffit de déterminer si l'élément est apparu dans le sous-arbre gauche du nœud
let arr = [0, 1, 2, 2, 5, 7, 11, 7, 6, 4,5, 2, 2] class Node { constructor(value) { this.value = value this.left = null this.right = null } } class BinaryTree { constructor() { this.root = null this.arr = [] } insert(value) { let node = new Node(value) if (!this.root) { this.root = node this.arr.push(value) return this.arr } let current = this.root while (true) { if (value > current.value) { if (current.right) { current = current.right } else { current.right = node this.arr.push(value) break } } if (value < current.value) { if (current.left) { current = current.left } else { current.left = node this.arr.push(value) break } } if (value === current.value) { break } } return this.arr } } let binaryTree = new BinaryTree() for (let i = 0; i < arr.length; i++) { binaryTree.insert(arr[i]) } console.log(binaryTree.arr)
Idée d'optimisation un, enregistrer les valeurs maximales et minimales
Enregistrer les valeurs maximales et minimales des éléments insérés S'il est plus grand que le plus grand élément ou si le plus petit élément est plus petit, alors insérez directement
let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2] class Node { constructor(value) { this.value = value this.left = null this.right = null } } class BinaryTree { constructor() { this.root = null this.arr = [] this.max = null this.min = null } insert(value) { let node = new Node(value) if (!this.root) { this.root = node this.arr.push(value) this.max = value this.min = value return this.arr } if (value > this.max) { this.arr.push(value) this.max = value this.findMax().right = node return this.arr } if (value < this.min) { this.arr.push(value) this.min = value this.findMin().left = node return this.arr } let current = this.root while (true) { if (value > current.value) { if (current.right) { current = current.right } else { current.right = node this.arr.push(value) break } } if (value < current.value) { if (current.left) { current = current.left } else { current.left = node this.arr.push(value) break } } if (value === current.value) { break } } return this.arr } findMax() { let current = this.root while (current.right) { current = current.right } return current } findMin() { let current = this.root while (current.left) { current = current.left } return current } } let binaryTree = new BinaryTree() for (let i = 0; i < arr.length; i++) { binaryTree.insert(arr[i]) } console.log(binaryTree.arr)
Idée d'optimisation deux, construisez un arbre rouge-noir <🎜. >
Construisez un arbre rouge-noir, équilibrez la hauteur de l'arbre Pour la partie sur les arbres rouge-noir, veuillez voir l'insertion des arbres rouge-noirlet arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2] console.log(Array.from(new Set(arr))) class Node { constructor(value) { this.value = value this.left = null this.right = null this.parent = null this.color = 'red' } } class RedBlackTree { constructor() { this.root = null this.arr = [] } insert(value) { let node = new Node(value) if (!this.root) { node.color = 'black' this.root = node this.arr.push(value) return this } let cur = this.root let inserted = false while (true) { if (value > cur.value) { if (cur.right) { cur = cur.right } else { cur.right = node this.arr.push(value) node.parent = cur inserted = true break } } if (value < cur.value) { if (cur.left) { cur = cur.left } else { cur.left = node this.arr.push(value) node.parent = cur inserted = true break } } if (value === cur.value) { break } } // 调整树的结构 if(inserted){ this.fixTree(node) } return this } fixTree(node) { if (!node.parent) { node.color = 'black' this.root = node return } if (node.parent.color === 'black') { return } let son = node let father = node.parent let grandFather = father.parent let directionFtoG = father === grandFather.left ? 'left' : 'right' let uncle = grandFather[directionFtoG === 'left' ? 'right' : 'left'] let directionStoF = son === father.left ? 'left' : 'right' if (!uncle || uncle.color === 'black') { if (directionFtoG === directionStoF) { if (grandFather.parent) { grandFather.parent[grandFather.parent.left === grandFather ? 'left' : 'right'] = father father.parent = grandFather.parent } else { this.root = father father.parent = null } father.color = 'black' grandFather.color = 'red' father[father.left === son ? 'right' : 'left'] && (father[father.left === son ? 'right' : 'left'].parent = grandFather) grandFather[grandFather.left === father ? 'left' : 'right'] = father[father.left === son ? 'right' : 'left'] father[father.left === son ? 'right' : 'left'] = grandFather grandFather.parent = father return } else { grandFather[directionFtoG] = son son.parent = grandFather son[directionFtoG] && (son[directionFtoG].parent = father) father[directionStoF] = son[directionFtoG] father.parent = son son[directionFtoG] = father this.fixTree(father) } } else { father.color = 'black' uncle.color = 'black' grandFather.color = 'red' this.fixTree(grandFather) } } } let redBlackTree = new RedBlackTree() for (let i = 0; i < arr.length; i++) { redBlackTree.insert(arr[i]) } console.log(redBlackTree.arr)
Autres méthodes de déduplication
Déduplication d'objet Pass Set
[...new Set(arr)]Déduplication via le
+ sort()
méthodereduce()
renvoie 0 par défaut ; dans réduire(), une comparaison congruente est effectuée compare(2, '2')
let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2] let newArr = [] arr.sort((a, b) => { let res = a - b if (res !== 0) { return res } else { if (a === b) { return 0 } else { if (typeof a === 'number') { return -1 } else { return 1 } } } }).reduce((pre, cur) => { if (pre !== cur) { newArr.push(cur) return cur } return pre }, null)via
<a href="http://www.php.cn/wiki/137.html" target="_blank">include<p style="text-align: left;">s() </p></a>
+ <a href="http://www.php.cn/wiki/137.html" target="_blank">include</a>s()
Méthode pour supprimer les doublonsmap()
let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2] let newArr = [] arr.map(a => !newArr.includes(a) && newArr.push(a))Déduplication via la méthode
+ includes()
reduce()
let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2] let newArr = arr.reduce((pre, cur) => { !pre.includes(cur) && pre.push(cur) return pre }, [])Déduplication via la paire clé-valeur de l'objet + méthode objet JSON
let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2] let obj = {} arr.map(a => { if(!obj[JSON.stringify(a)]){ obj[JSON.stringify(a)] = 1 } }) console.log(Object.keys(obj).map(a => JSON.parse(a)))Je pense que vous l'avez maîtrisé après avoir lu le cas dans cet article Méthode, pour des informations plus intéressantes, veuillez faire attention vers d'autres articles connexes sur le site Web php chinois ! Lecture recommandée :
L'applet WeChat partage la page et revient à la page d'accueil
ElTableColumn ajoute une fonction de résumé de recherche
jQuery ajoute automatiquement des points de suspension lorsque le texte saisi dépasse le nombre de lignes spécifié
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!