How is the sorting of elements implemented when inserting a new element into a TreeSet?

In Java, TreeSet is implemented based on a red-black tree, which is a self-balancing binary search tree. When inserting a new element, the following occurs:

1. If the TreeSet is created with a comparator, its compare method is used to determine the position of the new element. If no comparator is provided, the elements must implement the Comparable interface.
2. The element is compared with current nodes in the tree to find the correct insertion point, maintaining order.
3. After insertion, the red-black tree is rebalanced to preserve its properties.

Thus, the sorting of elements upon insertion is ensured by the ordered placement within the data structure and the use of comparison via Comparable or Comparator.

Example:

TreeSet<String> set = new TreeSet<>();
set.add("banana");
set.add("apple");
set.add("cherry");

// Elements will be stored in sorted order: apple, banana, cherry