Неявна структура даних
В інформатиці неявна структура даних або структура даних з дієвим використанням пам'яті — це структура даних, яка зберігає дуже мало інформації, окрім основних або обов’язкових даних: структура даних, яка вимагає низьких додаткових витрат. Їх називають «неявними», тому що позиція елементів має значення і впливає на зв'язок між елементами; це відмінно від використання вказівників для представлення явного зв’язку між елементами. Визначення «низьких додаткових витрат» відрізняються, але зазвичай це означає сталі накладні витрати — O (1). Менш обмежувальне визначення — це стисла структура даних[en], яка припускає більші додаткові витрати.
Прикладом може бути представлення відсортованого списку відсортованим масивом, який дозволяє здійснювати пошук у логарифмічному часі за допомогою двійкового пошуку . На противагу дереву пошуку, зокрема двійковому дереву пошуку, яке також дозволяє пошук у логарифмічному часі, але потребує вказівників. Відсортований масив дієвий лише як статична структура даних, бо модифікація списку відбувається повільно – на відміну від двійкового дерева пошуку – але не вимагає додаткового простору для дерева.
Важливий приклад неявної структури даних це представлення досконалого двійкового дерева у вигляді списку в порядку зростання глибини, тобто корінь, перший лівий дочірній, перший правий дочірній, перший лівий дочірній для першого лівого дочірнього елемента і т.д.
Це можна узагальнити до повного двійкового дерева (де останній рівень може бути неповним), яке дає найвідоміший приклад неявної структури даних, а саме двійкову купу, яка слугує неявною структурою даних для черги з пріоритетом. Це складніший приклад ніж попередні, тому що він дозволяє виконувати кілька операцій і є ефективною динамічною структурою даних (вона дозволяє дієве змінювання даних): не тільки top, але також insert і pop .
- Дональд Кнут. Sorting and Searching // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — ISBN 0-201-89685-0.(англ.)
 | В іншому мовному розділі є повніша стаття Implicit data structure(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської. (вересень 2022)
|