Вид BST в O (n) использование постоянной памяти
Это не домашняя работа. Просто интересная задача :)
Учитывая полный двоичный поиск три represensted массивом. Отсортируйте массив в O (n) использование постоянной памяти.
Пример:
Дерево:
8
/ \
4 12
/\ / \
2 6 10 14
/\ /\ /\ /\
1 3 5 7 9 11 13 15
Массив: 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15
Вывод: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
2 ответа
Возможно, люди, называющие это домашним заданием, вероятно, еще не пробовали решить эту проблему.
В качестве подпрограммы мы используем следующее:
Given an array a1 a2 ... an b1 b2 .. bn, convert in O(n) time and O(1) space to
b1 a1 b2 a2 ... bn an
Решение для этого можно найти здесь: http://arxiv.org/abs/0805.1598
Мы используем это следующим образом.
Выполните указанное выше чередование для первых 2 ^ (k + 1) - 2 элементов, начиная с k = 1, повторяя для k = 2, 3 и т. Д., Пока не пройдете конец массива.
Например, в вашем массиве мы получаем (чередование наборов, обозначенных скобками)
8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15
[ ][ ]
4, 8, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 (k = 1, interleave 2)
[ ][ ]
2, 4, 6, 8, 10, 12, 14, 1, 3, 5, 7, 9, 11, 13, 15 (k = 2, interleave 6)
[ ][ ]
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 (k = 3, interleave 14)
Таким образом, общее время равно n + n / 2 + n / 4 + ... = O (n). Используемое пространство - O (1).
То, что это работает, можно доказать по индукции.
Думаю о варианте
O (1)на месте, но пока вот решениеO (N)
An O (N) space solution
Если вы можете использовать выходной массив O (N) , то вы можете просто выполнить обход по порядку . Каждый раз, когда вы посещаете узел, добавляйте его в выходной массив.
Вот реализация на Java:
import java.util.*;
public class Main {
static void inorder(int[] bst, List<Integer> sorted, int node) {
if (node < bst.length) {
inorder(bst, sorted, node * 2 + 1);
sorted.add(bst[node]);
inorder(bst, sorted, node * 2 + 2);
}
}
public static void main(String[] args) {
int[] bst = { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 };
final int N = bst.length;
List<Integer> sorted = new ArrayList<Integer>();
inorder(bst, sorted, 0);
System.out.println(sorted);
// prints "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]"
}
}