Застосування бінарного дерева пошуку з фіксованою висотою для прискорення обробки одновимірних масивів

Abstract

EN: Topicality. Nowadays, binary search trees are widely used to speed up searching, sorting, and selecting array elements. But the computational complexity of searching using a binary tree is proportional to its height, which depends on the sequence of processing the elements of the array. In order to reduce the height of a tree, its balancing is periodically carried out, which is a long process,, thus, the development of alternative methods of controlling the height of a binary tree is currently an actual scientific task. Objective. Development of algorithms for the formation and use of a binary tree with a fixed height to accelerate the search for an element in an array and to determine arbitrary i-th order statistics, in particular, the median of the array. Method. In this study, it is proposed to set the fixed height of the binary search tree by one greater than the minimum possible height of the binary tree to accommodate all the elements of the array because increasing the fixed height leads to excessive RAM consumption, and decreasing it slows down tree modifications. The formation of such trees is similar to the balancing of trees but, unlike it, the recursive movement of nodes in them is performed only when the corresponding subtree is completely filled. For a binary search tree with a fixed height, RAM is allocated once when it is created, immediately under all possible nodes of a binary tree with a given height. This allows to avoid allocating and freeing memory for each node of the tree and store the values of the nodes in a one-dimensional array without using pointers. The results. Our experiments showed that in order to speed up the search of elements and to determine the i-th order statistics of frequently changing unordered arrays, it is advisable to additionally form a binary search tree with a fixed height. To initialize this tree, it is advisable to use a sorted copy of the keys of the array elements, and not to insert them one by one. For example, the use of a binary tree with a fixed height accelerates the search of medians of such arrays by more than 7 times compared to the method of two binary pyramids and additionally accelerates the redistribution of compressed data between modified DEFLATE-blocks in the process of progressive hierarchical lossless compression of images of the ACT set by an average of 2.92%. Conclusions. To determine medians or i-th order statistics of individual unrelated arrays and subarrays, instead of known sorting methods, it is advisable to use Hoare partitioning with exchange over long distances as it rearranges only individual elements and does not order the entire array completely. In order to determine the medians of the sequence of nested subarrays, ordered by the growth of their length, it is worth using the method of two binary pyramids because they are oriented to rapid addition of new elements. To find medians or i-th order statistics after changes or removal of elements of an unordered array, it is advisable to use a binary search tree for the keys of array elements with a fixed height as such fixing prevents uncontrolled growth of the number of comparison operations and makes it possible to process the tree without using instructions. UK: Актуальність. На сьогодні для прискорення пошуку, сортування та відбору елементів масивів широко використовуються бінарні дерева пошуку. Але обчислювальна складність пошуку з використанням бінарного дерева пропорційна його висоті, яка, в свою чергу, залежить від послідовності опрацювання елементів масиву. Для зменшення висоти дерева періодично виконують його балансування, яке є тривалим процесом, тому розробка альтернативних способів контролю за висотою бінарного дерева є на сьогодні актуальним науковим завданням. Мета. Розробка принципів та відповідних алгоритмів формування та використання бінарного дерева з фіксованою висотою для прискорення пошуку елемента в масиві та визначення довільної i-ї порядкової статистики, зокрема, медіани масиву. Метод. В дослідженні запропоновано встановлювати фіксовану висоту бінарного дерева пошуку на одиницю більшою від мінімально можливої висоти бінарного дерева для розміщення всіх елементів масиву, адже збільшення фіксованої висоти призводить до зайвих витрат оперативної пам’яті, а зменшення – сповільнює модифікації дерева. Формування таких дерев подібне до балансування дерев, але, на відміну від нього, рекурсивне переміщення вузлів у них виконується лише тоді, коли відповідне піддерево заповнене повністю. Для бінарного дерева пошуку з фіксованою висотою оперативна пам’ять виділяється один раз при його створенні – відразу під всі можливі вузли бінарного дерева заданої висоти. Це дає змогу уникнути операцій виділення та звільнення пам’яті під кожен вузол дерева та зберігати значення вузлів в одновимірному масиві без використання вказівок. Результати. Наші експерименти показали, що для прискорення пошуку елементів та визначення i-тих порядкових статистик часто змінюваних невпорядкованих масивів доцільно додатково формувати бінарне дерево пошуку з фіксованою висотою. Для ініціалізації цього дерева доцільно використати відсортовану копію ключів елементів масиву, а не вставляти їх почергово. Використання бінарного дерева з фіксованою висотою прискорює, наприклад, пошук медіан таких масивів більш ніж в 7 разів відносно методу двох бінарних пірамід та додатково прискорює перерозподіл стиснутих даних між модифікованими DEFLATE-блоками в процесі прогресуючого ієрархічного стиснення без втрат зображень набору ACT в середньому на 2,92%. Висновки. Для визначення медіан чи i-тих порядкових статистик окремих непов’язаних масивів та підмасивів замість відомих методів сортування доцільно використовувати розбиття Hoare з обміном на великих відстанях, оскільки воно переставляє лише окремі елементи, а не впорядковує весь масив повністю. З метою визначення медіан послідовності вкладених підмасивів, впорядкованих за зростанням їх довжини, варто застосовувати метод двох бінарних пірамід, адже вони орієнтовані на швидке доповнення новими елементами. Для знаходження медіан чи i-тих порядкових статистик після змін чи вилучень елементів невпорядкованого масиву доцільно використати бінарне дерево пошуку ключів елементів масиву з фіксованою висотою, оскільки таке фіксування запобігає неконтрольованому зростанню кількостей операцій порівняння та дає змогу обробляти дерево без використання вказівок.