Nejlepší odpověď
Existují různé typy stromových datových struktur. Některé z nich jsou
- Binární strom : Toto je nejzákladnější ze stromové struktury. Kde každý uzel může mít maximálně dvě děti. Binární strom perfect je binární strom, ve kterém mají všechny vnitřní uzly dvě podřízené a všechny listy mají stejnou hloubku nebo stejnou úroveň. plný binární strom (někdy označovaný jako vlastní [15] nebo rovinný binární strom) je strom, ve kterém má každý uzel ve stromu buď 0 nebo 2 děti. V úplném binární strom je každá úroveň, kromě poslední možná úplně vyplněna a všechny uzly v poslední úrovni jsou co nejvíce vlevo. V nekonečné úplnosti binární strom, každý uzel má dvě děti.
- Binární vyhledávací strom: BST je binární strom s určitými vlastnostmi jako například a levé dítě daného uzlu obsahuje hodnotu menší než rovná danému uzlu a pravé dítě obsahuje uzel větší než daný uzel.
- AVL strom nebo výškově vyvážený binární strom : Jedná se o variantu binárního stromu, kde výškový rozdíl mezi levým a pravým dílčím stromem může být maximálně 1. Pokud se kdykoli liší o více než jeden, provede se vyvážení na obnovit tuto vlastnost. Vyhledávání, vkládání a mazání trvá O (log n) v průměrných i nejhorších případech, kde n je počet uzlů ve stromu před operací.
- Červeno-černý strom : Další variantou binárního stromu podobnou stromu AVL je samoobslužný binární vyhledávací strom. V tomto stromu jsou uzly barevně červené nebo černé.
- Strom rozložení: Strom rozložení je samočinně se nastavující binární vyhledávací strom s další vlastnost, která nedávno přistupuje k prvkům, je rychle znovu přístupná. Všechny běžné operace na binárním vyhledávacím stromu jsou kombinovány s jednou základní operací, zvanou splaying. Umístěním stromu pro určitý prvek se strom přeskupí tak, aby byl prvek umístěn v kořenu stromu.
- N-ary strom: V tomto stromu je omezení binárního stromu odstraněno. Tady uzel může mít maximálně n dětí. Stejně jako binární strom může být úplným, úplným nebo dokonalým stromem. N-ary je nějaký čas známý jako les.
- Trie Structure : V počítačové vědě trium, nazývané také digitální strom a někdy radix strom nebo strom předpony (protože je lze prohledávat pomocí předpon), je uspořádaná stromová datová struktura, která se používá k ukládání dynamické sady nebo asociativního pole, kde jsou klíče obvykle řetězce. Všichni potomci uzlu mají společnou předponu řetězce přidruženého k tomuto uzlu a kořen je přidružen k prázdnému řetězci.
- Strom přípon : Strom Trie a přípona spolu úzce souvisí. strom přípon (také nazývaný strom PAT nebo v dřívější podobě strom pozic) je komprimovaný soubor obsahující všechny přípony daného textu jako jejich klíče a pozice v textu jako jejich hodnoty. Stromy přípon umožňují obzvláště rychlé implementace mnoha důležitých řetězcových operací.
- Strom Huffman: Strom Huffman je binární strom seřazený podle frekvence, který se při kompresi často používá. data. Huffmanův strom je konstruován tak, aby přidělil krátké kódové slovo dlouhému textu na základě jeho četnosti výskytu.
- Struktura haldy [Upravit podle návrhu ]: Struktura haldy je další široce používaná stromová struktura se specifickou vlastností řazení. Existují dva typy haldy – Min haldy a Max haldy. V min haldě musí být nadřazený uzel menší než hodnoty všech jeho podřízených. Podobně v maximální haldě má rodič vždy větší hodnotu ve srovnání se všemi svými podřízenými. Jednou běžnou implementací haldy je binární halda, kde každý rodič může mít maximálně dvě děti.
Další populární stromová struktura zahrnuje, ale nikoli vyčerpávající B -Tree, B + – strom, R-Tree, Counted-B Tree, KD strom (nebo K- rozměrný BST), rozhodovací strom (a varianta n-ary stromu), Markelův strom, Fenwickův strom (nebo binární indexový strom), Range Tree.
Odpověď
- Šablona jako kód vytvořením stromu závislostí.
Nyní mě 5 minut vysvětlete, jak jsme při řešení našeho komplexního případu použití použili strom jako datovou strukturu.
Abychom vysvětlili scénář, vezměme si malý příklad získávání dat z API pomocí autentizace založené na tokenech.
Pokud tedy chcete dosáhnout tohoto cíle,
- nejprve získáte uživatelské jméno, heslo a informace o nájemci a zavoláte API, abyste načetli token.
- Poté s načteným tokenem zavolejte aktivní API tak, že jej předáte v záhlaví žádosti.
Toto je nyní velmi jednoduchý scénář, ale věci se dost komplikují, když musíte provést řetězec 10 API „každý na sobě závislých.
Toto je místo, kde jsme přišli s tímto přístupem ke stromu závislostí
Nejprve musíme vytvořit taková šablona
Nyní vytvoříme takový závislostní strom
Cokoli definované jako $ {} znamenalo, že je to závislé na výstupu jiných proměnných.
ResourceOps znamená, že má být API spuštěno
Takto se vytváří strom závislostí
- Vyhodnocujeme parametry, které jsou nezávislé a připojte je ke kořenovému adresáři.
- Poté přijdeme k operacím se zdroji a pochopíme, že to závisí na hodnotách připojených k kořenovému uzlu. Odpojíme je tedy od nich od kořenového adresáře a poté je připojíme k novému uzlu.
- Totéž bude provedeno pro všechny operace se zdroji a výstup.
Jakmile vytvoříme strom závislostí, přejdeme spustit listový uzel, pak přijít k rodiči s výsledkem provedení listového uzlu a pak je to rodič a rodič, dokud se nedostaneme k hornímu uzlu.
Jakmile dosáhneme horního uzlu, dostaneme výsledek a vrátíme se zpět jako odpověď úspěchu http.
Pokud dojde k chybě při provádění, vrátíme zpět chybovou odpověď čitelným způsobem.
Nemyslím si, že jsem to vysvětlil trochu, ale chci jen zdůraznit, jak vyřešili jsme skutečný problém se stromovou datovou strukturou pro provádění dynamických akcí, aniž by vývojář musel psát nějaký kód.