面试题：Java TreeSet在复杂范围查询场景下的优化

Question

给定一个TreeSet，里面存储了大量自定义的类对象，这些类实现了Comparable接口。现在需要进行一个复杂的范围查询：根据对象的某个属性值，查询出在两个给定值之间的对象，并且要求查询效率尽可能高。请阐述你会采取的优化策略，并且给出核心代码片段（可以使用伪代码辅助说明）。

Answer 1

优化策略

1. 利用Comparable接口排序特性：由于TreeSet使用了Comparable接口进行排序，在进行范围查询时，可利用其有序性。
2. 使用二分查找思想：避免全量遍历，通过二分查找找到范围的起始和结束位置，减少不必要的比较。

核心代码片段（Java示例）

假设自定义类为CustomClass，具有属性property用于范围查询。

import java.util.TreeSet;

public class Main {
    static class CustomClass implements Comparable<CustomClass> {
        private int property;

        public CustomClass(int property) {
            this.property = property;
        }

        public int getProperty() {
            return property;
        }

        @Override
        public int compareTo(CustomClass o) {
            return Integer.compare(this.property, o.property);
        }
    }

    public static CustomClass[] rangeQuery(TreeSet<CustomClass> treeSet, int min, int max) {
        // 利用subSet方法获取范围内的子集
        TreeSet<CustomClass> subSet = (TreeSet<CustomClass>) treeSet.subSet(new CustomClass(min), true, new CustomClass(max), true);
        return subSet.toArray(new CustomClass[0]);
    }

    public static void main(String[] args) {
        TreeSet<CustomClass> treeSet = new TreeSet<>();
        treeSet.add(new CustomClass(1));
        treeSet.add(new CustomClass(3));
        treeSet.add(new CustomClass(5));
        treeSet.add(new CustomClass(7));
        treeSet.add(new CustomClass(9));

        CustomClass[] result = rangeQuery(treeSet, 3, 7);
        for (CustomClass obj : result) {
            System.out.println(obj.getProperty());
        }
    }
}

伪代码解释

1. 定义CustomClass类：实现Comparable接口，重写compareTo方法，根据property属性进行比较。
2. rangeQuery方法：
   • 使用subSet方法从TreeSet中获取满足范围条件的子集。subSet方法第一个参数是范围起始对象（包含），第二个参数表示是否包含起始对象，第三个参数是范围结束对象（包含），第四个参数表示是否包含结束对象。
   • 将子集转换为数组返回。
3. main方法：构建TreeSet并添加对象，调用rangeQuery方法进行范围查询并输出结果。