JavaScriptによる二分探索木
通常のツリー構造の問題は、それらが分類されておらず、操作が非常に扱いにくいことです。 コンピュータでファイルの検索を実行する場合、通常はかなり長い時間がかかります。これは、ファイルが並べ替えられておらず、結果を取得するためにすべてを検索する必要があるためです。 ツリーの値を整理する方法をアップグレードすることで、これを大幅に改善できます。
前提条件
ここで学習できるツリーの基本概念を理解する必要があります。また、幅優先探索を使用して非常に基本的なツリートラバーサルを実行する必要があります。これをブラッシュアップできます。 ここ。
コンセプト
二分木は単なる通常のツリーであり、各ノードは最大で2つの子しか持てないという制限があります。 二分探索木には、2つの値がある場合、それらを順序付ける必要があるという追加のルールがあります。この場合、左側の小さい数字から右側の大きい数字の順に並べます。
二分探索木での検索は、元の検索ツリーを大幅に改善したものです。 O(n)
今からの検索速度で何かを見つけるには、必要なものが得られるまで左または右に移動する前に、各親ノードと必要なものを比較する必要があります。 O(logn)
すべての操作に対して。
作成
リンクリストと非常によく似ており、クラスを使用してノードとツリーを生成できます。 各ノードには、実際には左/下および右/大きい側へのポインター、値のみが必要です。繰り返し値はツリーに1回しか存在できないため、個人的にはカウンターを追加するのが好きです。
すでに何かがあるかどうかを確認した後、ちょっとしたユーティリティ関数を使用して、値を脇に置くことができます。 非常に簡単に言えば、ツリーをループする必要があります。値が現在のノードよりも小さい場合は左に移動し、右に移動します。その位置に新しいノードが存在しない場合は、一致する値がすでに存在する場合は、その値をインクリメントできます。カウンター。
class Node {
constructor(val) {
this.val = val;
this.right = null;
this.left = null;
this.count = 0;
};
};
class BST {
constructor() {
this.root = null;
}
create(val) {
const newNode = new Node(val);
if (!this.root) {
this.root = newNode;
return this;
};
let current = this.root;
const addSide = side => {
if (!current[side]) {
current[side] = newNode;
return this;
};
current = current[side];
};
while (true) {
if (val === current.val) {
current.count++;
return this;
};
if (val < current.val) addSide('left');
else addSide('right');
};
};
};
let tree = new BST();
tree.add(10);
tree.add(4);
tree.add(4);
tree.add(12);
tree.add(2);
console.log(tree);
探す
何かを見つけるのは信じられないほど簡単です。現在の値に対して左または右に移動して戻るだけです。 true
一致するものをヒットした場合。
find(val) {
if (!this.root) return undefined;
let current = this.root,
found = false;
while (current && !found) {
if (val < current.val) current = current.left;
else if (val > current.val) current = current.right;
else found = true;
};
if (!found) return 'Nothing Found!';
return current;
};
消去
削除は、リーフだけで作業するのではなく、ノードのすべての子を再構築または「リバランス」する必要があるため、最も複雑な操作です。 ノードがリーフであるかどうか、およびノードに子があるかどうかを確認する必要がある2つの条件があります。
まず、削除されたノードのすべての子を収集するためのユーティリティ関数が必要です。 基本的な幅優先探索を使用してすべてを配列にプッシュし、ループして各アイテムをツリーに再度追加します。
通常の検索との唯一の違いは、別の開始点を受け入れる必要があることです。そのため、削除されたノードの子のサブツリーのみに検索を制限できます。
BFS(start) {
let data = [],
queue = [],
current = start ? this.find(start) : this.root;
queue.push(current);
while (queue.length) {
current = queue.shift();
data.push(current.val);
if (current.left) queue.push(current.left);
if (current.right) queue.push(current.right);
};
return data;
}
親に戻ることはできないため、変数を使用して親ノードを次の場所に格納します。 current
それを使って設定します current
に null
子供たちを救った後。
の deleteNode
ノードの子を収集し、その親に次のように設定します null
、次に使用する create
それぞれの子供たちに、ツリーで適切に再構築します。 子配列には、削除されたノードも含まれます。これは、スプライスアウトするだけです。
delete(val) {
if (!this.root) return undefined;
let current = this.root,
parent;
const pickSide = side => {
if (!current[side]) return 'No node found!';
parent = current;
current = current[side];
};
const deleteNode = side => {
if (current.val === val && current.count > 1) current.count--;
else if (current.val === val) {
const children = this.BFS(current.val);
parent[side] = null;
children.splice(0, 1);
children.forEach(child => this.create(child));
};
};
while (current.val !== val) {
if (val < current.val) {
pickSide('left');
deleteNode('left');
};
else {
pickSide('right');
deleteNode('right');
};
};
return current;
}
結論
これは完全なCRUD操作でした。更新は基本的に、1つのノードを削除し、別の場所にまったく新しいノードを作成するだけであり、実際には独自のメソッドを必要としません。
バイナリヒープと優先度キューに移動すると、バイナリ検索ツリーを使用してよりクールな処理を実行できるようになります。