ルート集約のアルゴリズム - 2分木編
CIDRのリストをルート集約するアルゴリズムを整理する。本稿では、IPアドレスを2分木を用いて処理する方法を紹介する。
ルート集約をキーワードとしているが、本稿では、ルーティングについては扱わない。IPアドレスの集約についてのみ着目する。
ルート集約に関する記事、第3弾である。
線形編との違いは、CIDRリストを集約する点は同じであるが、アプローチや実装方法が異なるため計算効率などが異なる。
ルート集約の例
ルート集約の例を示す。下の例では、4つのCIDR表記のネットワークアドレス(/32を含む)を1つに集約することができる。
192.168.0.0/24
192.168.1.0/24
192.168.2.0/24
192.168.3.0/24
↓ 集約
192.168.0.0/22
モチベーション
安定的なCIDRリストの集約を目指す。CIDRのリストの量が多くても、安定した短い時間で集約処理できることを目指す。
2分木（バイナリトライ）を使用したCIDRルート集約アルゴリズム
本稿では、2分木（バイナリトライ）を用いて、CIDRのリストを最小集合へと自動的に集約するアルゴリズムを解説する。このアルゴリズムは、CIDRをビット列に変換して木構造に登録し、包含関係の除去と兄弟ノードの親方向への圧縮を繰り返すことで、重複のない最適なCIDR集合をO(32n)の時間計算量で求めることができる。
前提知識
プレフィックス木（トライ）
プレフィックス木は、ビット列をキーとする木構造である。IPv4アドレスは32ビットで表現されるため、深さ32の2分木を考えると、各プレフィックス（CIDR）は木のルートからあるノードまでのパスに対応する。
- 左の子ノードはビット
0を表す - 右の子ノードはビット
1を表す - 各CIDR
/Nは、アドレスの上位Nビットをたどった先のノードに対応する
アルゴリズムの概要
本アルゴリズムは、CIDRのリストをプレフィックス木（BinaryTree）に登録し、包含関係や隣接するプレフィックスを整理・集約することで、最小のCIDR集合へ正規化する手法である。
処理の流れ
入力CIDRs: [A, B, C, D, ...]
各CIDRについて以下を繰り返す:
1. CIDRをビット列（プレフィックスパス）へ変換する
2. 既に上位プレフィックスに包含されているか判定する
- 包含されていればスキップする
3. 同じプレフィックス以下に存在する下位プレフィックスを削除する
4. プレフィックスをBinaryTreeのノードとして作成する
5. そのノードを marked（含む）として登録する
6. 必要に応じて兄弟ノードを親ノードへ集約（圧縮）する
全CIDRの処理が完了したら:
7. Treeから正規化されたプレフィックス集合を取得する
8. プレフィックス集合をCIDRへ変換し、出力する
アルゴリズムの詳細
1. CIDRからビット列への変換
CIDR 192.168.1.0/24 を考える。まずIPアドレスを32ビットの整数に変換する：
192.168.1.0 → 11000000.10101000.00000001.00000000
プレフィックス長が24なので、上位24ビットをプレフィックスパスとして抽出する：
[1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
このビット列をたどることで、木の中で対応するノードに到達する。
逆に、プレフィックスパスからCIDRを復元するには、パスのビットを左寄せで32ビットに拡張し、パスの長さをプレフィックス長とする。
2. 上位に包含されているか判定（is_ancestor_marked）
新しいCIDRを登録する前に、すでにその範囲をカバーする上位プレフィックスが木に存在しないかを確認する。
たとえば、192.168.1.0/24 が既に木に登録されている（marked）状態で、192.168.1.0/25 を追加しようとすると、/24 のノードが上位に存在するため、/25 は重複でありスキップされる。
判定方法：プレフィックスパスを上から順にたどりながら、各ノードの marked フラグを確認する。途中で marked なノードが見つかれば、そのパスは既に包含されている。
木の状態: /24 が marked
追加しようとするパス: /25
→ 上位の /24 ノードが marked → スキップ
3. 子要素の削除（remove_subtree）
逆に、より広いプレフィックスを追加する場合、既存の下位プレフィックスを削除する必要がある。
たとえば、192.168.1.0/25 と 192.168.1.128/25 が既に木に存在する状態で、192.168.1.0/24 を追加すると、/25 2つは /24 に包含されるため削除される。
削除方法：プレフィックスパスをたどって対象ノードに到達し、そのノードの marked フラグを false にし、子ノード（left, right）をすべて None にすることで、サブツリー全体を除去する。
木の状態: /25x2 が marked
追加するパス: /24
→ /24 のサブツリー（＝ /25x2 を含む）を丸ごと削除
→ /24 ノードを marked として設定
4. 挿入（insert）
CIDRを木に登録する一連の処理をまとめると、insert 操作は以下のように実行される。
insert(path):
1. path.len() > depth ならスキップ
2. is_ancestor_marked(path) ならスキップ（上位に包含済み）
3. パスをたどりながら必要に応じてノードを作成
4. remove_subtree: 対象ノードのサブツリーを削除
5. 対象ノードを marked = true に設定
6. compress_up: 親方向への集約を実行
5. 親方向への集約・圧縮（compress_up）
ノードを marked にした後、親方向に遡りながら圧縮を行う。あるノードの左右の子ノードが両方とも marked であれば、これらは親ノード1つに集約できる。
集約条件：
- 左ノードが marked であること
- 右ノードが marked であること
- この2つが揃っていれば、親ノードを marked にし、左右の子ノードを削除する
この圧縮を再帰的に行うことで、木全体が自動的に集約される。
圧縮前:
[ ]
/ \
[L] [R] ← 両方 marked
圧縮後:
[marked] ← 親に集約、子は削除
圧縮前:
[ ]
/ \
[ ] [ ]
/ \
[L] [R] ← 両方 marked
圧縮後:
[ ]
/ \
[marked] ← 親に集約
6. 正規化後の探索（extract_marked）
全CIDRの登録と圧縮が完了した後、木から marked なノードをすべて抽出する。これは深度優先探索（DFS）で行われる。
重要な点：marked なノードが見つかった場合、そのサブツリーは探索しない。なぜなら、marked ノードはその下位範囲をすべてカバーしており、子ノードの探索は不要だからである。
抽出された各プレフィックスパスは、CIDR表記に変換されて出力される。
2分木を使用するメリット
- 1回のスキャンで正規化完了
- 各CIDRを1度だけ処理すればよい
- O(n) の時間計算量
- 木の深さが固定（32）であるため
- 自動的な集約
- 兄弟ノードの圧縮により、最も短いプレフィックスに自動的に集約される
- 包含関係の自動処理
- 上位・下位の判定が木の走査で自然にできる
まとめ
本稿では、CIDRのリストをルート集約するアルゴリズムを整理し、紹介した。IPアドレスを2分木を用いて集約できるようになった。