木構造

木(Tree)は一種の非線形のデータ構造であり、自然界の木の枝分かれした階層を模倣しています。配列や連結リストのように一列に並ぶ線形構造とは異なり、木の中のデータ要素(ノード)の間には明確な一対多の階層関係があります。

木構造まるで実際の木のようなものです:

  • 根ノード:木の根元であり、親ノードを持たない唯一のノード
  • 子ノード:あるノードから分岐したノード
  • 葉ノード:子ノードを持たないノードで、木の葉のようなもの
  • パス:あるノードから別のノードまでの経路
  • 深さ:根ノードからそのノードまでのパスの長さ
  • 高さ:そのノードから最も遠い葉ノードまでのパスの長さ

身近な例え:

  • 家系図祖父母→親→子→孫
  • 組織構造:CEO→ディレクター→マネージャー→社員
  • ファイルシステム:ルートディレクトリ→サブディレクトリ→ファイル
  • 図書分類:総記→下位分類→具体的な書籍
構造の種類 検索効率 挿入効率 削除効率 順序性
配列 O(n) O(n) O(n) 无
連結リスト O(n) O(1) O(1) 无
ハッシュテーブル O(1) O(1) O(1) 无
二分探索木 O(log n) O(log n) O(log n) 有

基本用語

詳しく学ぶ前に、木の基本用語を確認しておきましょう:

  • ノード(Node):木の中の各要素です。格納するデータと、その子ノードへのリンクを含みます。
  • 根ノード(Root):木の最上位にあるノードで、木全体の起点です。1つの木には根ノードが1つだけ存在します。
  • 親ノードと子ノード(Parent & Child):ノードAが下のノードBに接続されている場合、AはBの親ノードであり、BはAの子ノードです。1つの親ノードは複数の子ノードを持つことができます。
  • 兄弟ノード(Siblings):同じ親ノードを持つノード同士は兄弟ノードになります。
  • 葉ノード(Leaf):子ノードを持たないノードで、終端ノードとも呼ばれます。
  • 辺(Edge):2つのノードを結ぶ線で、それらの関係を表します。
  • パス(Path):根ノードから特定のノードまでに経由するノードの並びです。
  • 高さ(Height):あるノードから最も遠い葉ノードまでの最長パス上の辺の数。木の高さは根ノードの高さと同じです。
  • 深さ(Depth):根ノードからあるノードまでのパス上の辺の数。根ノードの深さは0です。
  • レベル(Level):深さが同じすべてのノードは同じレベルに属します。根ノードはレベル0にあります。

木の基本性質

  1. 唯一のパス:木の中の任意の2つのノード間には、パスがただ1つだけ存在します。
  2. N個のノード、N-1本の辺:N個のノードを持つ木には、合計N-1本の辺があります。
  3. 閉路なし:木の中に閉路は存在しません(つまり、あるノードから出発して辺をたどっても、最終的にそのノードに戻ることはありません)。

なぜ木が必要なのか?—— 木の利点と応用

配列と連結リストがあるのに、なぜ木が必要なのかと疑問に思うかもしれません。答えは効率にあります。

  • 配列:検索が速い(インデックスによる)が、挿入と削除が遅い(大量の要素を移動する必要がある)。
  • 連結リスト:挿入と削除が速いが、検索が遅い(先頭から走査する必要がある)。
  • 木(特に二分探索木):データの順序を保ちながら、連結リストよりはるかに速い検索速度と、配列より効率的な挿入・削除操作を提供します。

実際の応用シーン:

  • ファイルシステム:コンピュータ内のフォルダとファイルは、木構造で整理されています。
  • データベースインデックス:B木やB+木は、データベースで高効率な問い合わせを実現するための中核的なデータ構造です。
  • 組織図:会社や部門の階層管理。
  • 決定木:人工知能や機械学習における分類モデル。
  • HTML DOM:Webページの文書オブジェクトモデル(DOM)は木構造です。

二分木:木の仲間の中で最も重要な存在

