y-高速トライ木
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/02 06:29 UTC 版)
「トライ (データ構造)」の記事における「y-高速トライ木」の解説
y-高速トライ木（英: y-fast trie）とは、格納する整数が w ビットの時、x-fast trie に全体の 1/w だけしか格納せず、残りを Treap などの平衡2分探索木に O(w) 個ずつに分けて入れる。これにより全体の空間計算量が、実際に木に格納されたデータの数 n に対し O(n) となり、x-高速トライ木より改善する。また、追加・削除の時間計算量が O(log w) になる。1982年に Dan E. Willard が x-fast trie と同時に発表した。
※この「y-高速トライ木」の解説は、「トライ (データ構造)」の解説の一部です。
「y-高速トライ木」を含む「トライ (データ構造)」の記事については、「トライ (データ構造)」の概要を参照ください。
ウィキペディア小見出し辞書の「y-高速トライ木」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- y-高速トライ木のページへのリンク
