java实现一个区间树（Interval Tree）支持快速查询。

  • mingtian66

    2025-05-14 15:30:19
  • Java
  • 原创

区间树（Interval Tree）是一种增强型的二叉搜索树，专门用于存储区间并支持快速查询，比如查找与给定区间重叠的所有区间。区间树通常使用红黑树或 AVL 树作为底层结构，以确保树的平衡性。

下面是一个使用 Java 实现的简单区间树示例，支持插入区间和查询与给定区间重叠的区间。为了简化实现，我们将使用基本的二叉搜索树结构，不实现自平衡（如红黑树或 AVL 树）以保持代码简洁。在实际应用中，建议使用自平衡树来确保性能。

javaCopy Codeimport java.util.ArrayList;import java.util.List;class Interval {    int low, high;    public Interval(int low, int high) {        this.low = low;        this.high = high;
    }
}class IntervalTreeNode {
    Interval interval;    int max; // 最大高值，用于优化查询
    IntervalTreeNode left, right;    public IntervalTreeNode(Interval interval) {        this.interval = interval;        this.max = interval.high;        this.left = null;        this.right = null;
    }
}class IntervalTree {    private IntervalTreeNode root;    public IntervalTree() {        this.root = null;
    }    public void insert(Interval interval) {
        root = insert(root, interval);
    }    private IntervalTreeNode insert(IntervalTreeNode node, Interval interval) {        if (node == null) {            return new IntervalTreeNode(interval);
        }        // 根据区间的低值进行插入
        if (interval.low < node.interval.low) {
            node.left = insert(node.left, interval);
        } else {
            node.right = insert(node.right, interval);
        }        // 更新当前节点的最大高值
        node.max = Math.max(node.max, interval.high);        return node;
    }    public List search(Interval interval) {
        List result = new ArrayList<>();
        search(root, interval, result);        return result;
    }    private void search(IntervalTreeNode node, Interval interval, List result) {        if (node == null) {            return;
        }        // 如果当前节点的区间与给定区间重叠，则加入结果
        if (overlap(node.interval, interval)) {
            result.add(node.interval);
        }        // 如果左子树的最大高值大于等于给定区间的低值，则递归搜索左子树
        if (node.left != null && node.left.max >= interval.low) {
            search(node.left, interval, result);
        }        // 递归搜索右子树
        search(node.right, interval, result);
    }    private boolean overlap(Interval i1, Interval i2) {        return i1.low <= i2.high && i2.low <= i1.high;
    }    public static void main(String[] args) {        IntervalTree tree = new IntervalTree();
        tree.insert(new Interval(15, 20));
        tree.insert(new Interval(10, 30));
        tree.insert(new Interval(17, 19));
        tree.insert(new Interval(5, 20));
        tree.insert(new Interval(12, 15));
        tree.insert(new Interval(30, 40));
        List result = tree.search(new Interval(14, 16));
        System.out.println("Overlapping intervals:");        for (Interval interval : result) {
            System.out.println("[" + interval.low + ", " + interval.high + "]");
        }
    }
}

代码说明

  1. ‌ Interval 类‌：表示一个区间，包含低值  low 和高值  high。

  2. ‌ IntervalTreeNode 类‌：表示区间树的节点，包含一个区间对象  interval 和一个  max 属性，用于存储以该节点为根的子树中所有区间的最大高值。

  3. ‌ IntervalTree 类‌：

    • insert 方法：根据区间的低值插入新区间，并更新节点的  max 值。
    • search 方法：查找与给定区间重叠的所有区间。利用  max 值优化搜索，避免不必要的遍历。
    • overlap 方法：判断两个区间是否重叠。

  4. ‌ 主方法‌：创建一个区间树，插入一些区间，并查询与给定区间重叠的区间。

优化建议

  • ‌ 自平衡树‌：为了实现更好的性能，可以使用红黑树或 AVL 树来保持树的平衡。
  • ‌ 更多优化‌：在插入和查询时，可以进一步优化以处理更多边界情况，比如完全相同的区间等。

这个实现提供了一个基本的区间树结构，适用于学习和理解区间树的基本原理。


http://travel.zgjzs.org

http://hotel.zgjzs.org

http://food.zgjzs.org

http://tech.zgjzs.org

http://health.zgjzs.org

http://edu.zgjzs.org

http://music.zgjzs.org

