09/04/01 00:12:16
たとえばABC,ADE,ABDの三要素のトライ木を書くとこんなかんじ
A-B-C
| |-D
|
|-D-E
左端のAが木のトップで右側が子要素な。
親から末端ノードまでの要素を連結すると登録した要素になる。
ツリーの深さはキー長に比例するけど1回辺りの比較が超軽いのが特徴。
これを改良したのにパトリシア木とかあるけど詳細は略
09/04/01 00:12:16
たとえばABC,ADE,ABDの三要素のトライ木を書くとこんなかんじ
A-B-C
| |-D
|
|-D-E
左端のAが木のトップで右側が子要素な。
親から末端ノードまでの要素を連結すると登録した要素になる。
ツリーの深さはキー長に比例するけど1回辺りの比較が超軽いのが特徴。
これを改良したのにパトリシア木とかあるけど詳細は略