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

Ответ 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).

Это можно доказать индукцией.

Ответ 2

Думая о варианте O(1) in-place, но теперь здесь O(N) solution

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

Если вы можете использовать выходной массив O(N), вы можете просто выполнить обход посторонних. Каждый раз, когда вы посещаете node, добавьте его в выходной массив.

Здесь реализация в 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