区间树算法实现

Question

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

寻找重叠的算法如下：

间隔重叠IntervalSearch(root, x)

1. 如果 x 与根的区间重叠，则返回根的区间。

2. 如果 root 的左孩子不为空且左孩子中的最大值大于 x 的低值，则对左孩子重复

3. 否则右孩子会重复出现。

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

max 需要找到重叠，例如使用此数据

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

并搜索

24