Что означает "красно-черное дерево" в: TreeSet, который хранит свои элементы в красно-черном дереве, упорядочивает свои элементы на основе их значений;
Я читал Java Tutorial Oracle, и я столкнулся с утверждением ниже.
TreeSet, который хранит свои элементы в красно-черном дереве, упорядочивает свои элементы на основе их значений;
Меня смутила фраза "красно-черное дерево", я выполнил простой поиск в Интернете и не нашел удовлетворительного ответа.
3 ответа
Красно-черное дерево - это своего рода самобалансирующееся дерево двоичного поиска. Существует несколько видов самоуравновешивающихся деревьев, таких как 2-3 дерева, деревья AA, деревья AVL и красно-черные деревья.
Назначение самоуравновешивающегося дерева очевидно, когда вы рассматриваете наихудший случай, когда может существовать несамостоятельно балансирующееся дерево двоичного поиска.
Рассмотрим этот случай: начните с вставки целого числа в пустое дерево (не самобалансировку). Продолжайте вставлять целые числа, каждое значение которых больше предыдущего. Ваше худшее время поиска приведения будет для последнего вставленного элемента с временной сложностью O(n). Это потому, что вам нужно пройти по всему дереву, чтобы добраться до нужного элемента, так же, как связанный список.
Это намного хуже, чем сбалансированное двоичное дерево поиска с временной сложностью O(lg n). Поэтому существуют методы, такие как красно-черное дерево, которые пытаются гарантировать, что дерево сбалансировано (имеется в виду, что вес каждого ребенка одинаков).
Для меня третий результат поиска был https://en.wikipedia.org/wiki/Red%E2%80%93black_tree, который хорошо объясняет концепцию.
По сути, это метод, позволяющий сохранить бинарное дерево практически сбалансированным, чтобы независимо от порядка вставки оно не вырождается в связанный список, при этом сохраняя низкую стоимость вставки (и удаления).
1) Каждый узел имеет красный или черный цвет, а корень дерева всегда черный.
2) Нет двух смежных красных узлов (красный узел не может иметь красного родителя или красного ребенка, красный должен иметь черного родителя).
3) Каждый путь от корня до узла NIL имеет одинаковое количество черных узлов.