algorithm - ソートされた値のソートされたキーを生成する

Question

キーから文字列値へのマッピングと、値からキーへのマッピングを維持する必要があります。これらのリストの両方が常にソートされていることを確認する必要があります。新しい値はいつでもリストに追加できます。新しい値が追加されたときに、多くのキーを再生成したり、不均衡なツリーになってしまうことなく、2 つの並べ替えられたリストを維持できるようにするために使用する最適なデータ構造は何ですか?

Answer 1

これは、「この問題では、ラベルがリスト全体で単調になり、任意の場所で挿入および削除されるように、各ノードに明示的なラベルを付けてリンクされたリストを維持することが最終的な目標です」と説明できますか?

これはhttp://courses.csail.mit.edu/6.897/spring05/lec/lec24.pdfのセクション 3 です。これらは、キーのテーブルを暗黙的なツリー構造として表示することにより、キーのテーブルをギャップのあるソート順で維持する方法を示しています。テーブルのセクション内のキーを再編成することは、サブツリーのバランスを再調整することと同じです。