通常のツリー構造の問題は、それらが分類されておらず、操作が非常に扱いにくいことです。 コンピュータでファイルの検索を実行する場合、通常はかなり長い時間がかかります。これは、ファイルが並べ替えられておらず、結果を取得するためにすべてを検索する必要があるためです。 ツリーの値を整理する方法をアップグレードすることで、これを大幅に改善できます。

前提条件

ここで学習できるツリーの基本概念を理解する必要があります。また、幅優先探索を使用して非常に基本的なツリートラバーサルを実行する必要があります。これをブラッシュアップできます。 ここ

コンセプト

二分木は単なる通常のツリーであり、各ノードは最大で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 それを使って設定します currentnull 子供たちを救った後。

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つのノードを削除し、別の場所にまったく新しいノードを作成するだけであり、実際には独自のメソッドを必要としません。

バイナリヒープと優先度キューに移動すると、バイナリ検索ツリーを使用してよりクールな処理を実行できるようになります。