Параллельное построение двоичного дерева на основе сортировки

Введение. Разработаны алгоритмы параллельного построения двоичного дерева. Алгоритмы выполнены на основе сортировки и описаны в конструктивной форме. Для множества из N элементов временная сложность имеет оценки T(R) = O(1) и T(R) = O(log₂ N), где число процессоров R = (N²-N)/2. Дерево строится со свойством единственности. Алгоритмы инвариантны относительно вида входной последовательности. Целью работы являлась разработка и исследование способов ускорения процесса организации и преобразований древовидных структур данных на основе алгоритмов устойчивой максимально параллельной сортировки для их применения к базовым операциям информационного поиска в базах данных.

Материалы и методы. Взаимно однозначное соответствие множества входных элементов и построенного для него двоичного дерева устанавливается при помощи устойчивой адресной сортировки. Сортировка обладает максимальным параллелизмом, в операторной форме устанавливает взаимно однозначное соответствие входных и выходных индексов. На этой основе разрабатываются методы взаимного преобразования двоичных структур данных.

Результаты исследования. Получен эффективный параллельный алгоритм построения двоичного дерева на основе адресной сортировки с временной сложностью T(N²) = O(log₂ N). От известных аналогов алгоритм отличается структурой и логарифмической оценкой временной сложности, позволяющей достигать ускорения аналогов порядка O(N^α), α≥1. В качестве усовершенствованного варианта предложена модификация алгоритма, обеспечивающая максимально параллельное построение двоичного дерева на основе устойчивой адресной сортировки и априорного вычисления хранимых индексов корней поддеревьев. Алгоритм отличается структурой и оценкой временной сложности T(1) = O(1). Аналогичная оценка достигается в последовательном варианте модифицированного алгоритма, что позволяет достигать ускорения известных аналогов порядка O(N^α), α>1.

Обсуждения и заключение. Полученные результаты направлены на организацию эффективных способов динамической обработки баз данных. Предложенные способы и алгоритмы могут составить алгоритмическую основу для ускоренного детерминированного поиска в реляционных базах данных и информационных системах.

1. Ромм, Я. Е. Сравнение слов с единичной временной сложностью / Я. Е. Ромм, Д. А. Чабанюк // Известия Южного федер. ун-та. Технические науки. — 2014. — №7 (156). — С. 230–238.

2. Ромм, Я. Е. Параллельная сортировка слиянием по матрицам сравнений. II / Я. Е. Ромм // Кибернетика и системный анализ. — 1995. — № 4. — С. 13–37.

3. Ромм, Я. Е. Построение двоичного дерева на основе параллельной сортировки / Я. Е. Ромм, Д. А. Чабанюк // Фундаментальные исследования. — 2015. — Т. 8., № 3. — С. 509–513.

4. Ромм, Я. Е. Параллельное построение двоичного дерева на основе сортировки / Я. Е. Ромм, Д. А. Чабанюк // Аспекты развития науки, образования и модернизации промышленности : матер. Всеросс. научно-практ. конф. — Таганрог, 2017. — Т. 1. — С. 77–84.

5. Laganà A. Computational Science and Its Applications: Lecture Notes in Computer Science / A. Laganà, V. Kumar, C. Tan. — Assisi: Springer Science & Business Media, 2004. — 1044 p. — https://doi.org/10.1007/b98048

6. Chalermsook P. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015) / P. Chalermsook, M. Goswami; eds. – Piscataway, NJ: IEEE, 2015. – 410-423 p. – DOI: 10.1109/FOCS.2015.98

7. Гавриков, А. В. Т-неприводимые расширения для ориентированных бинарных деревьев / А. В. Гавриков // Компьютерные науки и информационные технологии. — 2016. — № 6. — С. 123–125. — https://doi.org/10.17223/20710410/34/6

8. Гриценко, Н. С. Построение двоичного дерева на основе модифицированной схемы хранения деревьев общего вида «left child»-«right sibling» (LCRS) / Н. С. Гриценко, Ю. С. Белов // Инженерный журнал : наука и инновации. — 2014. — № 3. — С. 75–84. — https://doi.org/10.18698/2308-6033-2014-3-1281.

9. Amir A. Adaptive dictionary matching / A. Amir, M. Farach // Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on. — IEEE, 1991. — P. 760-766. — https://doi.org/10.1109/SFCS.1991.185445

10. Fischer J. Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE / J. Fischer, V. Heun // Combinatorial Pattern Matching – Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. – Vol. 4009. – P. 36-48.

11. Institute of Electrical and Electronics Engineers. Pattern-Avoiding Access in Binary Search Trees / Computer Society // 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015). – 2015. – № 56. — P. 410-423. https://doi.org/10.1109/FOCS.2015.32