The 30 second answer
A binary search tree finds a key in time proportional to its height. Insert sorted keys into a plain one and the height becomes n, so lookups turn linear. Balanced trees such as red-black trees keep the height logarithmic. Java's TreeMap is one, with guaranteed log n operations and sorted keys. I choose it when I need order or ranges, and HashMap otherwise.
Binary search trees. Each node's left subtree holds smaller keys and its right subtree larger ones, so search, insert and delete take time proportional to the tree's height. With random inserts the height is close to log n; with sorted inserts a naive tree degenerates into a linked list of height n.
Balancing. AVL trees and red-black trees rotate nodes on insert and delete to keep the height logarithmic. Red-black trees allow slightly more imbalance in exchange for fewer rotations, which is why many libraries use them. TreeMap and TreeSet are red-black trees with guaranteed log n operations, and HashMap turns very long collision chains into small red-black trees so a bad hash does not make lookups linear.
TreeMap versus HashMap. HashMap is expected constant time and unordered. TreeMap is log n and sorted, and adds what a hash map cannot do: firstKey, floorKey, ceilingKey, headMap, tailMap and subMap. Use it for "the price band containing 42 euros", "all events between two timestamps", or ordered iteration without a separate sort.
NavigableMap<Integer, String> bands = new TreeMap<>(Map.of(0, "budget", 50, "mid", 150, "premium"));
bands.floorEntry(42).getValue(); // "budget": the greatest key <= 42
bands.subMap(0, true, 100, false); // keys in [0, 100)Ordering must match equality. A TreeMap compares keys with compareTo or its comparator, never equals, so a comparator that returns 0 for different objects merges them. See equals, hashCode and TreeSet ordering.
On disk. Databases use B+ trees instead, many keys per node to keep the tree shallow for block storage: see B+ tree lookups. Lucene's terms dictionary uses yet another structure: What is an FST?.