データ構造

【でーたこうぞう (data structure)】

与えられたデータを, 計算の高速化のために構造をもたせて記憶する手法の総称. 目的に合わせ, あるいくつかの機能を, 高速, あるいは省メモリで行えるよう設計される. 例えば, ある言葉を $n\,$ 個の言葉の辞書データから検索するとき, 通常の配列では, 最悪で挿入・削除に $O(n)\,$ , 検索に $O(\log n)\,$ か, 挿入と削除に $O(1)\,$ , 検索に $O(n)\,$ の時間を要する. 二分探索木というデータ構造は, これらの機能を $O(\log n)\,$ 時間で行い, 使用メモリは $O(n)\,$ である.