V tomto výučbe sa dozviete o stromovej dátovej štruktúre. Dozviete sa tiež rôzne druhy stromov a terminológiu použitú v tomto strome.
Strom je nelineárna hierarchická dátová štruktúra, ktorá sa skladá z uzlov spojených hranami.
Strom
Prečo stromová dátová štruktúra?
Ostatné dátové štruktúry, ako sú polia, prepojený zoznam, zásobník a fronta, sú lineárne dátové štruktúry, ktoré ukladajú údaje postupne. Aby bolo možné vykonať akúkoľvek operáciu v lineárnej dátovej štruktúre, časová zložitosť rastie so zväčšovaním veľkosti dát. V dnešnom výpočtovom svete to však nie je prijateľné.
Rôzne stromové dátové štruktúry umožňujú rýchlejší a ľahší prístup k údajom, pretože ide o nelineárnu dátovú štruktúru.
Terminológie stromov
Uzol
Uzol je entita, ktorá obsahuje kľúč alebo hodnotu a smerníky na jej podradené uzly.
Posledné uzly každej cesty sa nazývajú listové uzly alebo externé uzly , ktoré neobsahujú odkaz / smerník na podradené uzly.
Uzol, ktorý má aspoň podradený uzol, sa nazýva interný uzol .
Hrana
Je to spojenie medzi ľubovoľnými dvoma uzlami.
Uzly a hrany stromu
Koreň
Je to najvyšší uzol stromu.
Výška uzla
Výška uzla je počet hrán od uzla po najhlbší list (tj. Najdlhšia cesta od uzla k listovému uzlu).
Hĺbka uzla
Hĺbka uzla je počet hrán od koreňa po uzol.
Výška stromu
Výška Stromu je výška koreňového uzla alebo hĺbka najhlbšieho uzla.
Výška a hĺbka každého uzla v strome
Stupeň uzla
Stupeň uzla je celkový počet vetiev tohto uzla.
les
Zbierka nesúrodých stromov sa nazýva les.
Vytváranie lesa zo stromu
Les môžete vytvoriť rezaním koreňa stromu.
Druhy stromov
- Binárny strom
- Binárny vyhľadávací strom
- Strom AVL
- B-strom
Traverz stromu
Ak chcete vykonať akúkoľvek operáciu na strome, musíte sa dostať do konkrétneho uzla. Algoritmus prechodu stromom pomáha pri návšteve požadovaného uzla v strome.
Ak sa chcete dozvedieť viac, navštívte stromový priechod.
Aplikácie stromu
- Binárne vyhľadávacie stromy (Binary Search Trees) sa používajú na rýchlu kontrolu, či je prvok v množine alebo nie.
- Halda je druh stromu, ktorý sa používa na triedenie haldy.
- V moderných smerovačoch sa na ukladanie informácií o smerovaní používa upravená verzia stromu s názvom Tries.
- Najobľúbenejšie databázy používajú stromy B a stromy, ktoré sú variantmi stromovej štruktúry, ktorú sme sa vyššie naučili na ukladanie ich údajov.
- Kompilátory používajú strom syntaxe na overenie syntaxe každého programu, ktorý napíšete.
