辞書を表すデータ構造を考案するように依頼されました。ディクショナリには、個別のキー番号を持つアイテムが保持されます。データ構造は、O(1) 時間で次の操作をサポートする必要があります: insert(x)、delete(x)、findMin()、findMax()、successor(x)、predecessor(x)。また、search(x) 操作は O(log n) 時間で行う必要があります。
課題は、スキップ リスト、ハッシュ テーブル、およびヒープに関するものでした。最適な構造はスキップ リストになると思いますが、O(1) tine で挿入と削除を実装する方法が見つかりませんでした。助言がありますか？
ハッシュ テーブルとスキップ リストの両方のデータ構造を使用する必要があります。要素を挿入するたびにminと の値を更新できます。maxしたがって、findMin()とfindMax()もO(1)です。また、一定時間内に
insert()あります。delete()
ところで、アイテムを検索する前にアイテムを削除することはできません。で検索するとO(logn)、delete()がO(logn)自動的に表示されます。
ハッシュ テーブルは (正しく実装されている場合)、検索、削除、および挿入を提供しO(1)ます。残りの操作 ( successor()、predecessor()) は、スキップ リストで使用できます。