* This implementation uses a left-leaning red-black BST. It requires that * the key type implements the {@code Comparable} interface and calls the * {@code compareTo()} and method to compare two keys. It does not call either * {@code equals()} or {@code hashCode()}. * The put, contains, remove, minimum, * maximum, ceiling, and floor operations each take * logarithmic time in the worst case, if the tree becomes unbalanced. * The size, and is-empty operations take constant time. * Construction takes constant time. *
* For additional documentation, see Section 3.3 of
* Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
* For other implementations of the same API, see {@link ST}, {@link BinarySearchST},
* {@link SequentialSearchST}, {@link BST},
* {@link SeparateChainingHashST}, {@link LinearProbingHashST}, and {@link AVLTreeST}.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class RedBlackBST