JavaScriptの二分木（バイナリツリー）とは？基本概念と重要用語を徹底解説

二分木（バイナリツリー）は、データの格納を目的として使用される特殊なデータ構造です。最大の特徴は、各ノードが持てる子ノードの数が2つまでという条件にあります。

二分木は、整列済み配列と連結リストの両方の長所を兼ね備えた構造です。検索はソートされた配列と同等の速さで行え、データの挿入や削除も連結リストと同様に高速に実行できます。そのため、大量のデータを効率的に扱いたい場合に非常に有用なデータ構造といえます。

以下は、二分木の構造を示したイラストです。図には、このあと解説する重要な用語も含まれています。

二分木における重要な用語

二分木を理解するうえで押さえておきたい、主要な用語を以下にまとめました。

• パス（Path） − 木の辺に沿ってたどることができる、一連のノードの並びを指します。

• ルート（Root） − 木の最上部に位置するノードのことです。木には必ず1つのルートしか存在せず、ルートから任意のノードへの経路は常に1本に定まります。

• 親（Parent） − ルート以外のすべてのノードは、1つ上のノードへ向かう辺を1本持ちます。この接続先となるノードを「親ノード」と呼びます。

• 子（Child） − あるノードから下向きの辺で接続されているノードを「子ノード」と呼びます。

• 葉（Leaf） − 子ノードを一切持たないノードのことを「葉ノード」と呼びます。

• 部分木（Subtree） − あるノードと、そこから派生する子孫全体で構成される木を指します。

• 訪問（Visiting） − 処理の対象がノード上にあるときに、そのノードの値を確認することを意味します。

• 走査（Traversing） − 特定の順序に従って、ノードを順番に通過していく操作のことです。

• レベル（Levels） − ノードの世代を表します。ルートをレベル0とすると、その直下の子ノードはレベル1、孫ノードはレベル2となり、世代が下がるごとにレベルが1ずつ増加します。

• キー（Keys） − ノードが保持する値のことであり、検索操作を実行する際の判定基準となります。

まとめ

二分木は「検索の速さ」と「挿入・削除の柔軟性」を両立できる優れたデータ構造です。パスやルート、葉といった基本的な用語を正しく理解しておくことは、走査アルゴリズムや探索木の実装を学ぶうえでの土台となります。まずは各用語の意味をしっかり押さえ、実際のコードでの活用につなげましょう。