V tomto kurzu se dozvíte o stromové datové struktuře. Dozvíte se také různé druhy stromů a terminologie používané ve stromu.
Strom je nelineární hierarchická datová struktura, která se skládá z uzlů spojených hranami.
Strom
Proč stromová datová struktura?
Další datové struktury, jako jsou pole, propojený seznam, zásobník a fronta, jsou lineární datové struktury, které ukládají data postupně. Aby bylo možné provést jakoukoli operaci v lineární datové struktuře, časová složitost se zvyšuje s nárůstem velikosti dat. V dnešním výpočetním světě to ale není přijatelné.
Různé stromové datové struktury umožňují rychlejší a snadnější přístup k datům, protože jde o nelineární datovou strukturu.
Terminologie stromů
Uzel
Uzel je entita, která obsahuje klíč nebo hodnotu a odkazy na jeho podřízené uzly.
Poslední uzly každé cesty se nazývají listové uzly nebo externí uzly , které neobsahují odkaz / ukazatel na podřízené uzly.
Uzel, který má alespoň podřízený uzel, se nazývá interní uzel .
Okraj
Jedná se o spojení mezi libovolnými dvěma uzly.
Uzly a hrany stromu
Vykořenit
Je to nejvyšší uzel stromu.
Výška uzlu
Výška uzlu je počet hran od uzlu k nejhlubšímu listu (tj. Nejdelší cesta od uzlu k uzlu listu).
Hloubka uzlu
Hloubka uzlu je počet hran od kořene k uzlu.
Výška stromu
Výška stromu je výška kořenového uzlu nebo hloubka nejhlubšího uzlu.
Výška a hloubka každého uzlu ve stromu
Stupeň uzlu
Stupeň uzlu je celkový počet větví daného uzlu.
Les
Kolekce nesouvislých stromů se nazývá les.
Vytváření lesa ze stromu
Les můžete vytvořit odříznutím kořene stromu.
Druhy stromů
- Binární strom
- Binární vyhledávací strom
- Strom AVL
- B-strom
Traverz stromu
Chcete-li provést jakoukoli operaci na stromu, musíte se dostat ke konkrétnímu uzlu. Algoritmus pro procházení stromem pomáhá při návštěvě požadovaného uzlu ve stromu.
Chcete-li se dozvědět více, navštivte stromový traverz.
Stromové aplikace
- Binární vyhledávací stromy (BST) se používají k rychlé kontrole, zda je prvek v sadě, nebo ne.
- Halda je druh stromu, který se používá pro třídění haldy.
- Upravená verze stromu s názvem Tries se používá v moderních směrovačích k ukládání informací o směrování.
- Nejpopulárnější databáze používají B-stromy a T-stromy, což jsou varianty stromové struktury, kterou jsme se naučili výše pro ukládání jejich dat
- Kompilátoři používají syntaxový strom k ověření syntaxe každého programu, který napíšete.
