木（ツリー）#
木（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]
preorder : [4, 2, 1, 3, 6, 5, 7]
inorder : [1, 2, 3, 4, 5, 6, 7]
postorder : [1, 3, 2, 5, 7, 6, 4]
BFS : [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]
inorder: [1, 3, 4, 5, 6, 7, 8]
search 4: True
search 9: False
3を削除後: [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
---------------------------------------------------------------------------
ModuleNotFoundError Traceback (most recent call last)
Cell In[5], line 1
----> 1 from sortedcontainers import SortedList
3 sl = SortedList([5, 3, 7, 1, 4])
4 sl.add(6)
ModuleNotFoundError: No module named 'sortedcontainers'
木の高さ・サイズ#
再帰を使うと木のプロパティを簡潔に計算できる。
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