random - ランダム化せずにリストをスキップしますか?

Question

だから私はスキップリストについて少し読んで、現在それを実装しています. しかし、これまで本当に得られなかったことが 1 つあります。スキップ リストがランダム化されるのはなぜですか? 私が見つけたすべての情報源で、スキップ リストは乱数を使用してアイテムが挿入されるレベルを決定していました。最適値を計算できませんでしたか? それとも、「4 つおきの項目」を上のレベルに挿入する必要があると言えませんか?

Answer 1

スキップ リストは、たとえば償却アクセス コストを最小限に抑えるために、決定論的に構築できます。ただし、決定論的な構築方法では、上位レベルのリストエントリのセットは常に既知であるため、パフォーマンスをO(n)に低下させる「敵対的な」削除操作のセットを構築するのは簡単です。ランダム化された構成では、最悪のケースの削除のセットがまだありますが、かなり大きなリストの場合、最悪のケースの削除シーケンスが偶然に見つかる可能性はほとんどありません.