Course contentsShow
← Java
Lesson 1132 of 2,87026. Map ImplementationsFree lesson

TreeMap Overview: Sorted Map Implementation

Understanding TreeMap as a NavigableMap that maintains keys in sorted order using a Red-Black tree.

TreeMap Overview: Sorted Map Implementation

You'll learn what TreeMap is and how it maintains keys in sorted order using a Red-Black tree.

What Is TreeMap?

TreeMap is Java's sorted map implementation. Unlike HashMap, which stores key-value pairs in no particular order, TreeMap keeps all entries sorted by their keys. It implements the NavigableMap interface, giving you powerful navigation and range operations on top of basic map functionality.

The Red-Black Tree Foundation

Under the hood, TreeMap uses a Red-Black tree — a self-balancing binary search tree. Think of it like a family tree where:

  • Each node contains a key-value pair
  • Keys are organized so smaller keys sit to the left, larger keys to the right
  • The tree automatically rebalances itself to maintain efficiency
  • Red-Black properties ensure the tree never gets too lopsided

Sorted Key Requirement

For TreeMap to maintain sorted order, your keys must be comparable. Either:

  1. The key class implements Comparable (natural ordering)
  2. You provide a Comparator when creating the TreeMap

Without one of these, you'll get runtime errors when adding elements.

TreeMap vs HashMap

While HashMap offers O(1) average-case performance for get/put operations, TreeMap guarantees O(log n) performance. You're trading a bit of speed for sorted ordering and navigation capabilities. Choose TreeMap when you need:

  • Keys in sorted order during iteration
  • Range queries (all keys between X and Y)
  • Finding closest keys (floor, ceiling operations)

Key Takeaway: TreeMap is a NavigableMap implementation that maintains entries sorted by key using a Red-Black tree, providing O(log n) operations with powerful navigation methods at the cost of slightly slower performance than HashMap.