Een niet-lineaire gegevensstructuur bestaat uit een verzameling elementen die op een vlak worden gedistribueerd, wat betekent dat een dergelijke reeks niet bestaat tussen de elementen zoals deze bestaat in een lineaire gegevensstructuur.
Vergelijkingstabel
| Basis voor vergelijking | Boom | diagram |
|---|---|---|
| Pad | Slechts één tussen twee hoekpunten. | Meer dan één pad is toegestaan. |
| Root-knooppunt | Het heeft exact één basisknooppunt. | Graph heeft geen root-knooppunt. |
| Loops | Geen loops toegestaan. | Graph kan loops bevatten. |
| ingewikkeldheid | Minder complex | Complexer in vergelijking |
| Traversal technieken | Pre-order, in-order en post-order. | Breedste-eerst zoeken en diepte-eerste zoeken. |
| Aantal randen | n-1 (waarbij n het aantal knooppunten is) | Niet gedefinieerd |
| Model type | hiërarchische | Netwerk |
Definitie van Tree
Een boom is een eindige verzameling gegevensitems die meestal worden aangeduid als knooppunten. Zoals hierboven vermeld, is een boom een niet-lineaire gegevensstructuur die gegevensitems in gesorteerde volgorde rangschikt. Het wordt gebruikt om een hiërarchische structuur tussen de verschillende gegevenselementen weer te geven en de gegevens te ordenen in takken die de informatie relateren. De toevoeging van een nieuwe rand in een boom resulteert in een formatie van de lus of het circuit.
Er zijn verschillende soorten bomen, zoals een binaire boom, een binaire zoekboom, een AVL-boom, een binaire draadboom, een B-tree, enz. Datacompressie, bestandsopslag, manipulatie van de rekenkundige uitdrukking en gameboom zijn enkele van de toepassing van de boom data structuur.
Eigenschappen van de boom:
- Er is een aangegeven knooppunt aan de bovenkant van de boom dat bekend staat als een wortel van de boom.
- De resterende gegevensitems zijn onderverdeeld in disjuncte subsets die als substructuur worden aangeduid.
- De boom wordt in de hoogte naar de bodem uitgezet.
- Er moet een boom worden verbonden, wat betekent dat er een pad moet zijn van de ene hoofdmap naar alle andere knooppunten.
- Het bevat geen lussen.
- Een boom heeft n-1 randen.
Er zijn verschillende termen geassocieerd met bomen zoals eindknooppunt, rand, niveau, graad, diepte, bos, etc. Onder die termen, waarvan sommige hieronder worden beschreven.
- Rand - Een lijn die twee knooppunten met elkaar verbindt.
- Niveau - Een boom wordt op een zodanige manier in niveaus verdeeld dat het basisknooppunt zich op niveau 0 bevindt. De directe kinderen bevinden zich dan op niveau 1 en de directe kinderen bevinden zich op niveau 2 enzovoort tot aan het terminal- of bladerknooppunt.
- Graad - Het is het aantal substructuren van een knoop in een bepaalde boom.
- Diepte - Het is het maximale niveau van elk knooppunt in een bepaalde boom en staat ook bekend als hoogte .
- Eindknooppunt - Het knooppunt op het hoogste niveau is het eindpuntknooppunt, terwijl andere knooppunten behalve terminal en wortelknooppunt bekend staan als niet-eindknopen.
Definitie van grafiek
Een grafiek is ook een wiskundige niet-lineaire gegevensstructuur die verschillende soorten fysieke structuren kan vertegenwoordigen. Het bestaat uit een groep hoekpunten (of knooppunten) en een reeks randen die de twee hoekpunten verbinden. Hoekpunten in de grafiek worden weergegeven als punt of cirkels en randen worden weergegeven als bogen of lijnsegmenten. Een rand wordt voorgesteld door E (v, w) waarbij v en w de paren hoekpunten zijn. Verwijdering van een rand van een circuit of verbonden grafiek creëert een subafbeelding die een boom is.
De grafieken zijn onderverdeeld in verschillende categorieën, zoals gericht, niet-gericht, verbonden, niet-verbonden, eenvoudig en multi-grafiek. Computernetwerk, transportsysteem, sociale netwerkgrafiek, elektrische circuits en projectplanning zijn enkele van de toepassingen van de grafische datastructuur. Het wordt ook gebruikt in de managementtechniek genaamd PERT (programmaevaluatie en overzichtstechniek) en CPM (critical path-methode) waarin de grafiekstructuur wordt geanalyseerd.
Eigenschappen van een grafiek:
- Een hoekpunt in een grafiek kan met behulp van randen worden verbonden met een willekeurig aantal andere hoekpunten.
- Een rand kan worden gericht of gericht.
- Een rand kan worden gewogen.
In de grafiek gebruiken we ook verschillende termen, zoals aangrenzende hoekpunten, pad, cyclus, mate, verbonden grafiek, volledige grafiek, gewogen grafiek, etc. Laten we enkele van deze termen begrijpen.
- Aangrenzende hoekpunten - Een hoekpunt a grenst aan hoekpunt b als er een rand (a, b) of (b, a) is.
- Pad - Een pad van een willekeurige hoekpunt w is een aangrenzende reeks hoekpunten.
- Cyclus - Het is een pad waar de eerste en laatste hoekpunten hetzelfde zijn.
- Graad - Het is een aantal randen dat op een hoekpunt valt.
- Verbonden grafiek - Als er een pad bestaat van een willekeurige vertex naar een andere vertex, staat die grafiek bekend als een verbonden grafiek.
Belangrijkste verschillen tussen boom en grafiek
- In een boom bestaat er slechts één pad tussen twee willekeurige hoekpunten, terwijl een grafiek unidirectionele en bidirectionele paden tussen de knooppunten kan hebben.
- In de boom is er precies één basisknooppunt, en elk kind kan slechts één ouder hebben. Tegenover, in een grafiek, is er geen concept van het wortelknooppunt.
- Een boom kan geen lussen en zelflussen hebben terwijl de grafiek lussen en zelflussen kan hebben.
- Grafieken zijn ingewikkelder omdat het loops en self-loops kan hebben. Bomen daarentegen zijn eenvoudig in vergelijking met de grafiek.
- De boom wordt doorkruist met behulp van pre-order, in-order en post-order technieken. Aan de andere kant gebruiken we voor het doorlopen van de grafiek BFS (Breadth First Search) en DFS (Depth First Search).
- Een boom kan n-1 randen hebben. Integendeel, in de grafiek is er geen vooraf gedefinieerd aantal randen en hangt het af van de grafiek.
- Een boom heeft een hiërarchische structuur terwijl grafiek een netwerkmodel heeft.
Conclusie
Grafiek en boom zijn de niet-lineaire gegevensstructuur die wordt gebruikt om verschillende complexe problemen op te lossen. Een grafiek is een groep hoekpunten en randen waar een rand een paar hoekpunten verbindt, terwijl een boom wordt beschouwd als een minimaal verbonden grafiek die moet worden verbonden en vrij van lussen.
