APPLICATION OF BINARY SEARCH TREE WITH FIXED HEIGHT TO ACCELERATE PROCESSING OF ONE-DIMENSIONAL ARRAYS

Abstract

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.