二分木(Binary Tree)は、各ノードが最大2つの子ノードを持つ木です。この2つの子ノードは通常、左の子ノードと右の子ノードと呼ばれます。二分木は、多くの強力な木構造(二分探索木、ヒープ、AVL木など)の基礎となっています。

基本構造は次のとおりです:

二分木の基本用語

用語 定義 身近な例え
ノード データとポインタを含む基本単位 家族の中の1人
根ノード 木の最上位のノード 家族の中の祖先
親ノード 子ノードを持つノード 親
子ノード 親ノードから指されているノード 子供
兄弟ノード 同じ親ノードの子ノード 兄弟姉妹
葉ノード 子ノードを持たないノード 家族の中で子供がいない人
深さ 根からそのノードまでの辺の数 世代の数
高さ そのノードから最も遠い葉ノードまでの辺の数 その家族が続く世代数

二分木の種類

種類 特徴 時間計算量 応用シーン
通常の二分木 各ノードが最大2つの子ノードを持つ O(n) 式木
全二分木 各ノードが0個または2個の子ノードを持つ O(n) ハフマン符号化
完全二分木 最後のレベルを除いてすべて埋まっている O(n) ヒープの実装
二分探索木 左<根<右 平均O(log n) 検索、ソート
平衡二分木 左右の部分木の高さの差≤1 O(log n) データベースインデックス
赤黒木 色付きの平衡木 O(log n) Linuxカーネル

二分探索木の操作

操作 説明 時間計算量
検索 値に基づいてノードを検索する 平均O(log n)、最悪O(n)
挿入 新しいノードを挿入する 平均O(log n)、最悪O(n)
削除 指定したノードを削除する 平均O(log n)、最悪O(n)
走査 すべてのノードにアクセスする O(n)

二分木の走査

走査とは、特定の規則に従って木の中のすべてのノードにアクセスし、各ノードを1回だけ訪問することです。これは木に関連するアルゴリズムの基礎となります。主に4つの方法があります:

  1. 行きがけ順(Pre-order):根 → 左 → 右

    • 最初にルートノードを訪問し、次に左部分木を再帰的に前順走査し、最後に右部分木を再帰的に前順走査します。
    • 応用:木のコピー、前置式の取得。
  2. 通りがけ順(In-order):左 → 根 → 右

    • 最初に左部分木を再帰的に中順走査し、次にルートノードを訪問し、最後に右部分木を再帰的に中順走査します。
    • 応用:二分探索木(BST)において、中順走査は昇順ですべての値を出力します。
  3. 帰りがけ順(Post-order):左 → 右 → 根

    • 最初に左部分木を再帰的に後順走査し、次に右部分木を再帰的に後順走査し、最後にルートノードを訪問します。
    • 応用:木の削除、ディレクトリサイズの計算。
  4. レベル順走査(Level-order):階層ごとに、左から右へ

    • ルートノードから始めて、階層ごとにノードを訪問します。
    • 応用:階層ごとにデータを処理する(組織図の出力など)。通常はキュー(Queue)を補助に使って実装します。。

例:下図の二分木の場合、走査結果は次のようになります。

        1
       / \
      2   3
     / \   \
    4   5   6
  • 前順:1, 2, 4, 5, 3, 6
  • 中順:4, 2, 5, 1, 3, 6
  • 後順:4, 5, 2, 6, 3, 1
  • レベル順:1, 2, 3, 4, 5, 6

実践:Pythonで二分木を実装する

理論は十分です。実際にコードを書いてみましょう!単純な二分木のノードクラスを実装し、挿入と走査の操作を完成させます。

ステップ1:ノードクラスを定義する

各ノードはデータを格納し、左と右の子ノードを指す必要があります。

例

class TreeNode:
    """二分木ノードクラス"""
    def __init__(self, value):
        self.value = value  # ノードが格納するデータ
        self.left = None    # 左の子ノードを指す
        self.right = None   # 右の子ノードを指す

    def __str__(self):
        """ノード情報を出力しやすくする"""
        return f"Node({self.value})"

ステップ2:サンプルの木を構築する

先ほどの例の図にあるツリーを手動で構築しましょう。

