木（ツリー） - データサイエンス関連+αのメモ

木（Tree） は、ノード（節）とエッジ（辺）で構成される階層的なデータ構造。

根（root）: 最上位のノード
子（child）: あるノードの直下のノード
親（parent）: あるノードの直上のノード
葉（leaf）: 子を持たないノード
深さ（depth）: 根からのエッジ数
高さ（height）: 根から最も遠い葉までのエッジ数

木は再帰的な構造を持つため、再帰的なアルゴリズムと相性がよい。

二分木（Binary Tree）¶

各ノードが最大2つの子（左・右）を持つ木。

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

木の走査（Tree Traversal）¶

木の全ノードを訪問する順序には以下の種類がある。

走査順	訪問順序	用途
前順（preorder）	根 → 左 → 右	ツリーのコピー・シリアライズ
中順（inorder）	左 → 根 → 右	BST のソート済み列挙
後順（postorder）	左 → 右 → 根	ツリーの削除・サイズ計算
幅優先（BFS）	深さ順に左から右	最短経路・レベル順処理

from collections import deque

def preorder(node):
    """前順（根 → 左 → 右）"""
    if node is None:
        return []
    return [node.val] + preorder(node.left) + preorder(node.right)

def inorder(node):
    """中順（左 → 根 → 右）"""
    if node is None:
        return []
    return inorder(node.left) + [node.val] + inorder(node.right)

def postorder(node):
    """後順（左 → 右 → 根）"""
    if node is None:
        return []
    return postorder(node.left) + postorder(node.right) + [node.val]

def bfs(root):
    """幅優先探索（BFS）"""
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result


#       4
#      / \
#     2   6
#    / \ / \
#   1  3 5  7
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)

print("preorder  :", preorder(root))   # [4, 2, 1, 3, 6, 5, 7]
print("inorder   :", inorder(root))    # [1, 2, 3, 4, 5, 6, 7]
print("postorder :", postorder(root))  # [1, 3, 2, 5, 7, 6, 4]
print("BFS       :", bfs(root))        # [4, 2, 6, 1, 3, 5, 7]

二分探索木（Binary Search Tree, BST）¶

二分探索木 は、次の条件を満たす二分木：

左部分木の全ノードの値 < 根の値
右部分木の全ノードの値 > 根の値

この性質により、木が平衡であれば探索・挿入・削除が $O(\log n)$ で行える。

操作：

insert(x): 値 x を挿入する（ $O(\log n)$ ）
search(x): 値 x を検索する（ $O(\log n)$ ）
delete(x): 値 x を削除する（ $O(\log n)$ ）

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        self.root = self._insert(self.root, val)

    def _insert(self, node, val):
        if node is None:
            return TreeNode(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        return node

    def search(self, val):
        return self._search(self.root, val)

    def _search(self, node, val):
        if node is None:
            return False
        if val == node.val:
            return True
        if val < node.val:
            return self._search(node.left, val)
        return self._search(node.right, val)

    def delete(self, val):
        self.root = self._delete(self.root, val)

    def _delete(self, node, val):
        if node is None:
            return None
        if val < node.val:
            node.left = self._delete(node.left, val)
        elif val > node.val:
            node.right = self._delete(node.right, val)
        else:
            # 子が0または1つの場合
            if node.left is None:
                return node.right
            if node.right is None:
                return node.left
            # 子が2つの場合：右部分木の最小値（中順後継）で置き換える
            successor = self._min_node(node.right)
            node.val = successor.val
            node.right = self._delete(node.right, successor.val)
        return node

    def _min_node(self, node):
        while node.left:
            node = node.left
        return node

    def inorder(self):
        return inorder(self.root)

bst = BST()
for v in [5, 3, 7, 1, 4, 6, 8]:
    bst.insert(v)

print("inorder:", bst.inorder())   # [1, 3, 4, 5, 6, 7, 8]
print("search 4:", bst.search(4))  # True
print("search 9:", bst.search(9))  # False

bst.delete(3)
print("3を削除後:", bst.inorder())  # [1, 4, 5, 6, 7, 8]

計算量まとめ¶

操作	平均（平衡時）	最悪（偏った木）
探索	$O(\log n)$	$O(n)$
挿入	$O(\log n)$	$O(n)$
削除	$O(\log n)$	$O(n)$
走査（全ノード）	$O(n)$	$O(n)$

昇順・降順に要素を挿入すると木が一方向に伸びて $O(n)$ に劣化する。これを防ぐために 平衡二分木（AVL木・赤黒木） が使われる。

Pythonでの活用¶

Python の標準ライブラリには BST の実装はないが、sortedcontainers の SortedList が $O(\log n)$ の挿入・削除・探索を提供する。

競技プログラミングでは sortedcontainers が利用可能な環境では SortedList を使うことが多い。

from sortedcontainers import SortedList

sl = SortedList([5, 3, 7, 1, 4])
sl.add(6)
print(sl)              # SortedList([1, 3, 4, 5, 6, 7])
print(sl[0])           # 最小値: 1
print(sl[-1])          # 最大値: 7
sl.remove(3)
print(sl)              # SortedList([1, 4, 5, 6, 7])
print(sl.bisect_left(5))  # 5以上の最初のインデックス: 2

木の高さ・サイズ¶

再帰を使うと木のプロパティを簡潔に計算できる。

def height(node):
    """木の高さ（葉のheightは0）"""
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))

def size(node):
    """木のノード数"""
    if node is None:
        return 0
    return 1 + size(node.left) + size(node.right)


bst2 = BST()
for v in [5, 3, 7, 1, 4, 6, 8]:
    bst2.insert(v)

print("height:", height(bst2.root))  # 2
print("size  :", size(bst2.root))    # 7