-3
Я изучал деревья красного дерева, и мне было интересно, какая временная сложность для назначения черных высот для каждого узла, когда мы делаем такой процесс, как вставка?Red Black Trees complexities
A
ответ
1
вставки в Красное черное дерево войти расходы (N) ... проверить эту прохладную ссылку на другие сложности различных структур данных/алгоритмы ...
другая полезная ссылка, показывающий, как вставка/удаление/перестановка узлов происходит в красном черном дереве ...
+0
Спасибо. Итак, если мы сделали удаление на узле более высокого уровня, у которого есть поддерево, то каково время O, чтобы перестроить черные высоты для всех узлов вниз? – user3085336
+0
На самом деле я не прошу удаления, я спрашиваю о времени, которое требуется, чтобы перестроить черные высоты для каждого узла после удаления узла сверху, например, например, root. – user3085336
+0
Да, удаление/перестановка будет стоить вам журнала (N), но не каждый узел должен будет иметь новую высоту обязательно, потому что когда вы удаляете, не все высоты обязательно меняются ... Я добавлю еще одну ссылку, чтобы показать, как вставка/удаление для красных черных деревьев работает –
Я не понимаю вопроса. Я не думаю, что что-то вроде «присвоения черных высот» является частью алгоритма. – svick
'какая временная сложность для назначения высоты черного для каждого узла, когда мы делаем такой процесс, как вставка? Это не вы делаете, когда вставляете в красно-черное дерево? –
Я имею в виду, если вы удалите узел, какое время нужно обновлять черными высотами для других узлов. Рассмотрим узел, который мы удаляем, является корневым узлом. Какое время требуется для изменения высоты черного для остальных узлов? – user3085336