Detailed explanation of deduplication and optimization steps for constructing a binary tree array using js

This time I will bring you a detailed explanation of the deduplication and optimization steps for constructing a binary tree array with js. What are the precautions for deduplication and optimization of a binary tree array with js? The following is a practical case, let’s take a look.

Preface

This article mainly introduces the relevant content about constructing a binary tree with js to deduplicate and optimize numerical arrays. It is shared for your reference. Learning, I won’t say much more below, let’s take a look at the detailed introduction.

Common two-layer loop to implement array deduplication

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 <p style="text-align: left;"><span style="color: #ff0000">Build a binary tree to achieve deduplication (only applicable to <strong>Array of numerical type<a href="http://www.php.cn/wiki/994.html" target="_blank">)</a></strong></span></p> Construct the previously traversed elements into a binary tree. Each node in the tree satisfies: the value of the left child nodeThis optimizes the process of judging whether the element has appeared before<p style="text-align: left;"></p>If the element is larger than the current node, you only need to judge whether the element is in the node. It just has to appear in the right subtree of the node<p style="text-align: left;"></p>If the element is smaller than the current node, you only need to determine whether the element has appeared in the left subtree of the node<p style="text-align: left;"></p><pre class="brush:php;toolbar:false">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 <p style="text-align: left;"><span style="color: #ff0000">Optimization idea one, record the maximum and minimum values<strong></strong></span></p>Record the maximum and minimum values ​​of the inserted elements. If it is larger than the largest element or the smallest element is smaller, insert it directly<p style="text-align: left;"> </p><pre class="brush:php;toolbar:false">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  current.value) {
    if (current.right) {
     current = current.right
    } else {
     current.right = node
     this.arr.push(value)
     break
    }
   }
   if (value <p style="text-align: left;"><span style="color: #ff0000">Optimization idea two, build a red-black tree<strong></strong></span></p>Build a red-black tree and balance the height of the tree<p style="text-align: left;"></p>About the red-black tree Part, please see red-black tree insertion<p style="text-align: left;"></p><pre class="brush:php;toolbar:false">let 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 <p style="text-align: left;"><span style="color: #ff0000">Other deduplication methods<strong></strong></span></p><p style="text-align: left;">Deduplication through Set object<strong></strong></p><pre class="brush:php;toolbar:false">[...new Set(arr)]

Through

sort() reduce() Method to remove duplicates

After sorting, compare adjacent elements to see if they are the same. If they are different, add them to the returned

It is worth noting that in the array, when sorting, the default

compare(2, '2') returns 0; and when reduce(), congruent comparison is performed

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)

By

include<a href="http://www.php.cn/wiki/137.html" target="_blank">s() </a> map() Method to remove duplicates

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

By

includes() reduce() Method to remove duplication

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
}, [])

Pair JSON object method through object key value

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

I believe you have mastered the method after reading the case in this article, please come for more exciting information Pay attention to other related articles on php Chinese website!

Recommended reading:

WeChat applet shares the page and jumps back to the homepage

ElTableColumn adds search summary function

jQuery automatically adds ellipses when the input text exceeds the specified number of lines

The above is the detailed content of Detailed explanation of deduplication and optimization steps for constructing a binary tree array using js. For more information, please follow other related articles on the PHP Chinese website!