Navigating Treemap in Java

Treemap in java is A Red-Black tree-based NavigableMap implementation. NavigableMap interface provides some interesting methods to navigate the map. In this article, we will quickly go through those methods.

NavigableMap

NavigableMap provides a method to navigate the map in interesting ways. For instance, rather than getting value stored for a key, we can retrieve the value stored against the smallest key or get the next immediate bigger key for the given key. Following are some of the interesting methods that we will look into. We can see actually these methods are helping us to access the TreeMap on both ends like (get the lowest key, get the highest key), etc.

Important method

lowerkey (key): Returns the greatest key strictly less than the given key, or null if there is no such key
lowerEntry (key): Follows the above and returns the key-value mapping for the key.
floorKey (key): Returns the greatest key less than the given key or equal to the given key, or null if there is no such key
floorEntry (key): Follows the above and returns the key-value mapping for the key.
higherKey (key): Returns the lowest key strictly greater than the given key, or null if there is no such key
higherEntry (key): Follows the above and returns the key-value mapping for the key.
ceilingKey (key): Returns the least key greater than or equal to the given key, or null if there is no such key
ceilingEntry (key): Follows the above and returns the key-value mapping for the key.
firstEntry (): Returns a key-value mapping associated with the least key in this map
lastEntry (): Returns a key-value mapping associated with the highest key in this map
pollFirstEntry (): Remove and returns a key-value mapping associated with the least key in this map
pollLastEntry (): Remove and returns a key-value mapping associated with the highest key in this map

Java Code to see above methods

Create and Populate Map

TreeMap<Integer, String> map = new TreeMap<> ();
map.put(15, "banana");
map.put(16, "apple");

lowerKey and lowerEntry Example

Here when we try with lowerKey(16) it looks for available keys and returns the greatest key lower then 16, in this case it is 15.

key = map.lowerKey(16);
test = map.lowerEntry(16);
System.out.println(key);  //15
System.out.println(test); //banana

floorKey and floorKeyEntry Example

Here when we try with floorKey(16) it looks for available keys and returns the greatest key lower than (or equal to 16), in this case, it is 16.

key = map.floorKey(16);
test = map.floorEntry(16);
System.out.println(key);  //16
System.out.println(test); //apple

higherKey and higherEntry

higher key will return the least key strictly greater than the given key and following the same logic higherEntry will return the key-value pair. Note that in this case, 14 key does not exist in the map

key = map.higherKey(14);
test = map.higherEntry(14);
System.out.println(key);  //15
System.out.println(test); //banana

ceilingKey and ceilingEntry

ceilingKey logic is very similar to higherkey, except the fact that it checks for the least key equal to or greater the given key.

key = map.ceilingKey(16);
test = map.ceilingEntry(16);
System.out.println(key); 			  //16
System.out.println(test.getValue()); //apple

Important Points

Treemap is Red-Black tree-based implementation.
Treemap provides guaranteed log(n) time cost for containsKey(), get(), put(), and remove() .

References

Red Black Tree

Navigating Treemap in Java