アプリケーションと関連するデータ構造
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/01 09:37 UTC 版)
「赤黒木」の記事における「アプリケーションと関連するデータ構造」の解説
赤黒木は挿入時間、削除時間、探索時間において、最悪のケースを保証する。これはリアルタイムシステムのような時間センシティブなアプリケーションにおいて価値あるのみならず、最悪のケースを保証する他のデータ構造における価値ある部品となっている。 例えば、計算幾何学で用いられる多くのデータ構造は赤黒木をベースとしているし、現行のLinuxカーネルで用いられる CFS （Completely Fair Scheduler）では赤黒木を使用している。 AVL木は O ( log n ) {\displaystyle {\mathcal {O}}(\log n)} の探索、挿入、削除をサポートする、もう一つのデータ構造である。AVL木は、赤黒木よりも厳密な平衡性を持っているため、挿入や削除は遅くなるが、検索は早くなる。このため、AVL木は一度構築して、再構成する必要のないデータ構造にとっては魅力的である。例えば、言語辞書（または、アセンブラやインタープリタの命令コードのようなプログラム辞書）などのように。 また、赤黒木はAVL木よりも条件が多いため、実装が面倒である。 赤黒木はまた、最も一般的な永続データ構造のひとつであり、関数型言語で特に価値がある。変化後に前のバージョンを保持できるように、連想配列や集合 (プログラミング)を構築するのに使われる。赤黒木の永続バージョンは、各挿入や各削除において O ( log n ) {\displaystyle {\mathcal {O}}(\log n)} の（時間に加えて）空間を要する。
※この「アプリケーションと関連するデータ構造」の解説は、「赤黒木」の解説の一部です。
「アプリケーションと関連するデータ構造」を含む「赤黒木」の記事については、「赤黒木」の概要を参照ください。
- アプリケーションと関連するデータ構造のページへのリンク
