値が任意の実数であるキーと値のペアの大規模なコレクションがあるとします。次の操作をサポートするデータ構造の作成に関心があります。
このデータ構造を使用して、たとえば、全国的なテスト スコアのストリームを受け取ったときに特定の学生がどのパーセンタイルにあるかを効率的に判断したり、サービスの質が異常に高い病院または低い病院を特定したりすることができます。
これらの操作を効率的に実行する方法はありますか (サブリニア時間など)。
このデータ構造を実装する 1 つの可能な方法は、順序統計ツリーとハッシュ テーブルのハイブリッドを使用することです。
順序統計ツリーは、バランス型二分探索ツリーの一種で、通常の二分探索ツリー操作に加えて、さらに 2 つの操作をサポートします。
順序統計ツリーは、ローテーション中に保持される追加情報を使用して、通常のバランスのとれた二分探索ツリー (赤/黒ツリーまたはAVL ツリーなど) を拡張することによって構築できます。このようにして、注文統計ツリーのすべての通常の BST 操作を O(log n) 時間で実行し、追加の操作も O(log n) 時間で実行できます。
ここで、キー/パーセンタイル スコアではなく、純粋に値のスコアを格納していたとします。この場合、次のようにパーセンタイル ルックアップを実装するのは非常に簡単です。すべての値を注文統計ツリーに格納します。特定の値のパーセンタイル スコアを決定するには、順序統計ツリーでランク操作を使用して、その値が表示されるインデックスを調べます。これにより、0 から n - 1 (n はツリー内の要素の数) の範囲の数値が得られ、順序統計ツリー内のそのスコアの位置が示されます。次に、必要に応じて、その数値に 99 / (n - 1) を掛けて、0 から 99 の範囲で実行される値のパーセンタイル スコアを取得できます。
パーセンタイルを超える最小値を決定するには、次のように選択操作を使用できます。0 ～ 99 のパーセンタイルが与えられた場合、そのパーセンタイルに 99 / (n - 1) を掛けて、0 ～ n - 1 の間の実数を取得します。その数の上限を取ると、0 から n - 1 までの範囲の自然数が生成されます。注文統計ツリーで選択操作を使用すると、指定されたパーセンタイル以上の範囲内の最初の値を見つけるために使用できます。
ただし、これらの操作は、キーと値のペアではなく、データ構造に純粋な値があることを前提としています。この操作をキーと値のペアで機能させるには、次のようにデータ構造を拡張します。
これら 2 つの変更により、データ構造に必要な機能を実装できるようになります。キーによるパーセンタイル ルックアップを実行するデータ構造を取得するには、まず、指定されたキーを使用してハッシュ テーブルにクエリを実行し、関連付けられた値をルックアップします。次に、前に行ったように、値に対してパーセンタイル ルックアップを行います。値が特定のパーセンタイル以上の最初のキーを示すデータ構造を取得するには、上記のように注文統計ツリーで通常のパーセンタイル検索操作を実行し、次に特定の値に関連付けられたキーを検索します。
ハッシュテーブルが連鎖ハッシュを使用すると仮定すると、各操作に必要な時間は次のようになります。
お役に立てれば！