2
Ich habe kürzlich die Implementierung von Interval Tree auf http://www.geeksforgeeks.org/interval-tree/ durchgelaufen. Hier schlägt der Algorithmus vor, einen maximalen Wert für jeden Teilbaum zu verwenden.Interval Tree Algorithmus Implementierung
Und die algo für Überlappung zu finden, ist wie:
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.
, was ich nicht verstehe, ist, warum ein Maximalwert verwenden, es kann auch durch einen Vergleich der Intervalle durchgeführt werden, um eine LOG zu erhalten (N) Ergebnis.
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;
}
}
kann auf unvollständigen Code nicht kommentieren, wie Knoten hinzugefügt und entfernt werden. – Jasen
Ich habe den Code aktualisiert, Einfügen ist dort, und ich habe noch nicht die Löschung implementiert. –
Ist das Java-Code? Dann musst du ** ein 'Java'-Tag hinzufügen ... Hast du das Bild auf jeden Fall gesehen? Sie können sehen, dass der Maximalwert * nicht * im Intervall enthalten sein muss. Zum Beispiel hat die Wurzel das Intervall '[15, 20]', aber den Maximalwert '40', so dass Sie diese Information nicht allein aus dem Wurzelintervall wiederherstellen können. – Bakuriu