Неявна структура даних

В інформатиці неявна структура даних або структура даних з дієвим використанням пам'яті — це структура даних, яка зберігає дуже мало інформації, окрім основних або обов’язкових даних: структура даних, яка вимагає низьких додаткових витрат. Їх називають «неявними», тому що позиція елементів має значення і впливає на зв'язок між елементами; це відмінно від використання вказівників для представлення явного зв’язку між елементами. Визначення «низьких додаткових витрат» відрізняються, але зазвичай це означає сталі накладні витрати — O (1). Менш обмежувальне визначення — це стисла структура даних^[en], яка припускає більші додаткові витрати.

Приклади[ред. | ред. код]

Прикладом може бути представлення відсортованого списку відсортованим масивом, який дозволяє здійснювати пошук у логарифмічному часі за допомогою двійкового пошуку . На противагу дереву пошуку, зокрема двійковому дереву пошуку, яке також дозволяє пошук у логарифмічному часі, але потребує вказівників. Відсортований масив дієвий лише як статична структура даних, бо модифікація списку відбувається повільно – на відміну від двійкового дерева пошуку – але не вимагає додаткового простору для дерева.

Важливий приклад неявної структури даних це представлення досконалого двійкового дерева у вигляді списку в порядку зростання глибини, тобто корінь, перший лівий дочірній, перший правий дочірній, перший лівий дочірній для першого лівого дочірнього елемента і т.д.

Це можна узагальнити до повного двійкового дерева (де останній рівень може бути неповним), яке дає найвідоміший приклад неявної структури даних, а саме двійкову купу, яка слугує неявною структурою даних для черги з пріоритетом. Це складніший приклад ніж попередні, тому що він дозволяє виконувати кілька операцій і є ефективною динамічною структурою даних (вона дозволяє дієве змінювання даних): не тільки top, але також insert і pop .

Ця стаття не містить посилань на джерела. Ви можете допомогти поліпшити цю статтю, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (вересень 2022)

В іншому мовному розділі є повніша стаття Implicit data structure(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської. (вересень 2022) Дивитись автоперекладену версію статті з мови «англійська». Перекладач повинен розуміти, що відповідальність за кінцевий вміст статті у Вікіпедії несе саме автор редагувань. Онлайн-переклад надається лише як корисний інструмент перегляду вмісту зрозумілою мовою. Не використовуйте невичитаний і невідкоригований машинний переклад у статтях української Вікіпедії! Машинний переклад Google є корисною відправною точкою для перекладу, але перекладачам необхідно виправляти помилки та підтверджувати точність перекладу, а не просто скопіювати машинний переклад до української Вікіпедії. Не перекладайте текст, який видається недостовірним або неякісним. Якщо можливо, перевірте текст за посиланнями, поданими в іншомовній статті. Докладні рекомендації: див. Вікіпедія:Переклад.