二分トライ木
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/02 06:29 UTC 版)
「トライ (データ構造)」の記事における「二分トライ木」の解説
二分トライ木（英: binary trie）やビット単位トライ木（英: bitwise trie）とは、整数を格納するトライ木で、上位ビットから 0 また 1 で左右に分岐する。 高速化のためのテクニックとして、下記の２つの方法が使える。 葉ノードは子が無く、子を指すポインタが空くので、葉ノード同士を双方向連結リストでつないでしまう。前後のノードを O(1) でたどれるようになる。 jumpポインタをノードに付け、一気に葉ノードまでジャンプする。
※この「二分トライ木」の解説は、「トライ (データ構造)」の解説の一部です。
「二分トライ木」を含む「トライ (データ構造)」の記事については、「トライ (データ構造)」の概要を参照ください。
ウィキペディア小見出し辞書の「二分トライ木」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 二分トライ木のページへのリンク
