Čítame lineárne dátové štruktúry ako pole, prepojený zoznam, zásobník a front, v ktorých sú všetky prvky usporiadané sekvenčne. Pre rôzne druhy údajov sa používajú rôzne dátové štruktúry.

Pri výbere štruktúry údajov sa berú do úvahy niektoré faktory:

Aký typ údajov je potrebné uložiť?: Je možné, že určitá štruktúra údajov môže byť pre určitý druh údajov najvhodnejšia.Náklady na operácie:Ak chceme minimalizovať náklady na operácie pri najčastejšie vykonávaných operáciách. Napríklad máme jednoduchý zoznam, na ktorom musíme vykonať operáciu vyhľadávania; potom môžeme vytvoriť pole, v ktorom sú prvky uložené v zoradenom poradí na vykonanie binárne vyhľadávanie . Binárne vyhľadávanie funguje veľmi rýchlo pre jednoduchý zoznam, pretože rozdeľuje vyhľadávací priestor na polovicu.Využitie pamäte:Niekedy chceme dátovú štruktúru, ktorá využíva menej pamäte.

Strom je tiež jednou z dátových štruktúr, ktoré predstavujú hierarchické dáta. Predpokladajme, že chceme zobraziť zamestnancov a ich pozície v hierarchickej forme, potom to môže byť znázornené takto:

Vyššie uvedený strom ukazuje organizačná hierarchia nejakej spoločnosti. Vo vyššie uvedenej štruktúre John je CEO spoločnosti a John má dvoch priamych podriadených s názvom ako Steve a Rohan . Steve má vymenovaných troch priamych podriadených Lee, Bob, Ella kde Steve je manažér. Bob má menovaných dvoch priamych podriadených Bude a Emma . Emma má pomenované dve priame podriadené Tom a Raj . Tom má menovanú jednu priamu správu Bill . Táto konkrétna logická štruktúra je známa ako a Strom . Jeho štruktúra je podobná skutočnému stromu, preto sa nazýva a Strom . V tejto štruktúre, koreň je na vrchu a jeho vetvy sa pohybujú smerom nadol. Preto môžeme povedať, že stromová dátová štruktúra je efektívnym spôsobom hierarchického ukladania dát.

Poďme pochopiť niektoré kľúčové body stromovej dátovej štruktúry.

• Stromová dátová štruktúra je definovaná ako kolekcia objektov alebo entít známych ako uzly, ktoré sú navzájom prepojené, aby reprezentovali alebo simulovali hierarchiu.
• Stromová dátová štruktúra je nelineárna dátová štruktúra, pretože sa neukladá sekvenčne. Je to hierarchická štruktúra, pretože prvky v strome sú usporiadané vo viacerých úrovniach.
• V stromovej dátovej štruktúre je najvyšší uzol známy ako koreňový uzol. Každý uzol obsahuje nejaké údaje a údaje môžu byť akéhokoľvek typu. Vo vyššie uvedenej stromovej štruktúre uzol obsahuje meno zamestnanca, takže typ údajov by bol reťazec.
• Každý uzol obsahuje nejaké údaje a prepojenie alebo referenciu iných uzlov, ktoré možno nazvať potomkami.

Niektoré základné pojmy používané v stromovej dátovej štruktúre.

Uvažujme o stromovej štruktúre, ktorá je uvedená nižšie:

stiahnite si video z youtube pomocou vlc

Vo vyššie uvedenej štruktúre je každý uzol označený nejakým číslom. Každá šípka zobrazená na obrázku vyššie je známa ako a odkaz medzi dvoma uzlami.

koreň:Koreňový uzol je najvyšší uzol v hierarchii stromu. Inými slovami, koreňový uzol je ten, ktorý nemá žiadneho rodiča. Vo vyššie uvedenej štruktúre je uzol s číslom 1 koreňový uzol stromu. Ak je uzol priamo prepojený s iným uzlom, nazývalo by sa to vzťah rodič-dieťa.Podradený uzol:Ak je uzol potomkom akéhokoľvek uzla, potom je uzol známy ako podradený uzol.rodič:Ak uzol obsahuje akýkoľvek poduzol, potom sa tento uzol považuje za rodiča tohto poduzla.Súrodenec:Uzly, ktoré majú rovnakého rodiča, sú známe ako súrodenci.Listový uzol: -Uzol stromu, ktorý nemá žiadny dcérsky uzol, sa nazýva listový uzol. Listový uzol je najspodnejší uzol stromu. Vo všeobecnom strome môže byť ľubovoľný počet listových uzlov. Listové uzly môžu byť tiež nazývané vonkajšie uzly.Vnútorné uzly:Uzol má aspoň jeden podriadený uzol známy ako an interné Uzol predka:-Predchodcom uzla je akýkoľvek predchádzajúci uzol na ceste od koreňa k tomuto uzlu. Koreňový uzol nemá žiadnych predkov. V strome zobrazenom na obrázku vyššie sú uzly 1, 2 a 5 predchodcami uzla 10.Potomok:Bezprostredný nasledovník daného uzla je známy ako potomok uzla. Na obrázku vyššie je 10 potomkom uzla 5.

