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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Приклади

[ред. | ред. код]

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

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

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

Джерела

[ред. | ред. код]