ホームページ > 記事 > ウェブフロントエンド > js を使用してバイナリ ツリー配列を構築するための重複排除と最適化の手順の詳細な説明
js を使用してバイナリ ツリー配列を構築するための重複排除と最適化の手順の詳細な説明
- php中世界最好的语言オリジナル
- 2018-05-03 11:09:061301ブラウズ
今回は、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)
赤黒ツリーを構築し、ツリーの高さのバランスを取ります赤黒ツリーの場合部分については、赤黒ツリーの挿入を参照してください
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 = '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)sort() + を使用します重複を削除するには、reduce() メソッドを使用します並べ替えた後、隣接する要素を比較して、それらが同じかどうかを確認し、異なる場合は、返された配列に追加します
並べ替えるときに、 を使用することに注意してください。 >compare(2, '2') はデフォルトで 0 を返しますが、reduce() では、<a href="http ://www.php.cn/ を通じて一致比較が実行されます <p style="text-align: left;"><pre class="brush:php;toolbar:false">[...new Set(arr)]</pre><code>sort() + reduce() 方法去重排序后比较相邻元素是否相同，若不同则添加至返回的数组中
值得注意的是，排序的时候，默认 compare(2, '2') 返回 0；而 reduce() 时，进行全等比较
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)
通过 <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
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 サイトの他の関連記事を参照してください。