http://sports.zgjzs.org

http://fashion.zgjzs.org

http://auto.zgjzs.org

http://finance.zgjzs.org

http://law.zgjzs.org

http://art.zgjzs.org

http://book.zgjzs.org

http://movie.zgjzs.org

http://game.zgjzs.org

http://job.zgjzs.org

http://house.zgjzs.org

http://kids.zgjzs.org

http://pet.zgjzs.org

http://beauty.zgjzs.org

http://garden.zgjzs.org

http://science.zgjzs.org

http://history.zgjzs.org

http://culture.zgjzs.org

http://city.zgjzs.org

http://weather.zgjzs.org

http://map.zgjzs.org

http://data.zgjzs.org

http://energy.zgjzs.org

http://eco.zgjzs.org

http://farm.zgjzs.org

http://market.zgjzs.org

http://trade.zgjzs.org

http://service.zgjzs.org

http://club.zgjzs.org

http://event.zgjzs.org

http://festival.zgjzs.org

http://expo.zgjzs.org

http://museum.zgjzs.org

http://library.zgjzs.org

http://school.zgjzs.org

http://hospital.zgjzs.org

http://bank.zgjzs.org

http://insurance.zgjzs.org

http://stock.zgjzs.org

http://invest.zgjzs.org

http://tour.zgjzs.org

http://electronics.shangpin.org

http://clothing.shangpin.org

http://furniture.shangpin.org

http://jewelry.shangpin.org

http://cosmetic.shangpin.org

http://digital.shangpin.org

http://appliance.shangpin.org

http://outdoor.shangpin.org

http://sporting.shangpin.org

http://luxury.shangpin.org

http://grocery.shangpin.org

http://office.shangpin.org

http://tool.shangpin.org

http://craft.shangpin.org

http://antique.shangpin.org

http://collectible.shangpin.org

http://handmade.shangpin.org

http://organic.shangpin.org

http://baby.shangpin.org

http://watch.shangpin.org

http://bag.shangpin.org

http://shoe.shangpin.org

http://glass.shangpin.org

http://ceramic.shangpin.org

http://textile.shangpin.org

http://metal.shangpin.org

http://wood.shangpin.org

http://stone.shangpin.org

http://plastic.shangpin.org

http://paper.shangpin.org

http://ink.shangpin.org

http://paint.shangpin.org

http://lighting.shangpin.org

http://kitchen.shangpin.org

http://bath.shangpin.org

http://bed.shangpin.org

http://sofa.shangpin.org

http://carpet.shangpin.org

http://curtain.shangpin.org

http://lamp.shangpin.org

http://mirror.shangpin.org

http://clock.shangpin.org

http://vase.shangpin.org

http://frame.shangpin.org

http://toy.shangpin.org

http://instrument.shangpin.org

http://plant.shangpin.org

http://gift.shangpin.org

http://business.snjrw.org

http://media.snjrw.org

http://design.snjrw.org

http://photo.snjrw.org

http://video.snjrw.org

http://studio.snjrw.org

http://network.snjrw.org

http://cloud.snjrw.org

http://career.snjrw.org

http://learning.snjrw.org

http://research.snjrw.org

http://innovation.snjrw.org

http://project.snjrw.org

http://solution.snjrw.org

http://global.snjrw.org

http://local.snjrw.org

http://china.snjrw.org

http://asia.snjrw.org

http://europe.snjrw.org

http://america.snjrw.org

http://africa.snjrw.org

http://ocean.snjrw.org

http://space.snjrw.org

http://earth.snjrw.org

http://nature.snjrw.org

http://green.snjrw.org

http://future.snjrw.org

http://ai.snjrw.org

http://robot.snjrw.org

http://vr.snjrw.org

http://ar.snjrw.org

http://iot.snjrw.org

http://blockchain.snjrw.org

http://crypto.snjrw.org

http://nft.snjrw.org

http://metaverse.snjrw.org

http://smart.snjrw.org

http://safe.snjrw.org

http://privacy.snjrw.org

http://security.snjrw.org

http://trust.snjrw.org

http://quality.snjrw.org

http://certified.snjrw.org

http://premium.snjrw.org

http://elite.snjrw.org

http://vip.snjrw.org

http://prime.snjrw.org

http://gold.snjrw.org

请使用浏览器的分享功能分享到微信等