I.4. Представяне и основни операции с нелинейни структури от данни: двоични дървета, коренови дървета, дървета за търсене

I. Обща част · Тема 4 · Подготовка по конспекта на СУ / ФМИ № 19, 2026/2027

Обхват от конспекта

Представяне и основни операции с нелинейни структури от данни: двоични дървета, коренови дървета, дървета за търсене. Графи. Особености и приложения. Видове обхождания. Построяване на покриващо дърво на граф. Оценка на времевата сложност.

Цел на подготовката

Да можеш самостоятелно да обясниш понятията и връзките между тях, да дадеш собствен пример и да приложиш изброените подходи в задача.

Примерна писмена разработка

Авторски образец за подготовка по тази тема. Не е официален отговор, утвърден от СУ, и не задава задължителен обем или схема за оценяване. Чети го за разбиране; упражнявай възпроизвеждане със собствени примери и сверявай с пълния обхват на конспекта.

Дървета и представяне

Дървото е свързан неориентиран граф без цикли. Кореновото дърво има избран корен, който определя отношенията родител–дете, предшественик–наследник, дълбочина и височина. Лист е връх без деца. Двоичното дърво има най-много две разграничени деца — ляво и дясно. То може да се представи с възли и указатели; при подходяща форма, например пълно двоично дърво, е удобно представяне чрез масив. За общо кореново дърво могат да се използват списъци от деца или връзки „първо дете–следващ брат“.

При обхождане в дълбочина на двоично дърво се различават preorder — корен, ляво, дясно; inorder — ляво, корен, дясно; и postorder — ляво, дясно, корен. Обхождането по нива използва опашка. Всяко посещаване на всички n възела е O(n); рекурсивният стек при дълбочинно обхождане е O(h), където h е височината. Обикновеното inorder е специфично за подредени леви и десни деца, а не универсално обхождане на произволен граф.

Двоично дърво за търсене

В двоично дърво за търсене ключовете в лявото поддърво са по-малки от ключа във възела, а десните са по-големи, при предварително определено правило за равните ключове. Търсенето сравнява ключа и избира едно поддърво. Вмъкването следва същия път. При изтриване се разглеждат случаи с нула, едно и две деца; при две деца стойността може да се замени с inorder наследник и той да се изтрие от подходящото място.

Основните операции са O(h). Балансираното дърво има h=O(log n), докато небалансирано дърво може да се изроди във верига с h=O(n). Следователно логаритмичната сложност не следва само от определението „двоично“. Inorder обхождането на дърво за търсене извежда ключовете в сортиран ред.

Графи, обхождания и покриващи дървета

Графът G=(V,E) задава върхове и ребра. Той може да е ориентиран или неориентиран, тегловен или нетегловен. Матрицата на съседство използва O(|V|²) памет и дава непосредствена проверка за ребро; списъците на съседство използват O(|V|+|E|) и са подходящи за разредени графи. При ориентиран граф трябва да се уточни какъв вид достижимост или свързаност се изследва.

BFS използва опашка и посещава върховете по нарастващ брой ребра от началото; така намира най-кратки пътища в нетегловен граф. DFS използва рекурсия или явен стек и изследва докрай един клон. Маркирането на посетените върхове предотвратява повторна обработка при цикли. Със списъци на съседство и двете обхождания са O(|V|+|E|), а с матрица — O(|V|²).

Ребрата, с които за пръв път откриваме върховете на свързан неориентиран граф, образуват покриващо дърво с |V|−1 ребра. При несвързан граф повторното стартиране от непосетени върхове образува покриваща гора. Това не е непременно минимално покриващо дърво по тегло — последното е друга задача. Дърветата моделират йерархии и индекси, а графите — по-общи зависимости; представянето и инвариантите определят ефективността на алгоритмите.

Литературна опора

За сверяване с литературата от конспекта: позиции 2 и 5 в библиографията. Допълнително: MIT 6.006 — дървета и графи.

Уроци за четене

  1. Коренови и двоични дървета
  2. Обхождания на двоично дърво
  3. Двоично дърво за търсене
  4. Графи и представяне на съседство
  5. Обхождане в ширина и в дълбочина
  6. Покриващо дърво и времева сложност

Литература

Библиографски сведения и източници · Официален конспект. Конкретните раздели и страници ще се посочват към всеки разработен урок.

Примери и упражнения

Всеки урок има самостоятелна задача с четири отговора за самопроверка.

Писмена разработка и устни въпроси

Формулировката на темата може да служи като заглавие за тренировъчна писмена разработка, а подточките — като контролен списък за обхвата. Следният план е учебна препоръка, не официална схема за оценяване на СУ:

  1. Въведение: предмет, предназначение и място на темата.
  2. Точни определения, означения и основни понятия.
  3. Последователно изложение на подточките от конспекта и връзките между тях.
  4. Собствен пример, схема, алгоритъм или заявка според темата; обосновка на избора.
  5. Важни свойства, ограничения, сравнения и типични грешки.
  6. Кратко обобщение.

Опорният план е за преговор. Развитият отговор трябва да обяснява и обосновава, а не само да изброява термини. По конспекта писменият изпит включва два въпроса; не е уточнено как точно ще бъде формулиран билетът. При конкретен въпрос се води по неговото условие. Няма потвърдено изискване за определен брой страници.