Abstract: https://doi.org/10.24412/cl-35065-2022-1-01-30 1. Мы рассмотрим новый быстрый алгоритм построения двоичного дерева поиска для заданного набора чисел. Алгоритм имеет линейную временную сложность, если этот набор чисел упорядочен. Алгоритм строит двоичное дерево поиска минимально возможной высоты, причем это дерево является полным в том смысле, что все уровни, кроме, возможно, самого нижнего, полностью заполнены. Алгоритм не использует рекурсивных вызовов функций и допускает простую эффективную параллелизацию. При сравнении производительности реализаций на языке R, в рассмотренных примерах новый алгоритм оказался более чем в 10 раз быстрее классического алгоритма Вирта (рекурсивно строящего левое и правое поддерево). 2. Мы рассмотрим алгоритм случайного выбора m объектов из n без возвращения. Алгоритм использует двоичное дерево поиска и имеет среднюю временную сложность O(m log m).

Cite: Рузанкин П.С.
Алгоритмы с двоичными деревьями поиска
Марчуковские научные чтения 2022 03-07 окт. 2022