Vlastnosti stromovej dátovej štruktúry

Rekurzívna dátová štruktúra:Strom je známy aj ako a rekurzívna dátová štruktúra . Strom možno definovať ako rekurzívne, pretože charakteristický uzol v stromovej dátovej štruktúre je známy ako a koreňový uzol . Koreňový uzol stromu obsahuje prepojenie na všetky korene jeho podstromov. Ľavý podstrom je na obrázku nižšie zobrazený žltou farbou a pravý podstrom je zobrazený červenou farbou. Ľavý podstrom možno ďalej rozdeliť na podstromy zobrazené v troch rôznych farbách. Rekurzia znamená zníženie niečoho podobným spôsobom. Takže táto rekurzívna vlastnosť stromovej dátovej štruktúry je implementovaná v rôznych aplikáciách.
Počet hrán:Ak existuje n uzlov, potom by bolo n-1 hrán. Každá šípka v štruktúre predstavuje odkaz alebo cestu. Každý uzol, okrem koreňového, bude mať aspoň jeden prichádzajúci odkaz známy ako okraj. Pre vzťah rodič-dieťa by existoval jeden odkaz.Hĺbka uzla x:Hĺbka uzla x môže byť definovaná ako dĺžka cesty od koreňa po uzol x. Jedna hrana prispieva jednou jednotkou dĺžky v ceste. Hĺbka uzla x teda môže byť definovaná aj ako počet hrán medzi koreňovým uzlom a uzlom x. Koreňový uzol má hĺbku 0.Výška uzla x:Výšku uzla x možno definovať ako najdlhšiu cestu z uzla x do listového uzla.

Na základe vlastností stromovej dátovej štruktúry sú stromy rozdelené do rôznych kategórií.

Implementácia stromu

Stromovú dátovú štruktúru je možné vytvoriť dynamickým vytváraním uzlov pomocou ukazovateľov. Strom v pamäti môže byť reprezentovaný takto:

Vyššie uvedený obrázok znázorňuje znázornenie stromovej dátovej štruktúry v pamäti. Vo vyššie uvedenej štruktúre obsahuje uzol tri polia. V druhom poli sú uložené údaje; prvé pole obsahuje adresu ľavého potomka a tretie pole adresu pravého potomka.

V programovaní môže byť štruktúra uzla definovaná ako:

 struct node { int data; struct node *left; struct node *right; } 

Vyššie uvedená štruktúra môže byť definovaná len pre binárne stromy, pretože binárny strom môže mať maximálne dve deti a generické stromy môžu mať viac ako dve deti. Štruktúra uzla pre generické stromy by bola odlišná v porovnaní s binárnym stromom.

Aplikácie stromov

Nasledujú aplikácie stromov:

Ukladanie prirodzene hierarchických údajov:Stromy sa používajú na ukladanie údajov v hierarchickej štruktúre. Napríklad súborový systém. Súborový systém uložený na diskovej jednotke, súbor a priečinok sú vo forme prirodzene hierarchických údajov a sú uložené vo forme stromov.Usporiadajte údaje:Používa sa na organizáciu údajov na efektívne vkladanie, mazanie a vyhľadávanie. Napríklad binárny strom má čas logN na vyhľadávanie prvku.Skúste:Ide o špeciálny druh stromu, ktorý sa používa na uloženie slovníka. Je to rýchly a efektívny spôsob dynamickej kontroly pravopisu.halda:Je to tiež stromová dátová štruktúra implementovaná pomocou polí. Používa sa na implementáciu prioritných frontov.B-strom a B+strom:B-Strom a B+Strom sú stromové dátové štruktúry používané na implementáciu indexovania v databázach.Smerovacia tabuľka:Stromová dátová štruktúra sa používa aj na ukladanie dát do smerovacích tabuliek v smerovačoch.

