Общее дерево в бинарную сложность преобразования деревьев

Question

Какова сложность времени и пространства преобразования общего дерева в бинарное?!

Спасибо

Answer 1

Я не знаю, что вы имеете в виду под "General Tree". Несмотря на это, сложность внедрения в сбалансированное бинарное дерево O(log n), куда n это количество предметов, которые в настоящее время находятся в дереве, поэтому построение полного дерева из некоторых списков предметов будет O(n log n), куда n это общее количество предметов, которые будут вставлены.

Вам также придется включить время, необходимое для получения предметов от другого дерева. Это время зависит от типа дерева, которое у вас есть. Ради аргумента я предполагаю, что вы можете пройти через это в линейное время, поэтому получение данных из существующего дерева O(n).

Это делает вашу общую сложность времени O(n + (n log n)).

Требуется дополнительное пространство n * sizeof(node), куда sizeof(node) размер вашего бинарного дерева. Обратите внимание, что если элементы, хранящиеся в узлах «общего дерева», являются указателями, вам не придется платить стоимость копирования фактических объектов-просто накладные расходы бинарного дерева, который обычно представляет собой три указателя: The Данные, ссылка левого ребенка и ссылка на правую дочернюю связь.