AnROm Jun 10 2017 at 13:08

Красно-черные деревья: коротко и ясно

3 min

274K

Algorithms*

+25

Comments 43

frees2 Jun 10 2017 at 13:39

Менюшку такую можно сделать, с двумя цветами, больше будет отвлекать. Прямо в шапке страницы. Сейчас шапки на пол экрана, а так хоть функциональность будет.

mayorovp Jun 10 2017 at 13:53

В нормальных ассоциативных массивах используются хеш-таблицы, а не деревья.

mayorovp Jun 11 2017 at 09:31

Хорошо, изменю формулировку, если эта не нравится.

Хеш-таблицы работают быстрее деревьев, а потому для ассоциативных массивов предпочтительнее использовать именно их.

Dark_Daiver Jun 11 2017 at 09:43

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

Large Jun 11 2017 at 12:03

если вам нужно реализовать неизменяемые структуры данных то без деревьев они будут потреблять слишком много памяти. сортированные таблицы тоже без деревьев нормально не сделаешь.

alexeykuzmin0 Jun 13 2017 at 16:48

Это не всегда (хотя и чаще всего) верно. Простой пример: ассоциативный массив из небольшого количества элементов с длинным ключом. Набросал эксперимент: сравнение std::map и std::unordered_map для контейнера из 1 000 элементов, ключом в которых является случайная строка длиной 100 000, а значение — символ:

Код

    const int COUNT = 1000;
    const int LENGTH = 100 * 1000;
    const int QUERIES = 10;

    string ss[COUNT];
    for (int i = 0; i < COUNT; ++i) {
        ss[i] = "";
        for (int j = 0; j < LENGTH; ++j) {
            ss[i] += (char)('a' + rand() % 10);
        }
    }
    
    double start = clock();
    unordered_map<string, char> um;
    for (int q = 0; q < QUERIES; ++q) {
        for (int i = 0; i < COUNT; ++i) {
            um[ss[i]] = ss[i][0];
        }
    }
    cout << (clock() - start) / CLOCKS_PER_SEC << endl;

    start = clock();
    map<string, char> m;
    for (int q = 0; q < QUERIES; ++q) {
        for (int i = 0; i < COUNT; ++i) {
            m[ss[i]] = ss[i][0];
        }
    }
    cout << (clock() - start) / CLOCKS_PER_SEC << endl;

На моей машине в зависимости от соотношения операций поиск/вставка (регулирующегося константой QUERIES в коде) std::map быстрее, чем std::unordered_map в 5-6 раз.

Собственно, думаю, понятно, почему именно в этом крайнем случае дерево работает быстрее, чем хеш-таблица.

MrShoor Jun 14 2017 at 06:15

Есть такая штука, как collision attack. Поэтому для всех ассоциативных контейнеров, смотрящих наружу — предпочительнее использовать деревья. Это например касается баз данных, любого серверного бек-энда принимающего пользовательские данные, объектов уровня ядра ОС и т.п.

А некоторые неосторожные хештаблицы умудряются сами себе устроить такой collision attack. Совсем недавно так облажались:
1. Swift
2. Rust
3. Delphi

mayorovp Jun 14 2017 at 06:23

Для защиты от такой атаки достаточно выбирать случайную хеш-функцию. Или можно использовать деревья уже внутри корзин хеш-таблицы, как делает стандартная библиотека Java

MrShoor Jun 14 2017 at 06:57

Это решение из разряда: «мне повезет». Коллизии заложены в самой природе хешфункции, и попытки замаскировать проблему не решат её.

mayorovp Jun 14 2017 at 08:48

Проблему collision attack такой подход именно что решает.

alexeykuzmin0 Jun 14 2017 at 12:06

Вероятность того, что «не повезет» обычно экспоненциально (или быстрее) уменьшается с ростом размера входных данных. Так что можно и рискнуть — все равно шансы того, что для более или менее разумного размера данных нам «не повезет» хоть за миллиард лет работы алгоритма, крайне малы.

MikeLP Jun 10 2017 at 14:03

Статья хорошая, дерево нужное (потому что многие, кому доводилось хранить сколь угодно большую вложенную структуру, интересовались хоть раз как хранить и опимизировать эту структуру, уменьшить время вствавки и т.д.), формулы понятные. Но все же хотелось бы обьяснения на пальцах без подробных формул, потому что, например, я лично приблизительно интуитивно понимаю как оно работает, но академические выражения «черная высота» не добавляет ясности. И в конце получился не очень красивый итог — аля шо не поняли лошки эти сраные деревья — а кто-то взял и понял. Лол.

Надеюсь у вас будет еще время сделать более подробную статью.

Large Jun 11 2017 at 12:14

посмотрите на авл-деревья они более простые (разница в длине веток не должна быть больше одного элемента) и на реальных данных обычно работают быстрее (удаление обходится дороже но если мало удаляете то можно смело использовать). идея везде до ужаса простая — если у вас есть список N элементов, то чтоб найти какой-то конкретный элемент вам нужно в худшем случае пробежаться от начала и до конца списка, то есть пройти N шагов, а если вы тот же список разветвили (с помощью операции сравнения) и превратили в дерево — то уже нужно пройти log N шагов. Любая операция — вставка или удаление должны менять дерево так, чтоб оно оставалось ветвистым (для авл деревьев — разница между высотой веток не больше 1 элемента, для красно-черных — не больше чем в два раза (потому их и красят в два цвета)) и не нарушалось правило поиска.

konshyn Jun 10 2017 at 16:23

Рассказ будет кратким, без рассмотрения алгоритмов балансировки при вставке/удалении элементов в красно-черных деревьях.

Т.е. самое важное, благодаря чему используется это дерево фактически везде в STL, не рассматривается?
Имхо, эту статью можно просто заменить ссылкой на википедию.

niamster Jun 10 2017 at 16:33

Красно-черные деревья не интуитивны, но если понять, что они эквиваленты 2-3 деревьям(которые воспринимаются проще) то все становится на свои места.

Отличное объяснение от автора красно-черных деревьев Р. Седжвика на портале Принстонского университета.

Для полноты статьи добавьте алгоритм удаления ячейки. Это самая захватывающая часть.

AnROm Jun 10 2017 at 16:42

Спасибо за замечание!

mayorovp Jun 10 2017 at 18:16

Скорее 2-4 деревьям.

fRoStBiT Jun 10 2017 at 18:13

Открывая статью с таким заголовком, думал, что наконец-то пойму, как происходит удаление чёрного листа.
Ан нет…

Andrey_Solomatin Jun 10 2017 at 20:58

Визуализация вставки и удаления: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

Если поставить на паузу и идти по шагам, там будет коротки пояснительный текст.

PitXBull Jun 10 2017 at 22:09

да просто родитель меняет цвет с красного на черный или остается черным…

mayorovp Jun 11 2017 at 09:29

Только если родитель красный, а брат — черный, и у брата нет красных детей. Иначе нарушится инвариант.

PitXBull Jun 11 2017 at 19:04

да в любом случае, иначе нарушаются свойства красно-черного дерева

PitXBull Jun 11 2017 at 19:09

p.s. Есть такое понятие — идентичность объекта, ознакомтесь.

UFO just landed and posted this here

rvncerr Jul 5 2017 at 14:00

Да, было дело. Я по сути рассказывал ровно то, что рассказывал уже упомянутый тут Robert Sedgewick в своей книге и в своем курсе на Coursera. Очень советую как первоисточник.

P.S. А эта статья так себе, я ничего не понял. :(

khim Jun 10 2017 at 20:02

ключи всех левых потомков <= k < ключи всех правых потомков

Распространённая ошибка. Рассмотрите дерево из миллиона одинаковых элементов и попытайтесь его сбалансировать. Хорошо получится?

Либо <= дважды, либо < дважды (а одинаковые элементы запрещены), пожалуйста.

grossws Jun 10 2017 at 23:50

Так, например, ассоциативные массивы в большинстве библиотек реализованы именно через красно-черные деревья.

А можно подтверждающую статистику? Ну, в STL map по умолчанию такой. В python, ruby, perl и lua по умолчанию hash map'ы. В java "по умолчанию" варианта нет, но присутствуют и hash map и tree map.

Maccimo Jun 11 2017 at 15:40

В военное время HashMap может стать немного красно-чёрным.

grossws Jun 11 2017 at 18:46

Только в тяжёлых бинах, большая же часть останется нормальной человеческой hash-таблицей с поиском/вставкой за O(1) с худшим вариантом на уровне O(log N).

И то, это детали имплементации, позволяющие иметь нормальную производительность при сильно неудачном сочетании данных и хэш-функции, когда много данных (или все) попадают в один бин.

workmi Jun 11 2017 at 00:22

а вот если к цвету прибавить вес(дальность до предка)… то брюки превращаются… брюки превращаются…

IvanTamerlan Jun 11 2017 at 18:03

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

UFO just landed and posted this here

ntkj666 Jun 12 2017 at 02:56

NIL на картинке

tangro Jun 12 2017 at 13:15

Красно-чёрным деревьям, как мне кажется, очень сильно мешает именно использование терминов «красный» и «чёрный». Я хорошо помню эту лекцию в университете «А теперь нарисуем дерево с черной вершиной и двумя красными детьми...» — и вся аудитория в ступоре, потому что откуда же у студентов с собой на лекции цветные карандаши или ручки? Во всей остальной дискретке используются какие-нибудь индексы, типы, подтипы — и всё понятно. А тут откуда-то взялись цвета, которые ещё и сочетаться должны в определённом порядке. Мы что, на лекции по моде в ПТУ легкой промышленности?

Maccimo Jun 12 2017 at 15:02

Спасибо вам, теперь я понял, почему квантовая физика так сложна!
Ведь там у кварков мало того, что цвет, так ещё и аромат есть. Откуда же у студентов с собой на лекции несколько флаконов духов возьмутся? Мы что, в парфюмерном магазине?

tangro Jun 13 2017 at 12:00

А в чём сарказм? Типа квантовая физика не сложна? Или типа неуместные аналогии делают её проще?

aristarh1970 Jun 13 2017 at 00:47

Не понял, а обозначить «красную вершину» кружочком, а «черную вершину» кружочком с крестиком нельзя?

tangro Jun 13 2017 at 11:59

Можно. Но это примерно как назвать «длиной» переменную, которая означает ширину и написать рядом комментарий, что это на самом деле длина. Будет работать, но добавляет лишний уровень косвенности и запутанности.

aristarh1970 Jun 13 2017 at 17:50

Вы передергиваете.
Если БЫ в алгоритме наравне с «красными/черными» вершинами присутствовали еще «белые» и «отмеченные крестиком» вершины, то ваша аналогия была бы уместана.
А так мы имееи ровно ДВА типа вершин, к которым применить краткую удобную систему условносных обозначений не составит труда.
Ни для записи, ни для понимания.

tangro Jun 13 2017 at 22:03

Ну ок, а в двоичной системе счисления мы, например, имеем две цифры — 0 и 1. Можно было бы назвать эти сущности названиями цветов, нот, ароматов или сказочных животных. Суть была бы та же — «два типа». Но мы их всё же называем цифрами 0 и 1. Красно-чёрные деревья очень сильно «выбиваются». Ну нет таких обозначений в векторах, матрицах, графах, уравнениях, графиках и всей прочей математике до и после этих цветных деревьев.

mayorovp Jun 13 2017 at 23:45

Напротив, алгоритмы на графах (а деревья — раздел графов) очень часто оперируют понятием цвета.

А уж графики-то всегда даже визуально раскрашивать стараются.

alexeykuzmin0 Jun 14 2017 at 12:17

Вы буквально воспринимаете всю специфическую графовую терминологию, что ли? Хорошо, что вам лектор не говорил фраз типа «и тут мы левого сына присваиваем правому соседу», совсем бы крыша поехала.

tangro Jun 14 2017 at 16:44

Говорил, конечно, крыша не поехала. Просто неудобная терминология, я же не говорю, что она сложная или что алгоритмы не работают. Названо просто глупо, а сама структура данных хорошая.