сложность превращения отсортированного массива в дерево 2-4 B

Question

Какая простота превращения отсортированного массива размера n в допустимое дерево 2-4 B?

Что было бы, если бы массив не был отсортирован.

Я считаю,что первый ответ должен быть O(logn) (столько разделений, что нам нужно сделать), а второй ответ должен быть O (nlogn + logn) = O (nlogn) из-за сортировки.

Спасибо.

Answer 1

Вы можете определенно преобразовать отсортированный массив в дерево 2-4 за O (n) раз.См. Построение красно-черных деревьев Ральфа Хинце для деталей.Его алгоритмы написаны в терминах красно-черных деревьев, но красно-черные деревья по сути такие же, как 2-4 дерева (черный узел с двумя черными дочерними элементами - это 2 узла, черный узел с одним красным дочерним элементом - это 3 узлаи черный узел с двумя красными дочерними элементами - это 4 узла).

И, да, если массив не отсортирован, вы застрянете за O (n log n) времени (если вы ничего не знаетеособенно о данных, которые позволяют сортировать их быстрее, чем за O (n log n)).

Answer 2

Что ж, если вы что-то делаете с n предметами, вполне вероятно, что вам придется потратить как минимум O(n) время на выполнение заданий.

Первое, о чем я подумал, - это прокрутить все n предметов и вставить каждый в дерево. Поскольку вставка O(log n), это O(n * log n) время ... но она полностью игнорирует, отсортированы ли ваши n элементы.

Если ваши n элементы отсортированы, вы, вероятно, сможете построить двоичное дерево поиска за O(n) время. Бьюсь об заклад, аналогичная вещь может работать для дерева 2-4 B.

Answer 3

Хитрость для преобразования упорядоченного списка в любое дерево состоит в следующем:

1. Учитывая число элементов N, напишите функцию (т.е. shape(N)), которая способнаопределения количества элементов в каждом поддереве (например, для дерева AVL, shape(6) -> [2, 3], когда один элемент входит в узел).

2. Написать (рекурсивную) функцию, котораяберет N элементов из начала списка и возвращает поддерево, содержащее эти элементы, и указатель на подсписок, содержащий оставшиеся элементы.