2
私は最近、http://www.geeksforgeeks.org/interval-tree/のインターバルツリーの実装を行った。ここでアルゴリズムは各サブツリーで最大値を使用することを提案している。インターバルツリーアルゴリズムのインプリメンテーション
として重複を見つけるためのアルゴがある：LOG（N）を取得するためにも間隔を比較することによって行うことができる最大値を使用する理由
Interval overlappingIntervalSearch(root, x)
1) If x overlaps with root's interval, return the root's interval.
2) If left child of root is not empty and the max in left child
is greater than x's low value, recur for left child
3) Else recur for right child.
私は理解していないことで、 結果。
public class IntervalTree {
private Node ROOT;
private class Node {
Point data;
Node left, right;
public Node(Point data) {
this.data = data;
}
}
public static void main(String... args) throws IOException {
new IntervalTree().task();
}
private void task() {
insert();
Node pop = findInterval(ROOT, new Node(new Point(6,7)));
if (pop != null) System.out.println(pop.data.toString());
else System.out.println("No overlap");
}
private Node findInterval(Node root, Node node) {
if (root == null) return null;
if (overlap(root.data, node.data)) return root;
else if (node.data.x < root.data.x) return findInterval(root.left, node);
return findInterval(root.right, node);
}
private boolean overlap(Point one, Point two) {
return two.x <= one.y && one.x <= two.y;
}
private void insert() {
int data[][] = new int[][]{{15, 20}, {10, 30}, {17, 19}, {5, 20}, {12, 15}, {30, 40}};
for (int i = 0; i < data.length; i++)
ROOT = insert(data[i]);
}
private Node insert(int[] pt) {
return insert(ROOT, new Node(new Point(pt[0], pt[1])));
}
private Node insert(Node root, Node node) {
if (root == null) return node;
else if (node.data.x < root.data.x)
root.left = insert(root.left, node);
else root.right = insert(root.right, node);
return root;
}
}
の検索は、ノードを追加および削除されたか、不完全なコードにコメントすることはできません。 – Jasen
私はコードを更新しました、挿入があり、私はまだ削除を実装していません。 –
そのJavaコードですか？次に、** javaタグを追加する必要があります。いずれの場合でも、その画像を見ましたか？最大値*は区間に含まれる必要はないことがわかります。例えば、ルートは '[15,20]'で最大値は'40 'なので、ルート間隔だけからその情報を回復することはできません。 – Bakuriu