1

CLRSアルゴリズムの本で概説されているように、Javaでインターバルツリーを実装しました（基本的な構造として赤黒ツリーを使用します）。この本では (そして私がオンラインで見た限りでは)、間隔にクエリ対象の番号が含まれるノードを見つける方法について説明しています。

私の場合、照会された数値がどの間隔にも当てはまらない場合、「最も近い」ノード、つまり間隔がクエリの直前と直後にあるノードを知りたいと考えています。次の関数を使用してこれを達成しました。各ノードには、間隔 (int low、int high) と、それ自体とそのサブツリーの最小値と最大値が含まれています。

public Node[] findPrevNext(int query) {
    if (tree.root.isNull())
        return null;
    else {
        Node prev = findPrev(query, tree.root, new Node());
        Node next = findNext(query, tree.root, new Node());
        Node[] result = {prev, next};
        return result;
    }
}

private Node findPrev(int query, Node x, Node prev) {
    if (x.interval.high < query && x.interval.high > prev.interval.high)
        prev = x;
    if (!x.left.isNull())
        prev = findPrev(query, x.left, prev);
    if (!x.right.isNull())
        prev = findPrev(query, x.right, prev);
    return prev;
}

private Node findNext(int query, Node x, Node next) {
    if (x.interval.low > query && x.interval.low < next.interval.low)
        next = x;
    if (!x.left.isNull())
        next = findNext(query, x.left, next);
    if (!x.right.isNull())
        next = findNext(query, x.right, next);
    return next;
}

もちろん問題は、関数 findPrev() と findNext() の両方がツリー全体をトラバースし、ツリーの構造を利用していないことです。このクエリを O(lgn) 時間で実行する方法はありますか?

また、すべてのインターバル ギャップを含む 2 つ目のインターバル ツリーを作成し、そこでクエリを実行する可能性も検討しました。ノードには、そのギャップの前後にある要素に関する情報が含まれます（私は試みましたが、これを実装することにまだ成功していません）。

編集:関数 findPrevNext() は、クエリの検索に失敗した後に呼び出されます。そのため、クエリは事前に特定の間隔に収まらないことがわかっています。

4

2 に答える 2

1

間隔は下端点によって順序付けられているため、上記は簡単です。間隔 [クエリ、クエリ] が存在する穴から開始して、左の子から親に到達するまでツリーを上ります。その親が目的のノードです。

以下は、最大フィールドの検査が必要なようです。クエリの下の間隔のみを含むサブツリー (つまり、下端点がクエリよりも低いもの) が与えられた場合、ノードが最大値 max を持つパスを下降することにより、最も近い下の候補を 1 つ抽出できます。O(log n) 個の最大のそのようなサブツリーがあり、左に行くことを検討したがそうしなかった検索アルゴリズムのたびに 1 つです。元の検索パスの O(log n) ノードも確認する必要があります。単純に、このアイデアは O(log 2 n) 時間アルゴリズムにつながりますが、各ノードでそのノードの最大値に等しい高さの間隔へのポインターを維持すると、O(log n) 時間アルゴリズムが得られます。 .

于 2013-05-15T04:10:02.567 に答える
0

TreeMap赤黒ツリーを実装するJavaは、メソッドheadMapおよびtailMapを実装します。これらのメソッドは、マップのクエリ ポイントより小さい部分 ( の場合headMap) またはクエリ ポイントより大きい部分 ( の場合) を返しますtailMap。ツリーにこれらのメソッドに似たものを実装すると、クエリ ポイントから線形トラバーサルを実行して、ツリー全体をトラバースするのではなく、N 個の最も近い間隔を見つけることができます。

于 2013-05-14T20:46:36.780 に答える