7

次のプロパティを使用して、閉じた間隔で効率的に動作するデータ構造を探しています。

  • 間隔を動的に追加または削除する

  • 各間隔の数値 (「深さ」) を設定し、いつでも変更できます。同じ深さは 2 つとありません

  • 「深さ」でソートされた、特定の間隔と重なるすべての間隔を見つける

私が見つけた最も近い構造は間隔ツリーですが、見つかった間隔を深さに関して任意の順序でリストしています。報告されたすべての「ソートされていない」間隔を収集し、後でソートすることはできましたが、すべてのクエリの結果をソートすることを避けることができました。

誰かがそのようなデータ構造を知っているか、またはそのようなソートをサポートするために間隔ツリーを拡張する方法 (可能な場合) を提案していますか?

例：

  1. [1,2] を空の構造に追加し、その深さを 1 に設定します
  2. [10,100] を追加、深さ = 2
  3. [5,55] を追加、深さ = 3
  4. [5,50] レポート [10,100] および [5,55] のクエリ
  5. [10,100] の深さを 3 に、[5,55] の深さを 2 に設定します。
  6. [5,50] レポート [5,55] および [10,100] のクエリ

編集

深さの更新よりも、高速な追加/削除とクエリに興味があります。深さは、他の操作の高速化に役立つ場合、O(n) までかかる場合があります。

4

4 に答える 4

5

必要なアルゴリズムが存在すると仮定しましょう。次に、ランダムな深さを持つ 100 万個の間隔のセットを作成し、[1, 1]それらをそのような間隔ツリーに挿入します。次に、 interval をクエリしましょう[1, 1]。すべての間隔を複雑さで並べ替えられた順序で返す必要がありますO(M + log N)が、要素N = 1のセットをM線形時間で並べ替えています。

言い換えれば、間隔ツリーから要素を取得した後で要素を深さでソートすることは、理論的に可能であるだけでなく、複雑さの点でも優れています。

于 2015-02-18T07:00:23.743 に答える
1

基本的にバイナリツリーであるTreeMapを使用したJavaでの私のソリューションは次のとおりです

テスト: http://ideone.com/f0OlHI

複雑

     Insert : 2 * O(log n)

     Remove : 2 * O(log n)

     Search : 1 * O(log n)

ChangeDepth : 7 * O(log n)

findOverlap : O(n)

間隔データセット.java

class IntervalDataSet
{
    private TreeMap<Integer,Interval> map;

    public IntervalDataSet ()
    {
        map = new TreeMap<Integer,Interval> ();
    }

    public void print ()
    {
        for(Map.Entry<Integer,Interval> entry : map.entrySet())
        {
          Integer key = entry.getKey();
          Interval value = entry.getValue();

          System.out.println(key+" => ["+value.min+","+value.max+"] ");
        }
    }

    public boolean changeDepth (int depth, int newDepth)
    {
        if (!map.containsKey(depth)) return false;

        if (map.containsKey(newDepth)) return false;

        Interval in = map.get(depth);

        in.depth = newDepth;

        remove(depth); insert(in);

        return true;
    }

    public boolean insert (Interval in)
    {
        if (in == null) return false;

        if (map.containsKey(in.depth)) return false;

        map.put(in.depth, in); return true;
    }

    public boolean remove (int depth)
    {
        if (!map.containsKey(depth)) return false;

        map.remove(depth); return true;
    }

    public Interval get (int depth)
    {
        return map.get(depth);
    }

    public void print (int depth)
    {
        if (!map.containsKey(depth))
          System.out.println(depth+" => X ");
        else
          map.get(depth).print();
    }

    public void printOverlappingIntervals (Interval in)
    {
        for (Interval interval : map.values())
            if (interval.intersect(in))
                interval.print();
    }

    public ArrayList<Interval> getOverlappingIntervals (Interval in)
    {
        ArrayList<Interval> list = new ArrayList<Interval>();

        for (Interval interval : map.values())
            if (interval.intersect(in))
                list.add(interval);

        return list;
    }

