Нелинейната структура от данни се състои от колекция от елементи, които са разпределени в равнината, което означава, че няма такава последователност между елементите, както съществува в линейна структура на данните.
Сравнителна таблица
| Основа за сравнение | Дърво | диаграма |
|---|---|---|
| път | Само между два върха. | Позволено е повече от един път. |
| Root възел | Той има точно един корен. | Графиката няма корен възел. |
| Loops | Не са разрешени примки. | Графиката може да има контури. |
| Сложност | По-малко сложно | По-сложни сравнително |
| Преходни техники | Предварителна поръчка, поръчка и поръчка. | Първоначално търсене и търсене в дълбочина. |
| Брой ръбове | n-1 (където n е броят на възлите) | Не е дефинирано |
| Тип модел | йерархически | мрежа |
Определение на дървото
Дървото е ограничена колекция от данни, които обикновено се наричат възли. Както е споменато по-горе, дървото е нелинейна структура от данни, която подрежда елементите от данни в подреден ред. Той се използва за показване на йерархична структура между различните елементи на данни и организира данните в клонове, които свързват информацията. Добавянето на нов ръб в дърво води до формиране на веригата или веригата.
Има няколко вида дървета, като двоично дърво, двоично дърво за търсене, дърво AVL, двоично дърво с резба, B-дърво и т.н. структура на данни.
Свойства на дървото:
- В горната част на дървото е обозначен възел, известен като корен на дървото.
- Останалите елементи от данни се разделят на несвързани подмножества, които се наричат поддерева.
- Дървото се разширява във височина към дъното.
- Дървото трябва да бъде свързано, което означава, че трябва да има път от един корен до всички други възли.
- Не съдържа никакви примки.
- Едно дърво има n-1 краища.
Има различни термини, свързани с дървета като терминален възел, ръб, ниво, степен, дълбочина, гора и т.н. Сред тези термини, някои от тях са описани по-долу.
- Edge - Линия, която свързва два възли.
- Ниво - Дървото е разделено на нива по такъв начин, че коренният възел е на ниво 0. Тогава неговите непосредствени деца са на ниво 1, а непосредствените му деца са на ниво 2 и т.н. до терминала или листа.
- Степен - Това е броят на поддертите на възел в дадено дърво.
- Дълбочина - Това е максималното ниво на всеки възел в дадено дърво и също така известен като височина .
- Терминален възел - Най-високото ниво на възела е терминален възел, докато други възли, с изключение на терминален и корен, са известни като не-терминални възли.
Определение на графика
Графиката също е математическа нелинейна структура от данни, която може да представлява различни видове физическа структура. Състои се от група от върхове (или възли) и набор от ръбове, които свързват двата върха. Вертикалите на графиката са представени като точка или кръгове, а ръбовете са показани като дъги или линейни сегменти. Ръбът е представен от E (v, w) където v и w са двойките върхове. Премахването на ръб от верига или свързан график създава подграф, който е дърво.
Графите са класифицирани в различни категории, като насочени, ненасочени, свързани, несвързани, прости и много графики. Компютърната мрежа, транспортната система, графика на социалните мрежи, електрическите вериги и планирането на проекти са някои от приложенията на структурата на графичните данни. Той се използва и в техниката на управление, наречена PERT (оценка на програмата и техника за преглед) и CPM (метод на критичен път), в която се анализира графичната структура.
Свойства на графиката:
- Един връх в графика може да бъде свързан с произволен брой други върхове, използвайки ръбове.
- Един ръб може да бъде двупосочен или насочен.
- Един ръб може да бъде претеглен.
В графиката също използваме различни термини като съседни върхове, път, цикъл, степен, свързан граф, пълна графика, претеглена графика и т.н. Да разберем някои от тези термини.
- Прилежащите върхове - връх а е съседен на връх b, ако има ръб (a, b) или (b, a).
- Path - Път от произволен връх w е съседна последователност от върхове.
- Цикъл - това е път, в който първият и последният върхове са еднакви.
- Степен - Това е редица ръбове, инцидентни на върха.
- Свързан граф - Ако съществува път от произволен връх до друг връх, тогава тази графика е известна като свързан граф.
Ключови разлики между дърво и графика
- В едно дърво съществува само един път между всеки два върха, докато графиката може да има еднопосочни и двупосочни пътеки между възлите.
- В дървото има точно един корен, а всяко дете може да има само един родител. В сравнение с, в графиката, няма концепция за коренния възел.
- Едно дърво не може да има примки и самообвивки, докато графиката може да има примки и самообвивки.
- Графиките са по-сложни, тъй като могат да имат контури и самообвивки. Обратно, дърветата са прости в сравнение с графиката.
- Дървото се пресича, като се използват предварителни, подредени и пост-техники. От друга страна, за пресичане на графика, ние използваме BFS (Първо търсене) и DFS (Първо търсене на дълбочина).
- Дървото може да има n-1 краища. Напротив, в графиката няма предварително определен брой ръбове и това зависи от графиката.
- Дървото има йерархична структура, докато графиката има мрежов модел.
заключение
Графиката и дървото са нелинейната структура на данните, която се използва за решаване на различни сложни проблеми. Графиката е група от върхове и ръбове, където ръб свързва чифт върхове, докато едно дърво се разглежда като минимално свързана графика, която трябва да бъде свързана и свободна от вериги.
