コミュニティ 学ぶ ツールライブラリ レジャー
検索
日本語
ホームページ > ウェブフロントエンド > jsチュートリアル > js を使用してバイナリ ツリー配列を構築するための重複排除と最適化の手順の詳細な説明

js を使用してバイナリ ツリー配列を構築するための重複排除と最適化の手順の詳細な説明

php中世界最好的语言
リリース： 2018-05-03 11:09:06
オリジナル
1372 人が閲覧しました

今回は、js でバイナリ ツリー配列を構築するための重複排除と最適化の手順について詳しく説明します。重複排除と最適化のために js でバイナリ ツリー配列を構築する場合の注意事項は何ですか? 、見てみましょう。

はじめに

この記事では主に、数値配列の重複排除と最適化を行うための js によるバイナリ ツリーの構築に関する関連内容を紹介します。以下では多くを述べません。詳細な紹介をご覧ください。

配列の重複排除を実装するための一般的な 2 層ループ

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)
ログイン後にコピー

重複排除を実現するためにバイナリ ツリーを構築します (数値型配列にのみ適用可能)

以前に走査した要素をバイナリ ツリーに構築します、ツリー内の各ノードは次の条件を満たします: 左のサブノードの値 < 現在のノードの値 < 右のサブノードの値

これにより、要素が以前に出現したかどうかを判断するプロセスが最適化されます

要素が現在のノードより大きい場合は、要素がノードの右側のサブツリーに出現したかどうかを判断するだけで済みます。要素が現在のノードよりも小さい場合は、要素が現在のノードよりも大きいかどうかを判断するだけで済みます。ノードの左側のサブツリーに要素が出現しました

最適化アイデア 1、最大値と最小値を記録します

最大の要素より大きい場合は、挿入された要素の最大値と最小値を記録します。または最小の要素の方が小さい場合は、直接挿入します

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)
ログイン後にコピー

最適化アイデア 2、赤黒ツリーを構築します

赤黒ツリーを構築し、ツリーの高さのバランスを取ります赤黒ツリーの場合部分については、赤黒ツリーの挿入を参照してください

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)
ログイン後にコピー

その他の重複排除方法