Typy stromovej dátovej štruktúry

Nasledujú typy stromovej dátovej štruktúry:

Všeobecný strom:Všeobecný strom je jedným z typov stromovej dátovej štruktúry. Vo všeobecnom strome môže mať uzol 0 alebo maximálne n počet uzlov. Neexistuje žiadne obmedzenie na stupeň uzla (počet uzlov, ktoré môže uzol obsahovať). Najvyšší uzol vo všeobecnom strome je známy ako koreňový uzol. Deti rodičovského uzla sú známe ako podstromy .

Tam môže byť n počet podstromov vo všeobecnom strome. Vo všeobecnom strome nie sú podstromy usporiadané, pretože uzly v podstrome nemožno usporiadať.
Každý neprázdny strom má dolnú hranu a tieto hrany sú spojené s uzlami známymi ako detské uzly . Koreňový uzol je označený úrovňou 0. Uzly, ktoré majú rovnakého rodiča, sú známe ako súrodencov . Binárny strom :Samotný binárny názov tu naznačuje dve čísla, t. j. 0 a 1. V binárnom strome môže mať každý uzol v strome maximálne dva podradené uzly. Maximálny tu znamená, či má uzol 0 uzlov, 1 uzol alebo 2 uzly.

Ak sa chcete dozvedieť viac o binárnom strome, kliknite na odkaz uvedený nižšie:
https://www.javatpoint.com/binary-tree Binárny vyhľadávací strom :Binárny vyhľadávací strom je nelineárna dátová štruktúra, ku ktorej je pripojený jeden uzol n počet uzlov. Ide o dátovú štruktúru založenú na uzloch. Uzol môže byť reprezentovaný v binárnom vyhľadávacom strome s tromi poľami, t. j. dátová časť, ľavé dieťa a pravé dieťa. Uzol môže byť pripojený k maximálne dvom podriadeným uzlom v binárnom vyhľadávacom strome, takže uzol obsahuje dva ukazovatele (ľavý podriadený a pravý podriadený ukazovateľ).
Každý uzol v ľavom podstrome musí obsahovať hodnotu menšiu ako je hodnota koreňového uzla a hodnota každého uzla v pravom podstrome musí byť väčšia ako hodnota koreňového uzla.

Uzol je možné vytvoriť pomocou užívateľom definovaného dátového typu známeho ako štruktúra, ako je ukázané nižšie:

 struct node { int data; struct node *left; struct node *right; } 

Vyššie je uvedená štruktúra uzla s tromi poľami: dátové pole, druhé pole je ľavý ukazovateľ typu uzla a tretie pole je pravý ukazovateľ typu uzla.

Ak sa chcete dozvedieť viac o binárnom vyhľadávacom strome, kliknite na odkaz uvedený nižšie:

https://www.javatpoint.com/binary-search-tree

koľko miest je v USA

AVL strom

Je to jeden z typov binárneho stromu, alebo môžeme povedať, že je to variant binárneho vyhľadávacieho stromu. AVL strom spĺňa vlastnosť binárny strom ako aj z binárny vyhľadávací strom . Je to samovyvažovací binárny vyhľadávací strom, ktorý vynašiel Adelson Velsky Lindas . Samovyvažovanie tu znamená vyváženie výšok ľavého podstromu a pravého podstromu. Toto vyváženie sa meria z hľadiska vyvažovací faktor .

Strom môžeme považovať za AVL strom, ak sa strom riadi binárnym vyhľadávacím stromom, ako aj vyrovnávacím faktorom. Vyvažovací faktor možno definovať ako rozdiel medzi výškou ľavého podstromu a výškou pravého podstromu . Hodnota vyvažovacieho faktora musí byť buď 0, -1 alebo 1; preto by mal mať každý uzol v strome AVL hodnotu vyrovnávacieho faktora buď ako 0, -1 alebo 1.

Ak sa chcete dozvedieť viac o strome AVL, kliknite na odkaz uvedený nižšie:

https://www.javatpoint.com/avl-tree

Červeno-čierny strom

