分子シミュレーション＆インフォマティクス 用語解説

木構造  [きこうぞう] [Tree Data Structure]

データを階層的に整理・管理するための基本的なデータ構造である。自然界の木を逆さまにしたように、最上位の根（ルート）から下に向かって枝分かれしていく構造を持つ。データの各単位は節（ノード）と呼ばれ、節間をつなぐ線を枝（エッジ）と呼ぶ。上の節と下の節は親子関係を持ち、各要素がただ一つの親要素しか持たないことを一意性という。また、木構造ではループ（循環）が発生しないことが大きな特徴である。ルートからの距離は深さ（Depth）、木構造全体の最大の深さは高さ（Height）と定義される。木構造は、ファイルシステム、Webサイトの構造、データベース設計、そして機械学習の決定木モデルなど、階層的なデータを扱う多くの分野で基礎として利用されている。

木構造の主な種類

木構造は、特定のルールを設けることで、多様な用途に最適化される。

１．二分木と多分木

• 「二分木（Binary Tree）」は、ノードから出る枝が「すべて2本以下」に制限された木である。ノードには「左の子ノード」と「右の子ノード」という概念がある。子ノードが3以上になる場合は「多分木（Multi-branch Tree）」と呼ばれる。

２．探索に特化した木

• 「二分探索木（Binary Search Tree）」：二分木の中で、「左の子のデータ＜親のデータ＜右の子のデータ」というルールを全てのノードが満たす木である。このルールにより、データの探索効率が非常に高くなる。
• 「B木（B-Tree）」：各ノードが多数の子ノードを持つことができ、階層の深さが常に同じになるよう自動でバランスを保つ木構造である。大量データを効率的に管理できるため、データベースやファイルシステムで広く用いられる。B木の派生変種として、「B+木」がある。

３．効率的なデータ操作のための木

• 「ヒープ（Heap）」：完全二分木とヒープ条件（親データが子データより常に大きい、または小さい）を満たす木構造である。優先度付きキューの実装や、高速な整列（ソート）であるヒープソートに利用される。
• 「平衡木（Balanced Tree）」：左右の部分木の高さの差が一定範囲内に保たれている木構造で、検索効率の低下を防ぐ目的で使用される。「AVL木」はその代表例である。