Пошук академічних текстів

Інформація × Реєстраційний номер 2125U003976, Матеріали видань та локальних репозитаріїв Категорія Опубліковано, Стаття Назва роботи ЗАСТОСУВАННЯ БІНАРНОГО ДЕРЕВА ПОШУКУ З ФІКСОВАНОЮ ВИСОТОЮ ДЛЯ ПРИСКОРЕННЯ ОБРОБКИ ОДНОВИМІРНИХ МАСИВІВ Автор Шпортько О. В.Бомба А. Я.Shportko A. V.Bomba A. Ya. Дата публікації 10-04-2025 Постачальник інформації Журнал "Радіоелектроніка, інформатика, управління" (Національний університет "Запорізька політехніка") Першоджерело https://ric.zp.edu.ua/article/view/324550 Видання National University "Zaporizhzhia Polytechnic" Опис Актуальність. На сьогодні для прискорення пошуку, сортування та відбору елементів масивів широко використовуються бінарні дерева пошуку. Але обчислювальна складність пошуку з використанням бінарного дерева пропорційна його висоті, яка, в свою чергу, залежить від послідовності опрацювання елементів масиву. Для зменшення висоти дерева періодично виконують його балансування, яке є тривалим процесом, тому розробка альтернативних способів контролю за висотою бінарного дерева є на сьогодні актуальним науковим завданням.Мета. Розробка принципів та відповідних алгоритмів формування та використання бінарного дерева з фіксованою висотою для прискорення пошуку елемента в масиві та визначення довільної i-ї порядкової статистики, зокрема, медіани масиву.Метод. В дослідженні запропоновано встановлювати фіксовану висоту бінарного дерева пошуку на одиницю більшою від мінімально можливої висоти бінарного дерева для розміщення всіх елементів масиву, адже збільшення фіксованої висоти призводить до зайвих витрат оперативної пам’яті, а зменшення – сповільнює модифікації дерева. Формування таких дерев подібне до балансування дерев, але, на відміну від нього, рекурсивне переміщення вузлів у них виконується лише тоді, коли відповідне піддерево заповнене повністю. Для бінарного дерева пошуку з фіксованою висотою оперативна пам’ять виділяється один раз при його створенні – відразу під всі можливі вузли бінарного дерева заданої висоти. Це дає змогу уникнути операцій виділення та звільнення пам’яті під кожен вузол дерева та зберігати значення вузлів в одновимірному масиві без використання вказівок.Результати. Наші експерименти показали, що для прискорення пошуку елементів та визначення i-тих порядкових статистик часто змінюваних невпорядкованих масивів доцільно додатково формувати бінарне дерево пошуку з фіксованою висотою. Для ініціалізації цього дерева доцільно використати відсортовану копію ключів елементів масиву, а не вставляти їх почергово. Використання бінарного дерева з фіксованою висотою прискорює, наприклад, пошук медіан таких масивів більш ніж в 7 разів відносно методу двох бінарних пірамід та додатково прискорює перерозподіл стиснутих даних між модифікованими DEFLATE-блоками в процесі прогресуючого ієрархічного стиснення без втрат зображень набору ACT в середньому на 2,92%.Висновки. Для визначення медіан чи i-тих порядкових статистик окремих непов’язаних масивів та підмасивів замість відомих методів сортування доцільно використовувати розбиття Hoare з обміном на великих відстанях, оскільки воно переставляє лише окремі елементи, а не впорядковує весь масив повністю. З метою визначення медіан послідовності вкладених підмасивів, впорядкованих за зростанням їх довжини, варто застосовувати метод двох бінарних пірамід, адже вони орієнтовані на швидке доповнення новими елементами. Для знаходження медіан чи i-тих порядкових статистик після змін чи вилучень елементів невпорядкованого масиву доцільно використати бінарне дерево пошуку ключів елементів масиву з фіксованою висотою, оскільки таке фіксування запобігає неконтрольованому зростанню кількостей операцій порівняння та дає змогу обробляти дерево без використання вказівок. Додано в НРАТ 2026-02-26 Закрити