Radix tree（基数木）はIPアドレスのLongest prefix matching（最長一致）などに使われる二分探索木です。 このエージでは，Radix treeへのノードの挿入、削除、検索アルゴリズムを解説します。 実装はgithub repositoryで公開しています。

具体的なアルゴリズムの説明の前に，以下の5つのエントリを使ってRadix treeの例を見ましょう。

以下の図は，上記の5エントリのRadix treeを図示したものです。 Radix treeはキーの各1ビットが二分木の左右の枝に対応しています。 Radix treeでは，それぞれのノードの深さがプレフィックス長+1になるようにノードが配置されています。

検索アルゴリズムは単純に二分木をキーの各ビットに従って辿るだけです。 深さdから深さd+1への探索は，キーのdビット目の値（0または1）により実行されます。 0であれば左分木，1であれば右分木を探索します。

例えば，上図の木に対して10101というキーで探索する場合は，

1. キーの最上位ビット（=1）を確認し，右の枝に進みます（ノードaからノードd）
2. 次にキーの第2ビット（=0）を確認し，左の枝に進みます（ノードdからノードe）
3. 次にキーの第3ビット（=1）を確認し，右の枝に進みます（ノードeからノードi）
4. 次にキーの第4ビット（=0）を確認し，左の枝に進みます
5. 左の枝は空のノード（null）なので，親ノードのうち値の存在するノードを逆探索します。 この例ではノードiが該当します。 このようにして，10101に対するLongest prefix matchingの結果として，ノードP2が得られます。

ノードの挿入は非常に単純です。 挿入されるノードの位置は深さがプレフィックス長+1であるので，探索と同じ手順で挿入場所を探すことができます。 挿入場所の探索中に空のノードに到達した場合は，値のないノード（例図中の灰色の円）を挿入します。

例えば，以下の図のようにP1, P2, P3, P4が既に挿入された状態で，P5を挿入する例を考えます。

挿入場所の深さはプレフィックス長+1なので，P5は深さ6に挿入されます。 検索アルゴリズムと同じ手順で挿入場所を探索します。 この例では，深さ3から4への探索で空のノードに到達するため，値のないノード（灰色の円）を追加します。 このようにして，下図のようにP5が挿入できます。

Radix treeからのノードの削除も単純です。 単純にプレフィックス情報に対応するノードの値を削除するだけです。 削除するノードの子ノードが空の場合は，再帰的に子ノードおよび値のない親ノードを削除できます。

例えば，上図の5エントリの例からP5を削除する場合を考えます。 まず，ノードhの値を削除します。するとノードhは子ノードも値も持たないノードになるので，ノードh自体を削除できます。 次に，削除したノードhの親ノードに対しても再帰的にノードの削除を試みます。 ノードgとノードfは再帰的にノードを削除すると，子ノードも値も持たないノードになるので，これらのノードは削除されます。