Попередній обхід масиву

Мені цікаво, якщо є алгоритм, який, враховуючи відсортований масив, дозволяє побудувати двійкове дерево пошуку в лінійний час?

Я зіткнувся з проблемою, коли у мене є близько 8 мільйонів елементів у файлі, які повинні бути завантажені в BST, так що O (n) буде значно краще O (n log n), якщо це можливо.

0
Це не питання дослідницького рівня в теоретичній інформатиці. cstheory.stackexchange.com/help/on-topic
додано Автор Justin, джерело
Це краще питання для обміну стеками
додано Автор prince, джерело

2 Відповіді

Я думаю, що найкращим способом є створення рекурсивного алгоритму. Ви можете розділити ваш вхід наполовину (прибл.) І не вмикати центральний елемент. Потім ви рекурсивно побудуєте дерево з лівим підводом, який буде лівою дитиною центрального елемента, і еквівалентно дереву, яке випливає з правого підмасива, буде правильна дитина.

Індукцією можна довести, що отримане дерево врівноважено, оскільки ви будуєте дерева однакового розміру з кожної сторони (+/- 1 вузол). Також легко довести, що в результаті виходить двійкове дерево пошуку, за конструкцією.

Що стосується складності, кожен вузол у рекурсивному дереві виконання приймає постійний час. Оскільки у вас є число вузлів, пропорційні кількості елементів у вашому введенні, то алгоритм O (n).

3
додано
Згоден Складність є лінійною і простір логарифмічний.
додано Автор Ramesh Soni, джерело

Хоча це не зовсім те, що ви запитали, ви також можете побудувати збалансовані дерева з впорядкованих даних в режимі онлайн. Тобто ви можете пройти свій масив зліва направо, створивши часткові результати, і якщо хтось попросив вас зупинитися після k елементів, ви могли б завершити створення дерева в журналі k Час (із загальним часом O ( k ), а додаткове сховище вимагає O (log k ).

Щоб вказати це іншим способом, ви могли б прочитати дані з труби і створити дерево (через допоміжні структури), не спершу поклавши його все в масив (тим самим уникаючи O ( n ) пам'яті, необхідної для масив). Алгоритми для цього для червоно-чорних дерев можуть бути знайдені приховані в реалізації бібліотеки NJ бібліотеки червоно-чорних наборів. Теоретичні основи можна знайти в Структурах чисто функціональних даних Окасакі .

Я знайшов аналогічний алгоритм для дерев AVL (висоти), але я ще не опублікував його, оскільки не знаю, чи є він частиною опублікованої літератури для дерев AVL.

2
додано