2
나는 최근에 간격 트리의 구현을 통해 http://www.geeksforgeeks.org/interval-tree/에 갔는데, 여기서 알고리즘은 각 하위 트리에서 최대 값을 사용하도록 제안합니다.간격 트리 알고리즘 inplementation
그리고 중복을 찾기위한 너 한테는 다음과 같이이다 :이 로그를 얻을 수도 간격을 비교하여 수행 할 수있는 최대 값, 을 사용하는 이유 이해가 안 무엇
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.
이다 (N) 결과.
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 태그를 추가해야합니다 ... 어떤 경우이든, 그 그림을 보았습니까? 최대 값 *이 해당 간격에 포함될 필요는 없음을 알 수 있습니다. 예를 들어, 루트는'[15, 20]'간격이지만 최대 값은'40 '이므로 루트 간격만으로는 그 정보를 복구 할 수 없습니다. – Bakuriu