JavaScriptを介したツリートラバーサル
ツリーは基本的には単なるリンクリストであり、ツリー上のノードの作成と削除は非常に簡単です。 一方、ソートされていない場合、検索は少し難しいので、ツリー全体の検索を処理するためのいくつかの異なる方法を調べます。
前提条件
ツリーとは何か、およびそれらがどのように機能するかについての基本的な理解が必要になります。 二分探索木を利用した特定の例ですが、これらは正確な実装というよりも技術とパターンであり、あらゆるタイプのツリーに簡単に適合させることができます。
コンセプト
二分探索木を使用すると、同じシステムを使用して、ノードを見つけるのと同じ新しいノードを作成できます。 ファイルシステムのような標準ツリーは、特定のルールに従わず、ツリーまたはサブツリーを介してすべてのアイテムを調べて、必要なものを見つけるように強制します。 これが、特定のファイルの検索の実行に非常に時間がかかる理由です。
過去のO(n)
を最適化する方法は多くありませんが、幅優先(水平方向に兄弟間)または深さ優先(垂直方向に親と子供)。
木
二分探索木は設定が最も簡単なので、ノードを追加することしかできない簡単な探索木をまとめることができます。
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 ]
深さ優先探索
深さ優先探索は、すべてのレベルを完了するよりも、ツリーの側面全体から葉までのトラバースを完了することに関心があります。
これを処理する主な方法は、preOrder
、postOrder
、inOrder
の3つですが、出力順序を変更するための相互のわずかな変更です。 さらに良いことに、キューについて心配する必要はもうありません。
ルートから始めて、短い再帰関数を使用してノードをログに記録してから、可能な限り左に移動し、途中でそのパスをログに記録します。 左側が完了すると、ツリー全体がログに記録されるまで、残りの右側の値の処理が開始されます。 最終的に訪問されるのは[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)
になります。これは、すべてのノードを調べることがポイントであるため、手抜きや巧妙なトリックの余地があまりないためです。
これらは覚えておく必要のある正確な実装ではなく、問題を解決し、より価値のあるアルゴリズムを構築するための一般的なパターンであることに注意してください。 下線を引く概念を理解すると、それらは任意の言語またはフレームワークに簡単に適合させることができます。