Nieliniowa struktura danych składa się z zbioru elementów, które są rozmieszczone na płaszczyźnie, co oznacza, że nie ma takiej sekwencji między elementami, jakie istnieją w liniowej strukturze danych.
Wykres porównania
| Podstawa do porównania | Drzewo | Wykres |
|---|---|---|
| Ścieżka | Tylko jeden między dwoma wierzchołkami. | Dozwolona jest więcej niż jedna ścieżka. |
| Węzeł główny | Ma dokładnie jeden węzeł główny. | Wykres nie ma węzła głównego. |
| Pętle | Żadne pętle nie są dozwolone. | Wykres może mieć pętle. |
| Złożoność | Mniej skomplikowane | Bardziej złożony porównawczo |
| Techniki traversal | Zamów w przedsprzedaży, na zamówienie i po zamówieniu. | Pierwsze wyszukiwanie i pierwsze wyszukiwanie w głąb. |
| Liczba krawędzi | n-1 (gdzie n to liczba węzłów) | Nie zdefiniowano |
| Typ modelu | Hierarchiczny | Sieć |
Definicja drzewa
Drzewo to skończona kolekcja elementów danych zwanych zwykle węzłami. Jak wspomniano powyżej, drzewo jest nieliniową strukturą danych, która porządkuje elementy danych w porządku posortowanym. Służy do pokazania hierarchicznej struktury pomiędzy różnymi elementami danych i porządkowania danych w gałęziach, które odnoszą się do informacji. Dodanie nowej krawędzi w drzewie powoduje utworzenie pętli lub obwodu.
Istnieje kilka rodzajów drzew, takich jak drzewo binarne, drzewo wyszukiwania binarnego, drzewo AVL, drzewo binarne z wątkami, drzewo B, itd. Kompresja danych, przechowywanie plików, manipulacja wyrażeń arytmetycznych i drzew gry to tylko niektóre z zastosowań drzewa struktura danych.
Właściwości drzewa:
- Na wierzchołku drzewa jest wyznaczony węzeł zwany korzeniem drzewa.
- Pozostałe elementy danych są podzielone na rozłączne podzbiory, określane jako poddrzewo.
- Drzewo jest powiększane w górę w kierunku dna.
- Drzewo musi być połączone, co oznacza, że musi istnieć ścieżka od jednego korzenia do wszystkich innych węzłów.
- Nie zawiera żadnych pętli.
- Drzewo ma krawędzie n-1.
Istnieją różne terminy związane z drzewami, takie jak węzeł końcowy, krawędź, poziom, stopień, głębokość, las itp. Spośród tych terminów niektóre z nich opisano poniżej.
- Edge - linia łącząca dwa węzły.
- Poziom - drzewo jest podzielone na poziomy w taki sposób, że węzeł główny znajduje się na poziomie 0. Następnie jego najbliższe dzieci znajdują się na poziomie 1, a jego najbliższe dzieci znajdują się na poziomie 2 itd. Aż do terminala lub węzła liści.
- Stopień - Jest to liczba poddrzew węzła w danym drzewie.
- Głębokość - Jest to maksymalny poziom dowolnego węzła w danym drzewie i znany również jako wysokość .
- Węzeł terminalu - węzeł najwyższego poziomu to węzeł końcowy, podczas gdy inne węzły oprócz terminala i węzła głównego są nazywane węzłami nieulotnymi.
Definicja wykresu
Wykres jest również matematyczną nieliniową strukturą danych, która może reprezentować różne rodzaje fizycznej struktury. Składa się z grupy wierzchołków (lub węzłów) i zestawu krawędzi, które łączą dwa wierzchołki. Wierzchołki na wykresie są reprezentowane jako punkt lub koła, a krawędzie są wyświetlane jako łuki lub odcinki linii. Krawędź jest reprezentowana przez E (v, w), gdzie v i w są parami wierzchołków. Usunięcie krawędzi z obwodu lub połączonego wykresu tworzy podgraph, który jest drzewem.
Wykresy są podzielone na różne kategorie, takie jak reżyserowane, niekierowane, połączone, niepowiązane, proste i wielobajtowe. Sieć komputerowa, system transportowy, wykres sieci społecznościowej, obwody elektryczne i planowanie projektu to tylko niektóre z zastosowań struktury danych wykresowych. Jest również stosowany w technice zarządzania nazwanej jako PERT (programowa ocena i technika oceny) i CPM (metoda ścieżki krytycznej), w której analizowana jest struktura wykresu.
Właściwości wykresu:
- Werteks na wykresie można połączyć z dowolną liczbą innych wierzchołków za pomocą krawędzi.
- Krawędź może być dwukierunkowa lub skierowana.
- Krawędź może być ważona.
Na wykresie używamy także różnych terminów, takich jak sąsiednie wierzchołki, ścieżka, cykl, stopień, połączony wykres, kompletny wykres, wykres ważony itp. Rozumiem niektóre z tych terminów.
- Sąsiednie wierzchołki - wierzchołek A przylega do wierzchołka b, jeśli występuje krawędź (a, b) lub (b, a).
- Ścieżka - ścieżka od losowego wierzchołka w jest sąsiednią sekwencją wierzchołków.
- Cykl - Jest to ścieżka, w której pierwsze i ostatnie wierzchołki są takie same.
- Stopień - Jest to liczba krawędzi padających na wierzchołek.
- Połączony wykres - jeśli istnieje ścieżka od przypadkowego wierzchołka do dowolnego innego wierzchołka, wówczas ten wykres jest nazywany połączonym wykresem.
Kluczowe różnice między drzewem a wykresem
- W drzewie istnieje tylko jedna ścieżka między dwoma wierzchołkami, podczas gdy wykres może mieć jednokierunkowe i dwukierunkowe ścieżki między węzłami.
- W drzewie znajduje się dokładnie jeden węzeł główny, a każde dziecko może mieć tylko jednego rodzica. W przeciwieństwie do tego, na wykresie nie ma koncepcji węzła głównego.
- Drzewo nie może mieć pętli i pętli własnych, podczas gdy wykres może zawierać pętle i pętle własne.
- Wykresy są bardziej skomplikowane, ponieważ mogą zawierać pętle i pętle własne. Natomiast drzewa są proste w porównaniu do wykresu.
- Drzewo jest wykonywane za pomocą technik przedsprzedaży, po kolei i po zamówieniu. Z drugiej strony, dla przechodzenia między wykresami używamy BFS (Szerokość pierwszego wyszukiwania) i DFS (Głębokość pierwszego wyszukiwania).
- Drzewo może mieć krawędzie n-1. Wręcz przeciwnie, na wykresie nie ma ustalonej liczby krawędzi i zależy to od wykresu.
- Drzewo ma hierarchiczną strukturę, podczas gdy wykres ma model sieci.
Wniosek
Wykres i drzewo to nieliniowa struktura danych, która służy do rozwiązywania różnych złożonych problemów. Wykres to grupa wierzchołków i krawędzi, gdzie krawędź łączy parę wierzchołków, podczas gdy drzewo jest uważane za minimalnie połączony wykres, który musi być podłączony i wolny od pętli.
