JavaScriptを介したツリートラバーサル

投稿日: 2022-04-20 2022-10-06
タグ: javascript

ツリーは基本的には単なるリンクリストであり、ツリー上のノードの作成と削除は非常に簡単です。一方、ソートされていない場合、検索は少し難しいので、ツリー全体の検索を処理するためのいくつかの異なる方法を調べます。

前提条件

ツリーとは何か、およびそれらがどのように機能するかについての基本的な理解が必要になります。二分探索木を利用した特定の例ですが、これらは正確な実装というよりも技術とパターンであり、あらゆるタイプのツリーに簡単に適合させることができます。

コンセプト

二分探索木を使用すると、同じシステムを使用して、ノードを見つけるのと同じ新しいノードを作成できます。ファイルシステムのような標準ツリーは、特定のルールに従わず、ツリーまたはサブツリーを介してすべてのアイテムを調べて、必要なものを見つけるように強制します。これが、特定のファイルの検索の実行に非常に時間がかかる理由です。

過去を最適化する方法は多くありません O(n) しかし、幅優先（水平方向に兄弟間）または深さ優先（垂直方向に親と子の間）のいずれかによって、ツリー全体を検索するための2つの主要な「哲学」があります。

木

二分探索木は設定が最も簡単なので、ノードを追加することしかできない簡単な探索木をまとめることができます。

class Node {
  constructor(val) {
    this.val = val;
    this.right = null;
    this.left = null;
  };
};

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) return this;
      if (val < current.val) addSide('left');
      else addSide('right');
    };
  };
};

const tree = new BST();
tree.create(20);
tree.create(14);
tree.create(57);
tree.create(9);
tree.create(19);
tree.create(31);
tree.create(62);
tree.create(3);
tree.create(11);
tree.create(72);

幅優先探索

幅優先探索は、次のレベルに移動する前に、すべてのレベルで、左から右にすべてのアイテムに焦点を合わせるという事実によって特徴付けられます。

これには、現在のノード、訪問したノードのリスト、および確認する必要のあるノードを追跡するための基本的なキューの3つの主要部分があります（配列を使用するので、非常に長くなることはありません）。

このツリーでどのように表示されるかを見ていきましょう。

私たちの current、子を（左から右に）キューにプッシュするので、次のようになります。 [20, 14, 57]. 次に変更します current キュー内の次のアイテムに移動し、その左と右の子をキューの最後に追加します。 [14, 57, 9, 19].

現在のアイテムを削除して追加できるようになりました visited 次のアイテムに移動する間、その子を探して、キューに追加します。これは、キューが空になり、すべての値が入るまで繰り返されます visited.

BFS() {
  let visited = [],
      queue = [],
      current = this.root;

  queue.push(current);
  while (queue.length) {
    current = queue.shift();
    visited.push(current.val);

    if (current.left) queue.push(current.left);
    if (current.right) queue.push(current.right);
  };

    return visited;
}

console.log(tree.BFS()); //[ 20, 14, 57, 9, 19, 31, 62, 3, 11, 72 ]

深さ優先探索

深さ優先探索は、すべてのレベルを完了するよりも、ツリーの側面全体から葉までのトラバースを完了することに関心があります。

これを処理する主な方法は3つあります。 preOrder, postOrder、と inOrder しかし、それらは出力順序を変更するための相互のごくわずかな変更にすぎません。さらに良いことに、キューについて心配する必要はもうありません。

ルートから始めて、短い再帰関数を使用してノードをログに記録してから、可能な限り左に移動し、途中でそのパスをログに記録します。左側が完了すると、ツリー全体がログに記録されるまで、残りの右側の値の処理が開始されます。最後に訪問したのは次のようになります [24, 14, 9, 3, 11, 19, ...].

preOrder() {
  let visited = [],
      current = this.root;

  let traverse = node => {
    visited.push(node.val);
    if (node.left) traverse(node.left);
    if (node.right) traverse(node.right);
  };

  traverse(current);
  return visited;
}

console.log(tree.preOrder()); // [ 20, 14, 9, 3, 11, 19, 57, 31, 62, 72 ]

ご想像のとおり、 postOrder の反対です preOrder、まだ垂直方向に作業していますが、ルートからリーフに移動する代わりに、下から上に検索します。

左下のノードから開始し、そのノードとその兄弟をログに記録してから、親に移動します。訪問の前半は次のようになりますが、 [3, 11, 9, 19, 14, ...]、それが機能するにつれて、それは木を泡立たせます。

ノードをにプッシュすることで、これを簡単に実現できます visited 両方のトラバーサルが完了した後。

postOrder() {
  let visited = [],
      current = this.root;

  let traverse = node => {
    if (node.left) traverse(node.left);
    if (node.right) traverse(node.right);
    visited.push(node.val);
  };

  traverse(current);
  return visited;
}

console.log(tree.postOrder()); // [ 3, 11, 9, 19, 14, 31, 72, 62, 57, 20 ]

に似ている postOrder, preOrder 訪問は下から上に機能しますが、兄弟の前に親を訪問するだけです。

開始または終了の代わりに、左側をトラバースした後、右側の前にリストにプッシュできます。結果は次のようになります。 [3, 9, 11, 14, 19, 20, ...].

inOrder() {
  let visited = [],
      current = this.root;

  let traverse = node => {
    if (node.left) traverse(node.left);
    visited.push(node.val);
    if (node.right) traverse(node.right);
  };

  traverse(current);
  return visited;
}

console.log(tree.inOrder()); // [ 3, 9, 11, 14, 19, 20, 31, 57, 62, 72 ]

まとめ

もちろん、これらのアルゴリズムはすべて O(n) 重要なのはすべてのノードを調べることなので、手抜きや巧妙なトリックを行う余地はあまりありません。

これらは覚えておく必要のある正確な実装ではなく、問題を解決し、より価値のあるアルゴリズムを構築するための一般的なパターンであることに注意してください。下線を引く概念を理解すると、それらは任意の言語またはフレームワークに簡単に適合させることができます。

getdocs

13036