Сортировка BST по O (n) с использованием постоянной памяти

Question

Это не домашняя работа.Просто интересная задача:)

При условии полного бинарного поиска три представлены массивом.Сортируйте массив по 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

Answer 1

Возможно, люди, называющие это домашним заданием, возможно, еще не пытались его решить.

Мы используем следующее как подпрограмму:

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).

Что это работает, можно доказать по индукции.

Answer 2

Думая о варианте O(1) на месте, но пока вот решение O(N)

O(N) космическое решение

Если вы можете использовать выходной массив 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]"
    }
}

Приложение

• Источник и вывод на ideone.com