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

Question

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

Благодаря

Answer 1

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

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

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

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