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

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

Подробен авторски текст за подготовка по конспекта на СУ. Краткият вариант е запазен на основната страница на темата. За преговор използвай плана; за обосновка — определенията и разработените примери. Това не е официален изпитен образец.

Кратка разработка и уроци по темата · План за изпита · Покритие · Източници

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

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

Покритие на конспекта

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

  1. Представяне и основни операции с нелинейни структури от данни: двоични дървета, коренови дървета, дървета за търсене — 1. Коренови и двоични дървета; 3. Дървета за търсене и основни операции
  2. Графи — 4. Графи, особености, представяне и приложения
  3. Особености и приложения — 4. Графи, особености, представяне и приложения
  4. Видове обхождания — 2. Обхождания на дървета; 5. BFS, DFS и построяване на покриващо дърво
  5. Построяване на покриващо дърво на граф — 5. BFS, DFS и построяване на покриващо дърво
  6. Оценка на времевата сложност — 3. Дървета за търсене и основни операции; 5. BFS, DFS и построяване на покриващо дърво

Кратък план за изпита

  1. Кореново и двоично дърво; представяния и приложения.
  2. Обхождания и основни операции.
  3. Дърво за търсене: инвариант, търсене, вмъкване и изтриване.
  4. Граф, видове и представяния.
  5. BFS и DFS; покриващо дърво и гора.
  6. Сложност и разграничаване на произволно и минимално покриващо дърво.

1. Коренови и двоични дървета

Дървото е свързан неориентиран граф без цикли. Между всеки два върха има единствен прост път. Ако изберем корен, всеки друг връх има единствен родител, а върховете непосредствено под него са негови деца. Връх без деца е лист. Дълбочината е броят ребра от корена до върха; тук височината на дървото е максималната дълбочина. При тази конвенция дърво с един връх има височина нула.

Кореново дърво с произволен брой деца може да се представи чрез списък от деца във всеки възел, чрез масив от родители или чрез „първо дете — следващ брат“. В последното представяне двата указателя имат различни роли; то не превръща логически всяко дърво в двоично дърво за търсене. Приложения са файлови йерархии, организационни структури и синтактични дървета.

Двоичното дърво има най-много две разграничени позиции за наследници — лява и дясна. Възел с едно ляво дете и възел с едно дясно дете са различни структури. Свързаното представяне пази стойност и два указателя. Пълно или почти пълно дърво може да се съхранява в масив: при корен на индекс 0 децата на i са на 2i+1 и 2i+2, когато съществуват. За много разредено дърво този подход може да остави множество неизползвани позиции.

2. Обхождания на дървета

Обхождането посещава всеки възел по определен ред. При preorder обработваме корена, лявото и дясното поддърво. При inorder — лявото поддърво, корена и дясното; тази форма е естествено определена за двоично дърво. При postorder обработваме децата преди родителя. Обхождането по нива използва опашка и посещава върховете с нарастваща дълбочина.

       8
      / \
     3  12
    / \
   1   6
Двоично дърво за пример; наклонените линии са ребра родител–дете.

За показаното дърво preorder е 8,3,1,6,12; inorder е 1,3,6,8,12; postorder е 1,6,3,12,8; по нива — 8,3,12,1,6. Всеки алгоритъм посещава n възела за Θ(n), ако обработката на възел е O(1). Рекурсивните дълбочинни обхождания използват O(h) стек при височина h, а обхождането по нива пази фронт, чийто размер може да е Θ(n).

Postorder е подходящо за освобождаване на възли или оценяване на израз, чиито операнди са в поддърветата. Preorder позволява запис на родител преди потомците. Редът на обхождане има значение за задачата; няма универсално „най-добро“ обхождане.

3. Дървета за търсене и основни операции

В двоично дърво за търсене всички ключове в лявото поддърво са по-малки от ключа на възела, а в дясното — по-големи, ако не допускаме повторения. Правилото важи за цялото поддърво, не само за непосредствените деца. Ако се допускат равни ключове, трябва отделно да се определи представянето им, например брояч във възела. Inorder обхождането дава ключовете в сортиран ред.

При търсене сравняваме търсения ключ с текущия. Равенството приключва търсенето; иначе продължаваме само наляво или надясно. При липсваща връзка ключът не е намерен. Вмъкването следва същия път и добавя нов лист на първата празна позиция. Търсене на 6 в примера сравнява последователно с 8, 3 и 6.

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

Цената на търсене, вмъкване и изтриване е O(h). При балансиране h=O(log n), но обикновено небалансирано дърво може да се изроди във верига с h=n−1. Следователно твърдението „дърво за търсене винаги търси за O(log n)“ е невярно без условие за височината.

4. Графи, особености, представяне и приложения

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

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

5. BFS, DFS и построяване на покриващо дърво

BFS, търсенето в ширина, пази опашка. Началният връх се маркира при поставяне в нея. Когато извадим връх, разглеждаме съседите му; всеки още непосетен съсед маркираме, записваме родителя му и добавяме в опашката. Маркирането при добавяне предотвратява многократно поставяне. В нетегловен граф BFS намира пътища с минимален брой ребра от началото.

