Представьте себе красно-черное дерево. Всегда ли есть последовательность вставок и удалений, которая ее создает?

Давайте предположим следующее определение красно-черного дерева:

Это двоичное дерево поиска.
Каждый узел окрашен в красный или черный цвет. Корень черный.
Два узла, соединенные ребром, не могут быть одновременно красными.
Здесь должно быть хорошее определение листа NIL, как на вики. Лист NIL окрашен в черный цвет.
Путь от корня до любого листа NIL содержит такое же количество черных узлов.

Вопрос

Предположим , что вы внедрили insertи deleteоперации для красно-черного дерева. Теперь, если вам дано правильное красно-черное дерево, всегда ли есть последовательность insertи deleteоперации, которые его строят?

мотивация

Этот вопрос мотивирован этим вопросом и обсуждением этого вопроса .

Лично я считаю, что если вы представляете себе правильное красно-черное дерево, состоящее только из черных узлов (что подразумевает, что вы представляете себе идеально сбалансированное дерево), существует последовательность insertи deleteоперации, которые его строят. Тем не мение,

Я не знаю, как точно доказать это
Я также заинтересован в более общем случае

data-structures search-trees balanced-search-trees alisianoi
источник

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

JOX

Нет, я думаю, вы не понимаете. Конечно, любой набор вставок и удалений создает некое красно-черное дерево. Вопрос заключается в следующем: является ли любое дерево, которое соответствует определению, конструируемым некоторой последовательностью вставок и удалений? Если вам дано какое-то дерево, можете ли вы воссоздать последовательность вставок и удалений?

Алисианои

@ all3fox Да, вы правы. Существует алгоритм, который использует операцию insertи deleteдля построения корректного красно-черного дерева, состоящего только из черных узлов . Он использует

вставки / делеции создать дерево высотой

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

вставки, затем используя

(h + 2) \cdot 2^{h} - 1

$(h + 2) \cdot 2^h - 1$

h

$h$

2^{h + 1} - 1

$2^{h+1} - 1$

h * 2^{h - 1}

$h * 2^{h-1}$ вставки и такое же количество удалений перекрашивают его в абсолютно черное дерево. Хитрость здесь в том, чтобы подняться в

раз по самому низкому красному слою вверх по дереву, пока оно не достигнет корня.

h

$h$

Антон Трунов

@AntonTrunov спасибо, я вроде это понимаю. Как насчет случая общего красно-черного дерева? Как вы думаете, возможно ли построить любое данное Красно-Черное Дерево с помощью insertи deleteопераций?

alisianoi

а) Ответ будет зависеть от точной реализации insertи delete; может быть несколько способов сделать эти операции. б) Так как деревья RB по сути являются B-деревьями порядка 4, можно искать вдохновение. Детали могут оказаться хитрыми, поскольку отображение из RB в B (и / или в обратном направлении) не является уникальным.

Рафаэль

Ответы:

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

Проблема с не наклоняющимися (левыми или правыми) красными черными деревьями заключается в том, что существует множество способов восстановить красную черноту после основного удаления или вставки.
Это не вставка или удаление, которое трансформирует дерево, а перебалансировка и вращение, которые происходят впоследствии, чтобы сохранить / восстановить красную черноту дерева.

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

Это было «решено» с левыми красно-черными деревьями.
Существует только один способ балансировки. Таким образом, любое заданное наклоняющееся красное черное дерево может быть реконструировано с использованием вставок и удалений, поскольку перебалансировка / ротация выполняются определенным детерминированным способом.

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

Согласно комментарию @ Антона:
существует алгоритм, который использует операцию вставки и удаления для построения корректного красно-черного дерева, состоящего только из черных узлов. Он использует вставки / делеции создать дерево высотой . Во-первых, мы можем создать идеально сбалансированное красно-черное дерево в ширину, используя $(h+2)⋅2^{h}−1$ $h$ $2^{h+1}−1$ $h∗2^{h-1}$ $h$ раз самый низкий красный слой вверх по дереву, пока он не достигнет корня.

Я думаю, что полный алгоритм балансировки, такой как Day-Stout-Warren, был бы более эффективным, хотя.

Johan
источник

Используя операции insertи deleteиз книги CLRS, вы можете построить действительное дерево RB, состоящее только из черных узлов . Хитрость заключается в том, чтобы вставить больше узлов, чем необходимо, а затем удалить лишние. Алгоритм будет устранить красные узлы.

Антон Трунов

@AntonTrunov, у вас есть ссылка на этот алгоритм, было бы неплохо включить ее в ответ. Я не могу найти его, используя мой Google-фу.

Йохан

К сожалению, у меня нет ссылки. Я попытался ответить на вопрос в то время и придумал алгоритм для частного случая всех черных деревьев RB. Я вроде описал это в этом комментарии, но не предоставил доказательства.

Антон Трунов

Что вы подразумеваете под «Это было« решено »с левыми красными черными деревьями». Даже левое красное черное дерево может хранить одни и те же предметы несколькими способами.

user239558