Поиск строк в TreeSet, которые начинаются с заданного префикса

Для начала предлагаю пересмотреть ваши требования. Character.MAX_VALUE — это U+FFFF, который не является допустимым символом Unicode и никогда им не будет; поэтому я не могу придумать вескую причину, по которой вам нужно было бы его поддержать.

Но если для этого требования есть веская причина, вам нужно «увеличить» свой префикс, чтобы вычислить наименьшую строку, которая больше, чем все строки, начинающиеся с вашего префикса. Например, учитывая "city", вам нужно "citz". Вы можете сделать это следующим образом:

/**
 * @param prefix
 * @return The least string that's greater than all strings starting with
 *         prefix, if one exists. Otherwise, returns Optional.empty().
 *         (Specifically, returns Optional.empty() if the prefix is the
 *         empty string, or is just a sequence of Character.MAX_VALUE-s.)
 */
private static Optional<String> incrementPrefix(final String prefix) {
    final StringBuilder sb = new StringBuilder(prefix);

    // remove any trailing occurrences of Character.MAX_VALUE:
    while (sb.length() > 0 && sb.charAt(sb.length() - 1) == Character.MAX_VALUE) {
        sb.setLength(sb.length() - 1);
    }

    // if the prefix is empty, then there's no upper bound:
    if (sb.length() == 0) {
        return Optional.empty();
    }

    // otherwise, increment the last character and return the result:
    sb.setCharAt(sb.length() - 1, (char) (sb.charAt(sb.length() - 1) + 1));
    return Optional.of(sb.toString());
}

Чтобы использовать его, вам нужно использовать subSet, когда вышеуказанный метод возвращает строку, и tailSet, когда он ничего не возвращает:

/**
 * @param allElements - a SortedSet of strings. This set must use the
 *                      natural string ordering; otherwise this method
 *                      may not behave as intended.
 * @param prefix
 * @return The subset of allElements containing the strings that start
 *         with prefix.
 */
private static SortedSet<String> getElementsWithPrefix(
        final SortedSet<String> allElements, final String prefix) {

    final Optional<String> endpoint = incrementPrefix(prefix);

    if (endpoint.isPresent()) {
        return allElements.subSet(prefix, endpoint.get());
    } else {
        return allElements.tailSet(prefix);
    }
}

Посмотрите его в действии: http://ideone.com/YvO4b3.

Если кто-то ищет более короткую версию ответа руаха:

Первый элемент на самом деле set.ceiling(prefix), а последний - вам нужно увеличить префикс и использовать set.floor(next_prefix)

public NavigableSet<String> subSetWithPrefix(NavigableSet<String> set, String prefix) {
    String first = set.ceiling(prefix);
    char[] chars = prefix.toCharArray();
    if(chars.length>0)
        chars[chars.length-1] = (char) (chars[chars.length-1]+1);
    String last = set.floor(new String(chars));
    if(first==null || last==null || last.compareTo(first)<0)
        return new TreeSet<>();
    return set.subSet(first, true, last, true);
}