Set オブジェクトによる重複排除 

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 = &#39;red&#39;
 }
}
class RedBlackTree {
 constructor() {
  this.root = null
  this.arr = []
 }
 insert(value) {
  let node = new Node(value)
  if (!this.root) {
   node.color = &#39;black&#39;
   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 = &#39;black&#39;
   this.root = node
   return
  }
  if (node.parent.color === &#39;black&#39;) {
   return
  }
  let son = node
  let father = node.parent
  let grandFather = father.parent
  let directionFtoG = father === grandFather.left ? &#39;left&#39; : &#39;right&#39;
  let uncle = grandFather[directionFtoG === &#39;left&#39; ? &#39;right&#39; : &#39;left&#39;]
  let directionStoF = son === father.left ? &#39;left&#39; : &#39;right&#39;
  if (!uncle || uncle.color === &#39;black&#39;) {
   if (directionFtoG === directionStoF) {
    if (grandFather.parent) {
     grandFather.parent[grandFather.parent.left === grandFather ? &#39;left&#39; : &#39;right&#39;] = father
     father.parent = grandFather.parent
    } else {
     this.root = father
     father.parent = null
    }
    father.color = &#39;black&#39;
    grandFather.color = &#39;red&#39;
    father[father.left === son ? &#39;right&#39; : &#39;left&#39;] && (father[father.left === son ? &#39;right&#39; : &#39;left&#39;].parent = grandFather)
    grandFather[grandFather.left === father ? &#39;left&#39; : &#39;right&#39;] = father[father.left === son ? &#39;right&#39; : &#39;left&#39;]
    father[father.left === son ? &#39;right&#39; : &#39;left&#39;] = 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 = &#39;black&#39;
   uncle.color = &#39;black&#39;
   grandFather.color = &#39;red&#39;
   this.fixTree(grandFather)
  }
 }
}
let redBlackTree = new RedBlackTree()
for (let i = 0; i < arr.length; i++) {
 redBlackTree.insert(arr[i])
}
console.log(redBlackTree.arr)
ログイン後にコピー

sort() + を使用します重複を削除するには、reduce() メソッドを使用します

並べ替えた後、隣接する要素を比較して、それらが同じかどうかを確認し、異なる場合は、返された配列に追加します

並べ替えるときに、 を使用することに注意してください。 >compare(2, '2') はデフォルトで 0 を返しますが、reduce() では、<a href="http ://www.php.cn/ を通じて一致比較が実行されます <p style="text-align: left;"><div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">[...new Set(arr)]</pre><div class="contentsignin">ログイン後にコピー</div></div><code>sort() + reduce() 方法去重

排序后比较相邻元素是否相同，若不同则添加至返回的数组中

值得注意的是，排序的时候，默认 compare(2, &#39;2&#39;) 返回 0；而 reduce() 时，进行全等比较

let arr = [0, 1, 2, &#39;2&#39;, 2, 5, 7, 11, 7, 5, 2, &#39;2&#39;, 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)
ログイン後にコピー

通过 <a href="http://www.php.cn/wiki/137.html" target="_blank">include</a>s() + map() 方法去重

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))
ログイン後にコピー

通过 includes() + reduce() wiki/137.html" target="_blank">include

s() + map() includes() を通じて重複を削除するメソッド

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
}, [])
ログイン後にコピー
+ reduce() 重複を削除するメソッド

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)))
ログイン後にコピー
オブジェクトのキーと値のペア + JSON オブジェクトの重複を削除するメソッド

rrreee

この記事の事例を読んだ後は、この方法を習得したと思います。さらにエキサイティングなコンテンツについては、php 中国語 Web サイトの他の関連記事にご注目ください。

推奨読書:

WeChat アプレットはページを共有し、ホームページに戻ります


ElTableColumn は検索概要機能を追加します


jQuery は入力テキストが指定された行数を超えると自動的に省略記号を追加します🎜🎜 🎜

以上がjs を使用してバイナリ ツリー配列を構築するための重複排除と最適化の手順の詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

関連ラベル：
javascript ステップ 詳しい説明
ソース：php.cn
前の記事：Vue は、bass.scss 実装手順をグローバルに導入します 次の記事：赤黒ツリーをJSで操作する方法
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
著者別の最新記事
最新の問題
JavaScript を使用せずにクリック時に画像ソースを動的に変更する CSS のみのメソッド img:active{} のような CSS のみを使用して、マウスクリック時に画像の src を変更する必要があります
から 2024-04-06 19:25:49
0
1
505
d3.js でズームインすると散布図のポイントの値が維持されない d3.js を使用するのは初めてなので、ご容赦ください。 vue.js ファイルに純粋な JavaScript として実装しました。ズーム機能を使用して散布図を作成しようとしていま...
から 2024-04-06 18:16:26
0
1
403
ベンダー固有の疑似要素上の JavaScript ホバー イベント 次の htmlinput タグがあります。 $("input[type='range']::-webkit-slider-thumb").on('hover',...
から 2024-04-06 15:35:24
0
1
274
Javascript/Jqueryを使用してボタンなしでフォームを送信する JavaScript 関数を呼び出し、JQUERY/PHP を使用してフォームを実行することにより、ボタンのないフォームを送信しようとしています。ページを再読み込みせずに、バックエ...
から 2024-04-06 14:54:03
0
2
421
CollapseDisplay クラスを使用してブートストラップ アコーディオン ヘッダーの外観をカスタマイズする class Collapseshow を使用してパネルのカード タイトルのスタイルを設定したいと考えています。この例では、最初のパネルです。 CSS を使用して .accordio...
から 2024-04-06 12:53:11
0
1
376
関連トピック
詳細>
人気のおすすめ
人気のチュートリアル
詳細>
関連するチュートリアル
人気のおすすめ
最新のコース
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート