Pull to refresh

Comments 43

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

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

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


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

На самом деле все сильно зависит от конкретного случая.
Скажем, если вам требуется держать много небольших ассоциативных массивов, то хэш-таблицы возможно не особо хороший вариант, т.к. потребляют относительно много памяти.
если вам нужно реализовать неизменяемые структуры данных то без деревьев они будут потреблять слишком много памяти. сортированные таблицы тоже без деревьев нормально не сделаешь.
Это не всегда (хотя и чаще всего) верно. Простой пример: ассоциативный массив из небольшого количества элементов с длинным ключом. Набросал эксперимент: сравнение 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 раз.

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

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

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

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

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

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

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


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

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

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

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

да в любом случае, иначе нарушаются свойства красно-черного дерева
p.s. Есть такое понятие — идентичность объекта, ознакомтесь.
UFO just landed and posted this here
Да, было дело. Я по сути рассказывал ровно то, что рассказывал уже упомянутый тут Robert Sedgewick в своей книге и в своем курсе на Coursera. Очень советую как первоисточник.

P.S. А эта статья так себе, я ничего не понял. :(
ключи всех левых потомков <= k < ключи всех правых потомков
Распространённая ошибка. Рассмотрите дерево из миллиона одинаковых элементов и попытайтесь его сбалансировать. Хорошо получится?

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

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

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


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

а вот если к цвету прибавить вес(дальность до предка)… то брюки превращаются… брюки превращаются…
при перебалансировке веса нужно пересчитывать. Выше уже выкладывали визуализацию, в которой при изменениях идут повороты вплоть до смены корня. Поменялся корень — нужно веса пересчитать, что сказывается на производительности.
UFO just landed and posted this here
Красно-чёрным деревьям, как мне кажется, очень сильно мешает именно использование терминов «красный» и «чёрный». Я хорошо помню эту лекцию в университете «А теперь нарисуем дерево с черной вершиной и двумя красными детьми...» — и вся аудитория в ступоре, потому что откуда же у студентов с собой на лекции цветные карандаши или ручки? Во всей остальной дискретке используются какие-нибудь индексы, типы, подтипы — и всё понятно. А тут откуда-то взялись цвета, которые ещё и сочетаться должны в определённом порядке. Мы что, на лекции по моде в ПТУ легкой промышленности?
Спасибо вам, теперь я понял, почему квантовая физика так сложна!
Ведь там у кварков мало того, что цвет, так ещё и аромат есть. Откуда же у студентов с собой на лекции несколько флаконов духов возьмутся? Мы что, в парфюмерном магазине?
А в чём сарказм? Типа квантовая физика не сложна? Или типа неуместные аналогии делают её проще?
Не понял, а обозначить «красную вершину» кружочком, а «черную вершину» кружочком с крестиком нельзя?
Можно. Но это примерно как назвать «длиной» переменную, которая означает ширину и написать рядом комментарий, что это на самом деле длина. Будет работать, но добавляет лишний уровень косвенности и запутанности.
Вы передергиваете.
Если БЫ в алгоритме наравне с «красными/черными» вершинами присутствовали еще «белые» и «отмеченные крестиком» вершины, то ваша аналогия была бы уместана.
А так мы имееи ровно ДВА типа вершин, к которым применить краткую удобную систему условносных обозначений не составит труда.
Ни для записи, ни для понимания.

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

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


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

Вы буквально воспринимаете всю специфическую графовую терминологию, что ли? Хорошо, что вам лектор не говорил фраз типа «и тут мы левого сына присваиваем правому соседу», совсем бы крыша поехала.
Говорил, конечно, крыша не поехала. Просто неудобная терминология, я же не говорю, что она сложная или что алгоритмы не работают. Названо просто глупо, а сама структура данных хорошая.
Sign up to leave a comment.

Articles