TreeMap Java. Как устроена

Question

Меня интересует как работает TreeMap в Java под капотом. Нигде не смог найти подробного описания того как эта карта устроена изнутри, везде просто говорится что она использует красно-черные деревья, то есть она сортирует по ключам. Но тут у меня возникает вопрос - ведь значения в деревьях хранятся отсортированы по своим правилам и это не совсем напоминает ту сортировку которую мы привыкли видеть. На картинке мы видим дерево - порядок цифр соответсвует правилам хранения в деревьях, но как на выходе из мапы вылетают отсортированные объекты? Я понимаю что преимущества хранения в деревьях это быстрый поиск объекта. Но я не понимаю как сама карта возвращает все объекты отсортированные именно так как мы привыкли (1,3,7,10.....) хотя в дереве они расположены будут не совсем так. Пробовал рассматривать сорцы но пока не смог разобраться... То есть я хочу узнать как происходит выборка из дерева и на выходе получаются отсортированные объекты по ключу.

Answer 1

Ну вообще, самый тупой алгоритм вида "найти минимальный элемент и удалить его, пока в дереве есть элементы" отработает за NlogN, так что можно так и сделать.

Можно конечно и за N, примерно так:

ArrayList<int> result = new ArrayList<int>();
BinaryTreeSearch tree; // произвольное бинарное дерево

void inOrder(Node v)
{
    if (v.left)
        inOrder(v.left);
    result.add(v);
    if (v.right)
        inOrder(v.right);   
}

public static void main(String[] args)
{
    inOrder(tree.root);
}

Извиняюсь за код - хотел показать только алгоритм, плюс на джаве я не писака, а макака, так что получилось, как получилось.

Почему обход верный: по свойству, в левом поддереве все элементы меньше данного, так что сначала нужно добавить все из них, а в правом все элементы больше данного, так что их добавить нужно в конце.

БЛОГ НА HUSL

TreeMap Java. Как устроена

Ответы (1 шт):