Прежде чем начинать говорить о красно-черных деревьях, немного о бинарных деревьях вообще. Важно, чтобы дерево было сбалансированным, чтобы длины поддеревьев отличались не больше чем на единицу. Если это не так, работа с таким деревом становится более затратной по времени и смысла в таком дереве уже нет. Однако, при операциях вставки и добавления дерево идет вразнос. Одни ветки становятся сильно длинее других. Его можно сбалансировать и привести ветки в порядок. Для этого придуманы самобалансирующиеся деревья - при вставке элементов им ветки выравнивают. Но балансирование - дорогая операция. Лучше всего - золотая середина. Красно-черное дерево, где узлы помечены черным и красным цветами, называют "достаточно сбалансированным". Длины поддеревьев у него могут отличаться больше, чем на единицу. Но никогда больше чем в два раза.
Пример использования из реальной жизни: std::map'ы обычно реализуют через красно-черные деревья.
Картинка из Википедии, которую обычно приводят в качестве примера красно-черного дерева, мне не нравится.
Эта картинка дает неверное впечатление. Дерево, изображенное на ней, сбалансировано. И разноцветные вершины расположены рядами. И создается ощущение, что оно всегда так. Вот картинка получше (из статьи Advanced Haskell Data Structures: Red-Black Trees):
Формальное описание красно-черного дерева и его свойств вы найдете в Википедии, а я вам предлагаю посмотреть вставку элеметов в красно-черное дерево под бодрящую музыку.
Если хочется расширить и углубить свое знание красно-черных деревьяв - вот вам хорошая лекция по красно-черным деревьям. На английском.
(Пост опубликован в рамках недели борьбы с велосипедизмом)
среда, июля 28, 2010
Красно-черные деревья
Подписаться на:
Комментарии к сообщению (Atom)
Atom feed
21 коммент.:
Нраведцо ^_^
Это, насколько я понимаю, всё ещё борьба с велосипедизмом? Жестокие же велосипедисты встречались на Вашем пути:)
ЕМНИП, четкого определения сбалансированности нет, есть несколько разных. Поэтому я бы немного подправил вводную часть. АВЛ-деревья не являются единственными "действительно" сбалансированными деревьями, красно-черные тоже сбалансированны, но по другому определению. Не нужно напрасно пугать читателей и вынуждать их искать более сложные алгоритмы
P.S. Отличный цикл, так держать!
pure virtual
Нраведцо ^_^
:-)
Это, насколько я понимаю, всё ещё борьба с велосипедизмом?
Ага
Жестокие же велосипедисты встречались на Вашем пути:)
Не, попыток придумать свои красно-черные деревья я не видела, к счастью.
Почему именно rb-tree? C точки зрения ручной реализации - это порядка 5-6 нетривиальных поворотов. А если надо удалять, так это вообще для большинства деревьев жестокая реализация.
Наиболее простым сбалансированным деревом (имхо) является декартово дерево (дерамида, treap), там только 2 тривиальных поворота, балансировка достигается как в двоичной куче за счет случайного дополнительного атрибута.
Почти успел реализовать Б-дерево, но понял что удаление из дерева очень не просто.
Дерамида у мена влезла в 10Кб исходников, а все другие реализации деревьев которые я нашел отличаются в большую строну на порядок (не менее двоичного).
Считаю, что красно-черное дерево не является велосипедом, а скорее какой-то монстрообразный танк.
Sergey Kishchenko
ЕМНИП, четкого определения сбалансированности нет, есть несколько разных. Поэтому я бы немного подправил вводную часть. АВЛ-деревья не являются единственными "действительно" сбалансированными деревьями, красно-черные тоже сбалансированны, но по другому определению.
В университетском курсе у нас термины "АВЛ" и "сбалансированные" деревья употреблялись как синонимы. Сейчас заглянула в перевод Кнута (Т.3, глава 6.2.3) "Бинарное дерево называется сбалансированным, если высота левого поддерева любого узла отличается не более чем на +/-1 от высоты правого поддерева". Так что все ОК вроде.
Не нужно напрасно пугать читателей и вынуждать их искать более сложные алгоритмы
Да если что - ссылки на Википедию есть, народ разберется если чего не так.
P.S. Отличный цикл, так держать!
Спасибо :-)
67108864
Почему именно rb-tree?
Потому что оно используется в STL. И в функциональных языках вроде тоже.
@Alena
>И в функциональных языках вроде тоже.
В библиоткех функциональных языков. Встроенной в ядро языка реализации я не встречал (возможно, где-то в целях оптимизации применяются).
Отличная статья.
RB-tree используется в реализации Microsoft COM Structured Storage
Интересно так же было бы их поискать в имплементации файловых систем.
Видео - класс!
Красно-чорные деревья говно.
Во-первых, это сочетание цветов = анархо-коммунизм
http://en.wikipedia.org/wiki/Anarchist_Catalonia
Во-фторых, их придумывали во времена когда RAM latency был 1 такт.
В современном мире, когда доступ к памяти порядка 30-150 тактов, подобные структуры данных хорошо работают только если влезают в кеш. Связные списки из этой же серии.
В тех редких случаях когда мне нужны деревья, предпочитаю B-trees.
Их как и многие другие полезные вещи тоже придумывали во времена когда RAM latency был 1 такт.
Однако придумывали для, цитата с wikipedia, "systems that read and write large blocks of data", шо в полной мере относится к оперативной памяти современных компьютеров: запросы в память нынче блоками по 64 байта, если свопится, то вообще страницами по 4kb.
Вот красивые графики, из которых следуети, что RB-trees сливают B-trees в среднем в 2.5 раза:
http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html
На некоторых операциях вперёд вырываюццо hashmaps.
Обращаю ваше внимание, шо в 100% тестах B-trees худший выбор из возможных.
Это кстати одна из причин, по которой я искренне считаю STL говном: как ты упомянула, он зачем-то использует RB-trees для реализации map.
Вот у Microsoft как обычно всё чётко: CAtlMap реализован через HashMap, к тому же память под элементы выделяется не как в STL, а большими блоками, причём об этом никому знать не обязательно - всё аккуратно спрятано внутри реализации. Это приводит к тому что типичные алгоритмы работающие с ассоциативными списками при использовании CAtlMap вместо std::map выигрывают от 2 раз до 1 порядка (когда-то пару раз измерял).
Soonts.
P.S. Но для расширения кругозора + прохождения собеседований конечно надо знать шо такое красно-чорные деревья.
Есть интересное расширения/упрощение обычных RB-деревьев. Так называемые Left-leaning RB-деревья. В них правила балансировки несколько проще.
Спасибо.
Использовать ли RB-trees -- конечно, дело хозяйское, но новичкам для общего образования пост очень полезен.
В университетском курсе у нас термины "АВЛ" и "сбалансированные" деревья употреблялись как синонимы.
Как хорошо, что еще есть университетские курсы, где преподают сбалансированные деревья :)
Сейчас заглянула в перевод Кнута (Т.3, глава 6.2.3) "Бинарное дерево называется сбалансированным, если высота левого поддерева любого узла отличается не более чем на +/-1 от высоты правого поддерева". Так что все ОК вроде.
Вполне возможно, что меня ввели в заблуждение какие-то другие источники.
Мне кажется, что для понимания КЧД нужно курить не все эти трюки с вращением, а начать с того, что КЧД - это отображение троичного B-дерева на двоичное. (Как известно, с помощью двоичных деревьев можно реализовать любую структуру данных. Доказано LISP'ом с его cons-парами).
Красные узлы - центральные в блоке, чёрные - боковые.
Все эти выверты с вращениями - это отображение алгоритмов перебалансировки троичного B-дерева.
По-моему, то ли в Кормене, то ли в Седжвике об этом хорошо написано.
тьфу, чёрный - центральный, красный - боковой.
Простите за глупости, а зачем эти сбалансированные деревья?
Простите за глупости, а зачем эти сбалансированные деревья?
Это структура данных, используется в программировании. Подробности знает Google.
вот такое попалось, достаточно понятно нарисовано. вдруг кому-нть пригодится.
http://rain.ifmo.ru/cat/view.php/vis/trees/red-black-2002
Если почитать сам пост и комментарии автора приходишь к выводу, что сбалансированными деревьями здесь называют AVL деревья. При этом почему-то балансировку называют слишком дорогой. И получается, что красно-черные быстрее. А может ли автор привести реальный пример сравнения AVL и Red-Black деревьев где бы AVL уступили цветным?
А то борьба с велосипедизмом смотрится смешно, если ссылаться только на то, что цветные используются в STL.
Сергей
Сергей, похоже моя статья вас чем-то расстроила и вы рветесь в бой.
Если вам действительно интересно сравнение AVL и красно-черных деревьев, то вы его найдете, например, здесь.
Если вам хочется просто поспорить, то вам не сюда.
добрый день! скажите, пожалуйста, каждое ли АВЛ дерево можно раскрасить так, чтобы оно было красно черным? нигде не могу найти ответ на этот вопрос. Спасибо!
статья супер. наконец-то я начала понимать профит КЧД
Отправить комментарий