x-高速トライ木
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/02 06:29 UTC 版)
「トライ (データ構造)」の記事における「x-高速トライ木」の解説
x-高速トライ木（英: x-fast trie）は、検索キーとして与えられた整数以上(以下)の値をもつ、キーに最も近い葉ノードを得る操作(successor, predecessor)を高速にできるようにした二分トライ木のバリエーションである。通常の二分トライ木との相違点は、階層高さごとのハッシュテーブル、葉ノード同士の双方向連結リスト、中間ノードが子ノードを0側(1側)のひとつしか持たない時に格納される、その中間ノード下で最大(最小)値をもつ葉ノードへのリンク(descendant pointer)を持つことである。。階層にたいして二分探索をおこなうことで、木に格納する整数のビット数 w に対し、Successor, Predecessorの時間計算量がO(log w)となる。1982年に Dan E. Willard が発表した。
※この「x-高速トライ木」の解説は、「トライ (データ構造)」の解説の一部です。
「x-高速トライ木」を含む「トライ (データ構造)」の記事については、「トライ (データ構造)」の概要を参照ください。
ウィキペディア小見出し辞書の「x-高速トライ木」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- x-高速トライ木のページへのリンク