例

# ノードを作成
root = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node6 = TreeNode(6)

# 接続関係を構築(Links)
root.left = node2
root.right = node3
node2.left = node4
node2.right = node5
node3.right = node6

print(f"ルートノード: {root}")
print(f"ルートノードの左の子ノード: {root.left}")
print(f"ルートノードの右の子ノード: {root.right}")

ステップ3:走査アルゴリズムを実装する(再帰版)

再帰はツリー走査を実装する最も直感的な方法です。

例

def preorder_traversal(node):
    """前順走査:根 -> 左 -> 右"""
    if node is None:
        return
    print(node.value, end=' ')  # 1. ルートノードを訪問
    preorder_traversal(node.left)   # 2. 左部分木を走査
    preorder_traversal(node.right)  # 3. 右部分木を走査

def inorder_traversal(node):
    """中順走査:左 -> 根 -> 右"""
    if node is None:
        return
    inorder_traversal(node.left)    # 1. 左部分木を走査
    print(node.value, end=' ')  # 2. ルートノードを訪問
    inorder_traversal(node.right)   # 3. 右部分木を走査

def postorder_traversal(node):
    """後順走査:左 -> 右 -> 根"""
    if node is None:
        return
    postorder_traversal(node.left)  # 1. 左部分木を走査
    postorder_traversal(node.right) # 2. 右部分木を走査
    print(node.value, end=' ')  # 3. ルートノードを訪問

print("\n--- 走査デモ ---")
print("前順走査の結果:", end=' ')
preorder_traversal(root) # 出力: 1 2 4 5 3 6

print("\n中順走査の結果:", end=' ')
inorder_traversal(root)  # 出力: 4 2 5 1 3 6

print("\n後順走査の結果:", end=' ')
postorder_traversal(root) # 出力: 4 5 2 6 3 1

ステップ4:レベル順走査を実装する(キューを使用)

レベル順走査では、キューの「先入れ先出し」という特性を利用する必要があります。

例

from collections import deque

def level_order_traversal(root):
    """レベル順走査:キューを使用"""
    if root is None:
        return

    queue = deque([root]) # キューを初期化し、ルートノードを入れる

    while queue:
        current_node = queue.popleft() # 1. キューの左側からノードを取り出す
        print(current_node.value, end=' ') # 2. そのノードを訪問

        # 3. そのノードの子ノード(存在すれば)を順にキューの右側に追加
        if current_node.left:
            queue.append(current_node.left)
        if current_node.right:
            queue.append(current_node.right)

print("\nレベル順走査の結果:", end=' ')
level_order_traversal(root) # 出力: 1 2 3 4 5 6

演習とチャレンジ

基礎学習の完了おめでとうございます!ツリーを本当にマスターするには、実際に練習することが不可欠です。

演習1:木の高さを計算する

関数を書いてくださいtree_height(node)、木のルートノードを受け取り、その木の高さを返します(空の木の高さは -1 または 0 とします。慣例に合わせてよいです。この例ではエッジの数と定義します)。

ヒント:ツリーの高さ = 1 + max(左部分木の高さ, 右部分木の高さ)。これは典型的な再帰問題です。

演習2:二分木で値を検索する

関数を書いてくださいsearch_in_tree(node, target_value)、与えられた二分木の中に、値がtarget_valueと等しいノードが存在するか検索します。見つかった場合は、True、それ以外の場合はFalse。

ヒント:任意の走査方法を使用して、各ノードを訪問するときにその値を比較できます。

チャレンジ:二分探索木(BST)

これは二分木の古典的な変種です。二分探索木では、任意のノードについて:

  • 其左部分木内のすべてのノードの値は<そのノードの値。
  • 其右部分木内のすべてのノードの値は>そのノードの値。

あなたのチャレンジは:

  1. 実装するinsert_into_bst(root, value)関数:二分探索木の正しい位置に値を挿入します。
  2. 実装するsearch_in_bst(root, value)関数:BSTの特性を利用して効率的に検索します(平均時間計算量 O(log N))。
その他の拡張