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

Question

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

Один из методов преобразует двухсвязный список в идеально сбалансированное простое двоичное дерево в O(n) время (учитывая, что количество предметов известно заранее).Алгоритм известен как "сворачивание" - это вторая половина алгоритма перебалансировки бинарного дерева, который когда-то был опубликован в Dr.Доббса.В основном это следующие шаги...

• Учитывая размер дерева, определите размеры левого и правого поддеревьев

• Рекурсия для левого поддерева

• Выберите узел из списка для использования в качестве корневого

• Рекурсия для правильного поддерева

• Свяжите поддеревья с корнем

У меня также есть аналогичный метод, который создает красно-черное дерево.Принцип тот же, но рекурсия отслеживает высоту узла - узлы с нулевой высотой создаются красными, все остальные - черными.Расчет начальной высоты основан на самом высоком установленном бите в размере дерева и настраивается таким образом, чтобы идеально сбалансированный (2^n)-1 размерное дерево имеет только черные узлы (рекурсия выполняется только до высоты один).

Дело здесь в том, что у меня есть только красные узлы на конечном уровне, и максимум ровно половина узлов красные.

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

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

Это чистое любопытство - я знаю, что у меня нет никаких практических причин, - но знает ли кто-нибудь о специализированном приложении, где этот выбор важен?

Answer 1

При стандартном анализе амортизированной стоимости модификации красно-черных деревьев с использованием метода физика черным узлам с нулевым или двумя красными дочерними элементами присваивается положительный потенциал, равный единице, что означает, что они представляют проблемные места в дереве, где может потребоваться дополнительная работа.Красным узлам и черным узлам, имеющим ровно один красный дочерний элемент, присваивается нулевой потенциал.

Итак, чтобы снизить стоимость модификаций, дайте каждому черному узлу по одному красному дочернему узлу.

---

Тот самый Причина почему черные узлы с одним красным дочерним элементом являются благословенными, лучше всего объясняется по аналогии с избыточными двоичными числами.Сначала я объясню, как соотнести красно-черные деревья с двоичными числами, а затем объясню, почему полезны узлы с одним красным дочерним элементом.

Как вы, наверное, знаете, красно-черные деревья - это способ представления 2-4 деревьев, в которых каждый простой путь от корня до листа имеет одинаковую длину, но узлы имеют 2, 3 или 4 дочерних элемента.Простейший алгоритм добавления или удаления узла в дереве 2-4 - это тот же алгоритм, что и добавление или вычитание узла из избыточное двоичное число.

Избыточное двоичное число - это число, в котором i - я цифра представляет 2ⁱ, так же, как в стандартном двоичном числе, но i-я цифра может быть 0, 1, или 2.Они называются избыточными, потому что существует несколько способов записи заданного числа.4_{декабрь} может быть написано 100, или 20, или 12.

Чтобы добавить единицу к избыточному двоичному числу, вы увеличиваете наименьшую значащую цифру;если оно равно 3, установите его равным 1 и увеличьте следующую наименее значащую цифру, и так далее.Алгоритм останавливается, когда он встречает 0 или 1.

Чтобы добавить лист к дереву 2-4, добавьте дочерний элемент к предполагаемому родительскому элементу.Если родительский узел имеет пять дочерних узлов, разделите его на два узла и сделайте их дочерними по отношению к его родительскому узлу.Продолжайте, пока не достигнете узла, который не нуждается в разделении.Таким образом, путь к корню прерывается, когда он встречает узел с двумя или тремя дочерними элементами.

Чтобы ограничить амортизированную стоимость увеличения избыточного двоичного числа, используйте метод физиков и присвоите потенциал, равный 1, каждой двухзначной цифре.Приращение xall, которое касается k цифр, высвобождает потенциал k-1, придавая ему амортизированную стоимость O (1).

Этот анализ аналогичен амортизированной стоимости увеличения стандартного двоичного числа, но стандартное двоичное число не может поддерживать как увеличение, так и уменьшение за O (1) амортизированное время:рассмотрим 2^k - 1.Это k цифр 1.Увеличьте затраты Θ(k).Если за этим следует уменьшение, пара стоит Θ (k) и возвращает число в его старое состояние.

Избыточный двоичный код отличается тем, что 1-разрядный код останавливает каскадные операции как увеличения, так и уменьшения.2-4 дерева отличаются тем, что 3 узла останавливают каскадные операции как вставки, так и удаления.

В красно-черных деревьях узел с одним красным дочерним элементом - это просто представление 3-узла в дереве 2-4.Эти узлы являются особыми и устойчивы к вставкам или удалениям в своих поддеревьях, поэтому вам следует отдавать им предпочтение при построении красно-черных деревьев, которые будут видеть много обновлений.

Если вы знаете, что увидите только вставки, отдавайте предпочтение узлам с двумя черными дочерними элементами.Если вы знаете, что увидите только удаления, отдавайте предпочтение узлам с двумя красными дочерними элементами.

Answer 2

Краткий ответ: это зависит.

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

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

Это зависит от того, потому что это обычно зависит от приложения.