Červeno-čierny strom je binárny vyhľadávací strom. Predpokladom červeno-čierneho stromu je, že by sme mali vedieť o binárnom vyhľadávacom strome. V binárnom vyhľadávacom strome by hodnota ľavého podstromu mala byť menšia ako hodnota tohto uzla a hodnota pravého podstromu by mala byť väčšia ako hodnota tohto uzla. Ako vieme, časová zložitosť binárneho vyhľadávania je v priemernom prípade log₂n, najlepší prípad je O(1) a najhorší prípad je O(n).

Keď sa na strome vykonáva akákoľvek operácia, chceme, aby bol náš strom vyvážený, aby všetky operácie ako vyhľadávanie, vkladanie, mazanie atď. trvali kratšie a všetky tieto operácie boli časovo zložité log₂n.

Červeno-čierny strom je samovyvažujúci binárny vyhľadávací strom. AVL strom je potom tiež binárny vyhľadávací strom vyrovnávajúci výšku prečo potrebujeme červeno-čierny strom . V strome AVL nevieme, koľko otáčok by bolo potrebných na vyváženie stromu, ale v červeno-čiernom strome sú na vyváženie stromu potrebné maximálne 2 rotácie. Obsahuje jeden extra bit, ktorý predstavuje červenú alebo čiernu farbu uzla, aby sa zabezpečilo vyváženie stromu.

Rozvetvený strom

Dátová štruktúra rozprestretého stromu je tiež binárny vyhľadávací strom, v ktorom je nedávno sprístupnený prvok umiestnený na koreňovú pozíciu stromu vykonaním niektorých rotačných operácií. Tu, rozstrekovanie znamená nedávno sprístupnený uzol. Je to a samovyvažovanie binárny vyhľadávací strom, ktorý nemá explicitnú podmienku rovnováhy, ako je AVL strom.

Je možné, že výška stromu zobrazenia nie je vyvážená, t. j. výška ľavého a pravého podstromu sa môže líšiť, ale operácie v strome zobrazenia majú poradie pokojne čas kde n je počet uzlov.

Rozvetvený strom je vyvážený strom, ale nemožno ho považovať za výškovo vyvážený strom, pretože po každej operácii sa vykoná rotácia, ktorá vedie k vyváženému stromu.

Treap

Štruktúra údajov Treap pochádza z údajovej štruktúry Tree a Heap. Zahŕňa teda vlastnosti stromových aj haldových dátových štruktúr. V binárnom vyhľadávacom strome musí byť každý uzol v ľavom podstrome rovnaký alebo menší ako hodnota koreňového uzla a každý uzol v pravom podstrome musí byť rovnaký alebo väčší ako hodnota koreňového uzla. V štruktúre údajov haldy obsahuje pravý aj ľavý podstrom väčšie kľúče ako koreň; preto môžeme povedať, že koreňový uzol obsahuje najnižšiu hodnotu.

V dátovej štruktúre treap má každý uzol oboje kľúč a prioritou kde kľúč je odvodený z binárneho vyhľadávacieho stromu a priorita je odvodená z dátovej štruktúry haldy.

The Treap dátová štruktúra sleduje dve vlastnosti, ktoré sú uvedené nižšie:

• Pravý potomok uzla>=aktuálny uzol a ľavý potomok uzla<=current node (binary tree)< li>
• Potomkovia akéhokoľvek podstromu musia byť väčšie ako uzol (hromada)

B-strom

B-strom je vyvážený m-cesta strom kde m určuje poradie stromu. Doteraz sme čítali, že uzol obsahuje iba jeden kľúč, ale b-strom môže mať viac ako jeden kľúč a viac ako 2 potomkov. Vždy udržiava zoradené údaje. V binárnom strome je možné, že listové uzly môžu byť na rôznych úrovniach, ale v b-strome musia byť všetky listové uzly na rovnakej úrovni.

Ak je objednávka m, uzol má nasledujúce vlastnosti:

• Každý uzol v b-strome môže mať maximum m deti
• Pre minimum detí má listový uzol 0 potomkov, koreňový uzol má minimálne 2 deti a vnútorný uzol má minimálny strop m/2 deti. Napríklad hodnota m je 5, čo znamená, že jeden uzol môže mať 5 potomkov a interné uzly môžu obsahovať maximálne 3 deti.
• Každý uzol má maximálny počet (m-1) kľúčov.

Koreňový uzol musí obsahovať minimálne 1 kľúč a všetky ostatné uzly musia obsahovať aspoň 1 kľúč strop m/2 mínus 1 kľúče.