DFS, търсенето в дълбочина, продължава по непосетен съсед, преди да се върне към останалите. Използва рекурсия или явен стек. То е полезно за компоненти, откриване на цикли и топологично подреждане на ациклични ориентирани графи. DFS не гарантира най-къс път. И двата алгоритъма със списъци на съседство имат O(|V|+|E|) време при константен достъп до съседите и константна проверка/маркиране на посетен връх; при матрица обикновено O(|V|²). Допълнителната памет за маркировки, родители и фронт е O(|V|).

Нека неориентираният граф има върхове A,B,C,D и ребра AB, AC, BC, BD, CD. При BFS от A и азбучен ред на съседите родителските ребра са AB, AC, BD. Те свързват всички върхове, нямат цикъл и са точно |V|−1: получаваме покриващо дърво. При DFS със същия ред е възможно дървото AB, BC, CD. Различните обхождания могат да дадат различни валидни дървета.

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

6. Покриващо дърво не означава минимално по тегло

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

При тегла AB=1, AC=5, BC=2, BD=4, CD=1 горното BFS дърво струва 10. Дървото AB, BC, CD струва 4 и е минимално. Това показва защо изискването към задачата определя алгоритъма. Изпитният отговор трябва да свърже дефиницията на структурата, нейния инвариант, представянето, алгоритъма и оценката му, вместо да изброява сложности без условия.

Уточнения при четене на реализациите от учебника

Сверка със СУ 2: Коренови/двоични дървета: ориг. 157–185 / нов PDF 151–177; BST/AVL: ориг. 186–215 / нов PDF 177–206; графи: ориг. 224–243 / нов PDF 213–232; пътища: ориг. 244–249 / нов PDF 232–237.

Номериране на височината. Задача 29 в книгата, ориг. 175 / нов PDF 167–168, нарича depth броя върхове по най-дългия път: листът дава 1. В настоящата разработка височината е брой ребра и листът има височина 0. За непразно дърво стойностите се различават с единица; това е конвенция, която трябва да се заяви, не различен алгоритъм.

Баланс и копиране. AVL дървото пази разлика на височините на дясното и лявото поддърво в границите −1,0,1. След вмъкване/изтриване се обновяват балансите и при нужда се прави ротация, която запазва inorder реда. За ключовете 30,20,10 единична дясна ротация дава корен 20 с деца 10 и 30. Копирането трябва да запази и balance, а не само ключовете и връзките — това е поправено и проверено в отделния комплект.

Алгоритъм срещу конкретен интерфейс. Оценката O(h) за търсене в BST предполага преминаване към дете за O(1). Селекторите leftTree/rightTree в учебния клас могат да създават копие на поддървото. Ако алгоритъмът ги използва многократно, цената на копията се добавя и обичайното O(h) не може да се пренесе механично. При анализ винаги проверяваме как е реализирана всяка използвана операция.

Реалната цена на BFS/DFS. Линейното O(|V|+|E|) предполага достъп до списъка на съседите и проверка/маркиране на посетен връх за O(1). В свързаната учебна реализация point търси върха, а member търси в списъка на посетените. Те могат да струват O(|V|). За едно обхождане това дава горна оценка O(|V|²+|V||E|), вместо да гарантира линейно време. Тази оценка не е за изброяването на всички прости пътища, което може да изисква експоненциално много резултати.

Покриващото дърво. Записваме реброто, по което за първи път откриваме всеки некоренов връх. За свързан неориентиран граф така получаваме |V|−1 ребра, без цикъл, защото всяко свързва нов връх към вече достигнатите. Това е авторско извеждане от BFS/DFS, а не отделен цитиран раздел за покриващи дървета в книгата. Минималната сума на теглата е различно изискване.

Терминологична бележка. На ориг. 228 / нов PDF 217–218 условието „път в поне едната посока за всяка двойка“ е наречено слаба свързаност. То е по-силно от обичайната слаба свързаност, която се проверява след премахване на посоките. Например A→B←C е свързан след премахване на посоките, но между A и C няма ориентиран път. В изпитния текст уточнявай самото условие.

СУ 2: учебник, проверен код и таблица за всички 20 теми · Допълнение по точните страници на учебника

Литературна опора и граници на сверяването

Официална библиография на СУ — номерата по-долу са от нея.

  • СУ 2 — М. Тодорова, Структури от данни и програмиране на C++, 2011; СУ 5 — L. Ammeraal, Algorithms and data structures in C++, 1996.
  • Сверка с наличен пълен текст: СУ 2 вече е наличен като проверена дигитализация. Точните оригинални и нови PDF страници са посочени в раздела със сверка. СУ 5 (Ammeraal) остава библиографска опора без сверка с пълен текст в проекта.
  • СУ 9 — Abelson, Sussman, Structure and Interpretation of Computer Programs, 2. изд., 1996. Наличен е пълен текст: MIT PDF. PDF е преформатирана Texinfo версия от 2016 г.; използваме номера на раздели, не предполагаеми страници на печатното издание. §2.2.2 и §2.3.3: йерархични данни и двоични дървета за множества.
  • Допълнителни университетски източници, извън списъка на СУ: MIT 6.006, лекции 5–6 и 13–14 за BST, AVL, BFS и DFS; MIT 6.046J, лекции 3–4 за минимални покриващи дървета. Примерните графи и изчисленията са авторски.

Текстът и примерите са авторска учебна разработка, а не официален отговор или указание на изпитна комисия на СУ. Номерацията на разделите в плана е авторска. Препратките показват опората за понятията, а не че примерите са преписани от учебник.

Обратно към кратката разработка и уроците