区间树算法实现

Question

我最近在 http://www.geeksforgeeks.org/interval-tree/ 上完成了区间树的实现，这里算法建议在每个子树上使用最大值。

寻找重叠的算法如下：

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.

我不明白的是为什么要使用最大值，也可以通过比较间隔来获得 LOG(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;
    }
}

Answer 1

需要最大值才能找到重叠，例如使用此数据

 {{15, 20}, {10, 11}, {17, 22}, {5, 20}, {12, 25}, {30, 40}};

并搜索 24

区间树算法实现

Interval Tree algorithm inplementation

tree

binary-search-tree