How does TreeMap/TreeSet's red-black tree implementation guarantee O(log n) operations, and what role does the Comparable/Comparator interface play in maintaining sorted order?

A red-black tree is a self-balancing binary search tree that maintains specific coloring invariants (root is black, red nodes can't have red children, every path from root to a null leaf has the same number of black nodes) through rotations and recoloring during insertion/deletion, guaranteeing the tree's height stays O(log n) even in adversarial insertion patterns that would degrade a naive unbalanced BST to O(n); TreeMap/TreeSet use either the keys' natural ordering (via Comparable.compareTo()) or an explicitly supplied Comparator to determine the tree's structure, meaning any custom key type used in a TreeMap must provide a consistent, total ordering, and inconsistent compareTo()/equals() behavior can cause TreeMap to behave incorrectly (using compareTo() == 0 as its notion of "equal" for the purposes of the map, potentially differing from the class's own equals()).

public class Employee implements Comparable<Employee> {
    private final int salary;
    // constructor omitted

    @Override
    public int compareTo(Employee other) {
        return Integer.compare(this.salary, other.salary);
        // NOTE: TreeSet<Employee> would consider two employees with EQUAL salary as
        // "duplicates" (compareTo == 0), even if their equals()/other fields genuinely differ!
    }
}