Кто-нибудь может объяснить, в чем разница между красно-черным деревом и бинарным деревом? Вижу разницу только в том, что красно-черное дерево промаркировано цветом, только не понятно для чего. Чтобы перестраивать дерево когда оно становится несбалансированным? Разве нельзя сделать такое же и в бинарном дереве без маркировки? Я же могу так же перестроить.
-
Маркировка цветом проводится по таким правилам, что при вставке/удалении узла можно быстро определить, что требуется перебалансировка дерева, при этом отнюдь не каждая операция с rb-tree может требовать новой балансировки.– avp26 окт 2016 в 21:29
-
Как этот цвет может помочь определить что нужна перебалансировка– J Mas27 окт 2016 в 6:29
-
Прочтите внимательно разделы Свойства и Вставка в вике– avp27 окт 2016 в 12:35
-
и все рано не понимаю для чего цвета, цвета то все равно меняются при поворотах.– J Mas27 окт 2016 в 17:40
-
1Правильно. Они меняются вместе с перебалансировкой дерева таким образом, чтобы отражать тот факт, что дерево уже снова сбалансировано. Мы узнаем, например при вставке, что она приводит к разбалансировке дерева, когда смотрим на цвета. Затем мы вращаем поддеревья и меняем цвета так, чтобы он соответствовали свойствам сбалансированного дерева. Да Вы просто сорсы посмотрите.– avp27 окт 2016 в 18:10
1 ответ
разве нельзя сделать такое же и в бинарном дереве без маркировки
Теоретически - можно. Но это может занимать очень много времени. Для того, чтобы балансировка шла быстрей, и вводят специальные признаки.
И красно-чёрные деревья - не единственный способ ускорить процесс. Есть ещё, например, АВЛ-деревья.
Одно из отличий (определяющее и другие характеристики) между к/ч и АВЛ состоит в том, что в к/ч на хранение этой дополнительной информации достаточно 1 бита (побитовая упаковка данных может немного усложнять алгоритм, но здорово экономит память, что в некоторых случаях важно). А в АВЛ - целого (если не вдаваться в детали), что не так скромно, но позволяет производить балансировку чуть быстрей.
Сравнение других характеристик обоих типов деревьев по этой ссылке.
Но по сути же и красно-чёрные, и АВЛ-деревья являются разновидностью двоичных деревьев.
-
И еще одна хорошая ссылка (из той же статьи в вике, на которую ссылаетесь), рассказывает про деревья поиска (в основном rb-tree)– avp26 окт 2016 в 21:24
-
Для меня наверное не понятна как происходит балансировка, чем помогает маркировка, объясните пожалуйста.– J Mas27 окт 2016 в 6:13
-
@JTan, см. комментарий avp к ответу. Без доп. признаков пришлось бы перелопачивать всё дерево целиком при каждой операции балансировки. Что именно это за признаки и как они помогают - зависит от типа дерева, есть в статьях по ссылкам в ответе и комментах.– PinkTux27 окт 2016 в 6:24