История из жизни. Девушка предложила своему парню-программисту пройти психологический тест: Девушка: Нарисуй дерево. Программист: (рисует бинарное дерево) Девушка: Нет, другое. Программист: Я и красно-черное дерево могу нарисовать. Итак, сегодня хочу немного рассказать о красно-черных деревьях. Рассказ будет кратким, без рассмотрения алгоритмов балансировки при вставке/удалении элементов в красно-черных деревьях. Читать дальше →
Что может заставить обратить внимание на красно-чёрные деревья, и как их реализовать? Статья ответит на оба эти вопроса. Бонусом будет показано, как на основе красно-чёрного сконструировать дерево интервалов. Читать далее
Это вторая часть из серии статей "Понимаем красно-черное дерево". Если вы пропустили первую часть, настоятельно рекомендую ознакомиться с ней здесь. Там мы разобрали причину появления кчд и расставили по полочкам некоторые его свойства.В данной части мы разберем вставку и балансировку. Эти вещи идут бок о бок, без балансировки дерево будет терять свои свойства, и толка от него будет мало. Читать далее
Использовано изображение портала cartoonbank.ru В прошлой статье мы рассмотрели правила формирования красно-чёрного дерева поиска и рассмотрели случаи балансировки при добавлении элементов. Теперь поговорим об удалении элементов. Возьмём, для примера, вот такое красно-чёрное дерево: Читать дальше →