Структури даних: тренувальні питання з поясненнями

1Що таке структура даних

Структура даних — це спосіб організувати дані в пам’яті так, щоб певні операції були швидкими: знайти елемент, додати його, видалити.

Жодна структура не є швидкою в усьому. Вибір структури — це вибір того, які операції мають бути дешевими. Їхню вартість записують у нотації Big O, де n — кількість елементів.

Двома базовими будівельними блоками є масив і зв’язний список.

Масив зберігає елементи в одному блоці пам’яті один за одним. Комп’ютер може обчислити, де розташований елемент i, тому читання a[i] займає O(1). Вставка на початок означає зсув кожного елемента: O(n).

Зв’язний список зберігає кожен елемент у вузлі з вказівником на наступний вузол. Останній вказівник — null. Вставка в голову (h) змінює лише один вказівник: O(1). Але щоб дістатися елемента i, треба пройти i вказівників: O(n).

Двозв’язний список має також вказівник на попередній вузол, тож можна йти в обидва боки.

2Стеки та черги

Стек схожий на стопку тарілок: додавати й забирати можна лише згори. Останній зайшов — першим вийшов: LIFO.

• push кладе елемент нагору, pop забирає верхній елемент, peek читає верхній, не забираючи. Усі O(1).
• Застосування: функція скасування в редакторі, стек викликів програми, перевірка збалансованості дужок, пошук углиб.

Черга схожа на чергу до каси: стаєте в кінець, виходите з початку. Перший зайшов — першим вийшов: FIFO.

• enqueue додає в кінець, dequeue забирає з початку. Обидві O(1).
• Застосування: завдання друку, повідомлення, що чекають обробки, пошук вшир.

Дек (deque, двостороння черга) дозволяє додавати й забирати з обох кінців. Черга з пріоритетом завжди першим забирає елемент із найвищим пріоритетом; її зазвичай будують як купу.

3Дерева, купи, геш-таблиці та графи

Дерево має один верхній вузол — корінь. Кожен інший вузол має рівно одного батька. Вузли без нащадків — листки. Дерево з n вузлами має n − 1 ребро.

У бінарному дереві кожен вузол має щонайбільше двох нащадків. Бінарне дерево пошуку (BST) додає правило: ключі в лівому піддереві менші за вузол, ключі в правому піддереві більші.

Пошук у BST іде одним шляхом донизу, тож коштує O(висота). Збалансоване дерево (AVL, червоно-чорне) тримає висоту близько log₂ n. Ключі, вставлені у відсортованому порядку, утворюють ланцюжок висотою n.

Купа — це бінарне дерево, де кожен батько менший за нащадків (min-купа) або більший (max-купа). Мінімум або максимум — у корені, а вставка й видалення коштують O(log n).

Геш-таблиця зберігає пари «ключ–значення». Геш-функція перетворює ключ на індекс, тому вставка й пошук займають у середньому O(1). Два ключі з однаковим індексом — це колізія, яку розв’язують ланцюжками (список на комірку) або відкритою адресацією (спробувати іншу комірку).

Граф має вершини, з’єднані ребрами, які можуть мати напрямок або вагу. Його зберігають як матрицю суміжності, пам’ять O(V²), або як списки суміжності, O(V + E).

4Метод крок за кроком

Запитання часто описують завдання й питають, яка структура підходить, або питають, як виглядає структура після кількох операцій.

1. Знайдіть операцію, що має бути швидкою: доступ за позицією, за ключем, найновіший елемент, найстаріший елемент, найменший елемент або діапазон.
2. Зіставте її зі структурою: індекс → масив, ключ → геш-таблиця, найновіше → стек, найстаріше → черга, найменше чи найбільше → купа, впорядкований порядок або діапазони → збалансоване дерево пошуку.
3. Перевірте вартість інших операцій, потрібних завданню, у нотації Big O.
4. Для запитання на трасування виконуйте операції по одній і записуйте стан після кожної.
5. Звірте кінцевий стан із правилом структури: LIFO, FIFO, порядок BST або порядок купи.

5Розв’язаний приклад

Простежте кожен крок. Спробуйте передбачити наступний, перш ніж його відкрити.

6Типові помилки

• Плутати LIFO і FIFO. Стек повертає найновіший елемент, черга — найстаріший.
• Думати, що зв’язний список дає швидкий доступ за індексом. Він мусить іти від голови.
• Вважати, що BST завжди має O(log n). Лише збалансоване дерево; відсортовані вставки дають O(n).
• Забувати про колізії в геш-таблиці. O(1) — це в середньому, а не в найгіршому випадку.
• Плутати обходи. Прямий (preorder): спочатку вузол. Симетричний (in-order): вузол посередині. Зворотний (postorder): вузол останнім.
• Використовувати матрицю суміжності для великого розрідженого графа. Вона марнує O(V²) пам’яті.

7Як виглядають екзаменаційні запитання

• Легкий: ключові терміни та факти. LIFO і FIFO, що таке вузол, корінь чи листок, правило BST, що робить геш-функція.
• Середній: застосування понять. Яка структура підходить для завдання, результат push і pop або вставок у BST, обходи дерев, геш-таблиця з лінійним пробінгом, вартість у нотації Big O.
• Складний: випадки й аналіз. Збалансовані дерева, купи в масивах, B-дерева, префіксні дерева (trie), union-find, фільтри Блума та проєкти на кшталт LRU-кешу.

Для купи, збереженої в масиві з індексу 0, нащадки індексу i розташовані за індексами 2i + 1 і 2i + 2, а батько — за ⌊(i − 1) / 2⌋.