Red Black Tree

TreeMap in Java

http://javahungry.blogspot.com/2014/06/how-treemap-works-ten-treemap-java-interview-questions.html

TreeSet in Java

http://javahungry.blogspot.com/2015/10/how-treeset-works-internally-in-java-interview-questions.html

TreeSet

683. K Empty Slots

TreeSet can help to maintain an ordered set. With .higher(x) and .lower(x), we can get the predecessor and successor of x.

.higher()

.lower()

.addAll(list)

.add()

.first() //but set doesn't have the first() method, has to use iterator

.pollFirst()

.descendingIterator()

class Solution {
    public int kEmptySlots(int[] flowers, int k) {

        TreeSet<Integer> boomPosSet = new TreeSet<>();
        for(int i=0; i<flowers.length; i++) {
            int currBoomPos = flowers[i];
            Integer higher = boomPosSet.higher(currBoomPos);
            if(higher!=null && higher - currBoomPos - 1 == k)
                return i+1;
            Integer lower = boomPosSet.lower(currBoomPos);
            if(lower!=null && currBoomPos - lower - 1 == k)
                return i+1;

            boomPosSet.add(currBoomPos);
        }

        return -1;
    }
}

TreeMap

It is just like HashMap but the <key, value> pairs are ordered by key value, so that we can find the floorKey and ceilingKey of a given key. It is useful when we deal with intervals.

.values are arranged in the order of their keys.

TreeMap<Integer, Integer> activeHeights = new TreeMap<>(Collections.reverseOrder());
activeHeights.firstEntry().getKey();

729. My Calendar I

class MyCalendar {
    TreeMap<Integer, Integer> calendar;


    public MyCalendar() {
        calendar = new TreeMap<>();
    }

    public boolean book(int start, int end) {
        Integer floorKey = calendar.floorKey(start);
        if(floorKey!=null && calendar.get(floorKey)>start) return false;
        Integer ceilingKey = calendar.ceilingKey(start);
        if(ceilingKey!=null && ceilingKey<end) return false;
        calendar.put(start, end);
        return true;
    }
}

Get subMap of it

NavigableMap<String, List<Integer>> resMap = logs.subMap(s, true, e, true); //true means inclusive