    public int size ()
    {
        return map.size();
    }

}

間隔.java

class Interval
{
    public int min;
    public int max;
    public int depth;

    public Interval (int min, int max, int depth)
    {
        this.min = min;
        this.max = max;
        this.depth = depth;
    }

    public boolean intersect (Interval b)
    {
        return (b != null
            && ((this.min >= b.min && this.min <= b.max)
                || (this.max >= b.min && this.max <= b.max))
            );
    }

    public void print ()
    {
        System.out.println(depth+" => ["+min+","+max+"] ");
    }
}

テスト.java

class Test
{
  public static void main(String[] args) 
  {
    System.out.println("Test Start!");
    System.out.println("--------------");

    IntervalDataSet data = new IntervalDataSet ();

    data.insert(new Interval( 1,3, 0 ));
    data.insert(new Interval( 2,4, 1 ));
    data.insert(new Interval( 3,5, 3 ));
    data.insert(new Interval( 4,6, 4 ));
    System.out.println("initial values");
    data.print();

    System.out.println("--------------");
    System.out.println("Intervals overlapping [2,3]");

    data.printOverlappingIntervals(new Interval( 2,3, -1 ));
    System.out.println("--------------");

    System.out.println("change depth 0 to 2");
    data.changeDepth( 0, 2 );
    data.print();
    System.out.println("--------------");

    System.out.println("remove depth 4");
    data.remove( 4 );
    data.print();
    System.out.println("--------------");

    System.out.println("change depth 1 to 4");
    data.changeDepth( 1, 4 );
    data.print();
    System.out.println("--------------");

    System.out.println("Test End!");
  }
}

間隔データセット 2

複雑

initialization : O(n)

   findOverlap : 2 * O(log n) + T(merge)

class IntervalDataSet2
{
    private Integer [] key;
    private TreeMap<Integer,Interval> [] val;
    private int min, max, size;

    public IntervalDataSet2 (Collection<Interval> init)
    {
        TreeMap<Integer,TreeMap<Integer,Interval>> map
            = new TreeSet<Integer,TreeMap<Integer,Interval>> ();

        for (Interval in : init)
        {
            if (!map.containsKey(in.min))
                map.put(in.min,
                    new TreeMap<Integer,Interval> ());

            map.get(in.min).put(in.depth,in);

            if (!map.containsKey(in.max))
                map.put(in.max,
                    new TreeMap<Integer,Interval> ());

            map.get(in.max).put(in.depth,in);
        }

        key = new Integer [map.size()];
        val = new TreeMap<Integer,Interval> [map.size()];

        int i = 0;
        for (Integer value : map.keySet())
        {
            key [i] = value;
            val [i] = map.get(value);
            i++ ;
        }

        this.size = map.size();
        this.min = key [0];
        this.max = key [size-1];

    }

    private int binarySearch (int value, int a, int b)
    {
        if (a == b)
            return a;

        if (key[(a+b)/2] == value)
            return ((a+b)/2);

        if (key[(a+b)/2] < value)
            return binarySearch(value, ((a+b)/2)+1, b);
        else
            return binarySearch(value, (a, (a+b)/2)-1);
    }

    public TreeMap<Integer,Interval> findOverlap (Interval in)
    {
        TreeMap<Integer,Interval> solution
            = new TreeMap<Integer,Interval> ();

        int alpha = in.min;
        int beta = in.max;

        if (alpha > this.max || beta < this.min)
            return solution;

        int i = binarySearch(alpha, 0,(size-1));
        int j = binarySearch(beta, 0,(size-1));

        while (alpha <= beta && key[i] < alpha) i++;
        while  (alpha <= beta && key[j] > beta) j--;

        for (int k = i; k <= j; k++)
            solution.addAll ( val[k] );

        return solution;
    }

}
于 2015-02-24T10:05:16.553 に答える