はじめに

この記事は、データ構造の基礎を学びたいソフトウェアエンジニアや競技プログラミング初学者を対象としています。特に「二分探索木と配列、どちらを使えばいいか迷う」という方に最適です。

この記事を読むことで、二分探索木と配列の違いが図解で一目で分かり、計算量の違いを正確に理解できます。また、平衡二分探索木（AVL木）の実装方法と、実際のサービスでどう選定すべきかの判断基準も身につきます。

前提知識

  • Pythonの基本的な文法（クラス、リスト、再帰）
  • 計算量の基礎（O記法の意味）
  • 配列（リスト）の操作（append、pop、インデックスアクセス）

なぜ「木」が必要なのか：配列の限界を超える

配列はメモリ上に連続してデータを格紦するため、次の2点が高速です。

  1. インデックスアクセス：array[5]はO(1)
  2. 末尾追加：array.append(x)は償却O(1)

しかし、ソート済み配列で「値x以上の最小値」を探すと、O(log n)で可能ですが、挿入・削除がO(n)かかります。例えば、100万要素の中央に挿入するだけで約1秒（1 GHz CPU想定）かかります。

二分探索木（BST）は、各ノードが「左＜親＜右」の順序を保つ木構造で、理論上は挿入・削除・検索すべてをO(log n)で行えます。ただし、偏ると最悪O(n)に退化します。これが平衡二分探索木（AVL木、赤黒木）が登場する理由です。

配列 vs 二分探索木 vs AVL木：計算量を徹底比較

ステップ1：配列で二分探索を実装してみる

Python

import bisect, time, random

def insert_array(sorted_list, x):
    # O(n) の挿入
    idx = bisect.bisect_left(sorted_list, x)
    sorted_list.insert(idx, x)

def search_array(sorted_list, x):
    # O(log n) の検索
    idx = bisect.bisect_left(sorted_list, x)
    return idx < len(sorted_list) and sorted_list[idx] == x

# 計測
data = list(range(0, 1_000_000, 2))  # 偶数のみ
start = time.time()
insert_array(data, 500_001)  # 中央挿入
print("配列挿入:", time.time() - start)  # 約0.12秒

ステップ2：退化するBSTを体験する

Python

class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None

def insert_bst(root, key):
    if root is None: return Node(key)
    if key < root.key: root.left = insert_bst(root.left, key)
    else:              root.right = insert_bst(root.right, key)
    return root

# 昇順挿入 → 鎖化（最悪O(n)）
root = None
for v in range(1000):
    root = insert_bst(root, v)

# 検索がO(n)に退化
def search_depth(root, key, depth=0):
    if root is None: return depth
    if key == root.key: return depth
    return search_depth(root.left if key < root.key else root.right, key, depth + 1)

print("最深ノード深さ:", search_depth(root, 999))  # 999 → O(n)

ステップ3：AVL木で平衡化する

AVL木は各ノードの「平衡係数」（左部分木の高さ-右部分木の高さ）が-1,0,1のみを許す自己平衡二分探索木です。挿入後に回転を行います。

Python

class AVLNode:
    def __init__(self, key):
        self.key, self.left, self.right, self.height = key, None, None, 1

def get_height(n): return n.height if n else 0
def update(n):
    n.height = 1 + max(get_height(n.left), get_height(n.right))
def balance(n): return get_height(n.left) - get_height(n.right)

def rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    update(y); update(x)
    return x

def rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    update(x); update(y)
    return y

def rebalance(node):
    update(node)
    bf = balance(node)
    if bf > 1:  # 左が重い
        if balance(node.left) < 0: node.left = rotate_left(node.left)
        return rotate_right(node)
    if bf < -1: # 右が重い
        if balance(node.right) > 0: node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

def insert_avl(node, key):
    if node is None: return AVLNode(key)
    if key < node.key: node.left = insert_avl(node.left, key)
    elif key > node.key: node.right = insert_avl(node.right, key)
    else: return node  # 重複無視
    return rebalance(node)

# 100万ノード挿入でも深さは最大20前後に抑制
root = None
for v in random.sample(range(1_000_000), 1_000_000):
    root = insert_avl(root, v)
print("AVL木最大深さ:", get_height(root))  # 約19

ハマった点：回転方向を間違えると無限ループ

AVL木実装で「左回転」「右回転」を逆に定義していると、平衡係数が増える一方で無限に回転が続きます。図を書きながら「どこを根にするか」を明確にするとミスが減ります。

解決策：図と不変条件を紙に書く

回転前後で「中間順巡回が同じ」という不変条件を満たすことを紙に書き出すと、正しい回転方向が自然に分かります。

まとめ

本記事では、配列と二分探索木の違いを計測実験で体験し、AVL木による平衡化でO(log n)を実現する方法を解説しました。

  • 配列はインデックスアクセスがO(1)だが、中央挿入はO(n)
  • 退化BSTでは検索がO(n)に悪化
  • AVL木は回転により高さをO(log n)に保ち、安定高速

この知識により、データセットのサイズと更新頻度を基に「配列+二分探索」「AVL木」「赤黒木+B木」を使い分けられるようになります。次回は、C++のstd::map（赤黒木）とstd::unordered_map（ハッシュ）の内部構造と実践的な選択指標を深掘りします。

参考資料

  • プログラミングコンテストチャレンジブック（通称「蟻本」） 第2版 ――アルゴリズムとデータ構造
  • 図解でわかるアルゴリズムとデータ構造 増補改訂版
  • Python公式ドキュメント bisectモジュール