Съдържание

• Сравнителна диаграма
• Определение на Дърво
• Свойства на дървото:
• Определение на графика
• Свойства на графика:
• заключение

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

Нелинейната структура на данни се състои от колекция от елементи, които са разпределени в равнина, което означава, че няма такава последователност между елементите, както съществува в линейна структура на данни.

1. 1. Сравнителна диаграма
   2. дефиниция
   3. Ключови разлики
   4. заключение

Сравнителна диаграма

Основа за сравнение	Дърво	диаграма
път	Само един между два върха.	Разрешен е повече от един път.
Корен възел	Той има точно един корен възел.	Графиката няма корен възел.
Loops	Не са разрешени бримки.	Графиката може да има бримки.
Сложност	По-малко сложен	По-сложно сравнително
Техники на преминаване	Предварителна поръчка, по поръчка и след поръчка.	Първо търсене и дълбочина.
Брой ръбове	n-1 (където n е броят на възлите)	Не е определено
Тип модел	йерархически	мрежа

Определение на Дърво

А дърво е ограничена колекция от елементи от данни, обикновено наричани възли. Както беше споменато по-горе, че дърво е нелинейна структура на данни, която подрежда елементите с данни в подреден ред. Използва се за показване на йерархична структура между различните елементи на данни и организира данните в клонове, които свързват информацията. Добавянето на нов ръб в дърво води до образуване на контура или верига.

Има няколко типа дървета като двоично дърво, двоично дърво за търсене, AVL дърво, бинарно дърво с резба, B-дърво и др. Компресиране на данни, съхранение на файлове, манипулиране на аритметичния израз и дърветата на играта са част от приложението на дървото структура на данни.

Свойства на дървото:

• Има обозначен възел в горната част на дървото, известен като корен на дървото.
• Останалите елементи от данни са разделени на разединени подмножества, които се отнасят до поддърво.
• Дървото е разширено във височина към дъното.
• Дървото трябва да бъде свързано, което означава, че трябва да има път от един корен до всички други възли.
• Не съдържа бримки.
• Дървото има n-1 ръбове.

Има различни термини, свързани с дървета като терминален възел, ръб, ниво, степен, дълбочина, гора и др. Сред тези термини някои от тях са описани по-долу.

• Ръб, край - Линия, която свързва два възела.
• ниво - Дърво е разделено на нива, така че кореновият възел да е на ниво 0. Тогава неговите непосредствени деца са на ниво 1, а непосредствените му деца са на ниво 2 и така нататък до терминалния или листния възел.
• степен - Това е броят на подредовете на възел в дадено дърво.
• дълбочина - Това е максималното ниво на всеки възел в дадено дърво и известно също като височина.
• Терминален възел - Възелът от най-високо ниво е терминалният възел, докато други възли, с изключение на терминал и корен, са известни като нетерминални възли.

Определение на графика

А диаграма е също математическа нелинейна структура на данни, която може да представлява различни видове физическа структура. Състои се от група върхове (или възли) и набор от ръбове, които свързват двата върха. Върховете на графиката са представени като точка или кръгове, а краищата са показани като дъги или линейни сегменти. Един ръб е представен от E (v, w), където v и w са двойките върхове. Отстраняването на ръба от схема или свързана графика създава подграф, който е дърво.

Графиките са класифицирани в различни категории като насочени, непосочени, свързани, несвързани, прости и много графични. Компютърната мрежа, транспортната система, графиката на социалната мрежа, електрическите вериги и планирането на проекти са някои от приложенията на структурата на графичните данни. Той също се използва в техника на управление, наречена като PERT (техника за оценка и преглед на програмата) и CPM (метод на критичния път), при който се анализира структурата на графиката.

Свойства на графика:

• Връх в графика може да бъде свързан с произволен брой други върхове с помощта на ръбове.
• Един ръб може да бъде двупосочен или насочен.
• Един ръб може да бъде претеглян.

В графиката също използваме различни термини като съседни върхове, път, цикъл, степен, свързана графика, пълна графика, претеглена графика и т.н. Нека разберем някои от тези термини.

• Съседни върхове - Връх a е в съседство с върха b, ако има ръб (a, b) или (b, a).
• път - Път от произволен връх w е съседна последователност от върхове.
• цикъл - Това е път, по който първият и последният върхове са еднакви.
• степен - Това е редица ръбове, случващи се на върха.
• Свързана графика - Ако съществува път от произволен връх до който и да е друг връх, тогава тази графа е известна като свързана графика.

1. В дърво има само един път между всеки два върха, докато графика може да има еднопосочни и двупосочни пътища между възлите.
2. В дървото има точно един корен възел и всяко дете може да има само един родител. Обратно, в графика няма концепция за коренния възел.
3. Дървото не може да има бримки и самообувки, докато графиката може да има бримки и самообувания.
4. Графиките са по-сложни, тъй като могат да имат бримки и самообувки. За разлика от тях дърветата са прости в сравнение с графиката.
5. Дървото се пресича с помощта на техники за предварителна заявка, по поръчка и след поръчка. От друга страна, за преминаване на графики използваме BFS (Breadth First Search) и DFS (Depth First Search).
6. Едно дърво може да има n-1 ръбове. Напротив, в графиката няма предварително определен брой ръбове и това зависи от графиката.
7. Дървото има йерархична структура, докато графиката има мрежов модел.

заключение

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