TreeSet and TreeMap: Sorted and Fast

TreeSet: a sorted set

TreeSet keeps its items sorted and has no repeats. Add, remove and contains are O(log n). Its superpower is asking for neighbours:

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> busStops = new TreeSet<Integer>();
        int[] km = {12, 3, 25, 18, 7};
        for (int k : km) busStops.add(k);
        System.out.println(busStops);                         // always sorted

        int me = 15;
        System.out.println("stop at or before me: " + busStops.floor(me));
        System.out.println("stop at or after me:  " + busStops.ceiling(me));
        System.out.println("first and last: " + busStops.first() + " " + busStops.last());
        System.out.println("stop after 25: " + busStops.higher(25));   // null: none
    }
}

Output

[3, 7, 12, 18, 25]
stop at or before me: 12
stop at or after me:  18
first and last: 3 25
stop after 25: null

TreeMap: a sorted map

TreeMap is a HashMap whose keys stay sorted – great when you need to print in order or find the nearest key:

import java.util.Map;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, String> grade = new TreeMap<Integer, String>();
        grade.put(90, "A");
        grade.put(75, "B");
        grade.put(60, "C");
        grade.put(0, "F");

        int[] marks = {95, 75, 61, 42};
        for (int m : marks) {
            Map.Entry<Integer, String> e = grade.floorEntry(m);   // the band this mark falls into
            System.out.println(m + " -> " + e.getValue());
        }
    }
}

Output

95 -> A
75 -> B
61 -> C
42 -> F

Remember: Need fast lookups and don't care about order? HashMap/HashSet, O(1). Need sorted order or “nearest”? TreeMap/TreeSet, O(log n).

Common mistake: floor and ceiling return null when there is no such item. Storing that in an int crashes with NullPointerException – check for null first.