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

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

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

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

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

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

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