Интерактивен учебник по информатика

Дърво и кореново дърво

Дървото е свързан граф без цикли. То е специален, но изключително важен вид граф — среща се навсякъде: файловата система, DOM на уеб страница, организационна структура, родословно дърво, дървета за търсене.

Често един от върховете се обявява за специален — наричаме го корен, а дървото — кореново дърво. Тогава можем да говорим за родител и деца: коренът е най-отгоре, а всеки друг връх има точно един родител (този по пътя към корена).

Фиг. 1 — Кореново дърво с корен 1. Връх 2 е родител на 4 и 5; върховете 4, 5, 6 нямат деца — те са листа.

Рекурсивна дефиниция (както е в учебника):

Един връх r е кореново дърво с корен r.
Ако T₁, …, Tₖ са коренови дървета с корени r₁, …, rₖ, добавяме нов връх r и ребра от него към всеки корен rᵢ. Получаваме ново кореново дърво с корен r.

Основни понятия

Корен — върхът, обявен за начало (няма родител).
Лист — връх без деца.
Родител / дете — съседните върхове нагоре / надолу.
Височина на връх — дължината на най-дългия път от него надолу до лист. Височината на дървото = височината на корена.
Разклоненост — максималният брой деца на връх.

Свойства на кореновите дървета

Теорема 1 — брой ребра

Кореново дърво с n върха има точно n − 1 ребра. Всеки връх освен корена има точно по едно ребро към своя родител — затова ребрата са с едно по-малко от върховете.

Теорема 2 — единствен път

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

Следствие

Ако към дърво добавиш кое да е несъществуващо ребро, веднага се появява точно един цикъл (новото ребро + единственият път между двата му края).

Представяне на коренови дървета

Понеже всеки връх има точно един родител, най-простото представяне е списък на родителите — масив p, в който p[i] е родителят на връх i. Коренът няма родител — записваме му 0.

За дървото от Фиг. 1:

i (връх)	1	2	3	4	5	6
p[i] (родител)	0	1	1	2	2	3

Ключово

Едно цяло дърво се събира в един масив! Това е възможно само защото всеки връх има точно един родител. (За обикновен граф трябва списък на съседство — там върховете имат много съседи.)

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

Двоично дърво е кореново дърво, в което всеки връх има най-много две деца — ляво и дясно. Тук редът на децата има значение (лявото е различно от дясното).

Фиг. 2 — Двоично дърво: всеки връх има ляво и/или дясно дете.

Представя се удобно с два масива: left[i] и right[i] — номерата на лявото и дясното дете на връх i (или 0, ако няма).

Двоичните дървета са основата на дърветата за търсене (BST), купищата (heap) и много други структури, които ще срещнеш по-нататък.

Покриващо дърво на граф

Покриващо дърво (spanning tree) на свързан граф е негов подграф, който е дърво и включва всички върхове. С други думи — оставяме само толкова ребра, колкото да държат графа свързан, без нито един цикъл.

Фиг. 3 — Покриващо дърво (зелено): свързва всички 5 върха с 4 ребра. Червените пунктирани ребра са премахнати, защото създават цикли.

Идея за построяване: докато в графа има цикъл, премахни едно ребро от него. Графът остава свързан (цикълът има друг път), но един цикъл изчезва. Когато не остане цикъл — имаме покриващо дърво.

Теорема

Граф е свързан тогава и само тогава, когато има покриващо дърво.

Съвет

Защо ни е? Представи си транспортна мрежа (пътища, кабели, тръби) — покриващото дърво е най-евтиният начин да свържеш всички точки без излишни връзки. Ефективното му намиране (с тегла → минимално покриващо дърво) е голяма тема в алгоритмиката.

Задача от учебника — листа на дървото

Лист е всеки връх, който не е родител на друг връх. Затова е достатъчно при прочитането на ребрата да отбелязваме кои върхове са родители, а накрая да изведем тези, които НЕ са:

static void Main()
{
    int n = int.Parse(Console.ReadLine());
    bool[] isParent = new bool[n + 1];

    // n-1 ребра: всеки ред е "родител", после "дете"
    for (int i = 1; i < n; i++)
    {
        int u = int.Parse(Console.ReadLine());   // родител
        isParent[u] = true;
        int v = int.Parse(Console.ReadLine());   // дете (пропускаме)
    }

    // листата са върховете, които не са родители
    for (int i = 1; i <= n; i++)
        if (!isParent[i]) Console.Write(i + " ");
    Console.WriteLine();
}

Какво трябва да запомниш

Дървото = свързан граф без цикли. Кореновото дърво има отделен корен.
Дърво с n върха има точно n − 1 ребра.
Между всеки два върха в дърво има единствен път.
Представяне: списък на родителите p[i] — цяло дърво в един масив.
Двоично дърво — всеки връх има ляво и дясно дете; редът има значение.
Покриващо дърво — свързва всички върхове без цикъл; граф е свързан ⟺ има покриващо дърво.