В този урок ще научите за дървесната структура на данните. Също така ще научите за различните видове дървета и терминологиите, използвани в дървото.
Дървото е нелинейна йерархична структура от данни, която се състои от възли, свързани с ръбове.
Дърво
Защо дървесна структура на данните?
Други структури от данни като масиви, свързан списък, стек и опашка са линейни структури от данни, които съхраняват данни последователно. За да се извърши някаква операция в линейна структура от данни, сложността на времето се увеличава с увеличаването на размера на данните. Но това не е приемливо в днешния изчислителен свят.
Различните дървовидни структури от данни позволяват по-бърз и лесен достъп до данните, тъй като това е нелинейна структура от данни.
Дървови терминологии
Възел
Възелът е обект, който съдържа ключ или стойност и насочва към дъщерните си възли.
Последните възли на всеки път се наричат листови възли или външни възли , които не съдържат връзка / указател към дъщерни възли.
Възелът, който има поне дъщерен възел, се нарича вътрешен възел .
Ръб, край
Това е връзката между всеки два възела.
Възли и ръбове на дърво
Корен
Това е най-горният възел на дърво.
Височина на възел
Височината на възел е броят на ръбовете от възела до най-дълбокия лист (т.е. най-дългият път от възела до листния възел).
Дълбочина на възел
Дълбочината на възел е броят на ръбовете от корена до възела.
Височина на дърво
Височината на дърво е височината на кореновия възел или дълбочината на най-дълбокия възел.
Височина и дълбочина на всеки възел в дърво
Степен на възел
Степента на възел е общият брой клонове на този възел.
Гора
Колекция от несвързани дървета се нарича гора.
Създаване на гора от дърво
Можете да създадете гора, като отрежете корена на дърво.
Видове дървета
- Двоично дърво
- Двоично дърво за търсене
- AVL дърво
- B-Tree
Обхождане на дърво
За да извършите някаква операция върху дърво, трябва да достигнете до конкретния възел. Алгоритъмът за обръщане на дърво помага при посещение на необходимия възел в дървото.
За да научите повече, моля, посетете обход на дърво.
Приложения на дърво
- Дърветата за двоично търсене (BST) се използват за бърза проверка дали даден елемент присъства в набор или не.
- Heap е вид дърво, което се използва за сортиране на купчини.
- Модифицирана версия на дърво, наречено Tries, се използва в съвременните рутери за съхраняване на информация за маршрута.
- Повечето популярни бази данни използват B-Trees и T-Trees, които са варианти на дървесната структура, която научихме по-горе, за да съхраняват техните данни
- Компилаторите използват синтаксисно дърво, за да проверят синтаксиса на всяка програма, която пишете.
