Legjobb válasz
Különböző típusú fa adatstruktúrák léteznek. Néhány közülük
- bináris fa : Ez a fa szerkezetének legalapvetőbb alapja. Ahol minden csomópontnak legfeljebb két gyermeke lehet. A tökéletes bináris fa egy bináris fa, amelyben az összes belső csomópontnak két gyermeke van és mind a levelek azonos mélységgel vagy azonos szinttel rendelkeznek. Egy teljes bináris fa (néha megfelelő [15] vagy sík bináris fának nevezik) egy fa, amelyben a fa minden csomópontjának 0 vagy 2 gyermeke van. Egy teljes bináris fa minden szint, lehetőleg az utolsó kivételével, teljesen kitöltve van, és az utolsó szint összes csomópontja a lehető legtávolabb helyezkedik el. A végtelen teljes bináris fa, minden csomópontnak két gyermeke van.
- Bináris kereső fa: a BST egy bináris fa, amelynek bizonyos tulajdonságai vannak mint például, és az adott csomópont bal gyermeke kevesebb, mint az adott csomópont értéke, a jobb oldali gyermek pedig az adott csomópontnál nagyobb csomópontot tartalmaz.
- AVL fa vagy magassággal kiegyensúlyozott bináris fa : Ez a bináris fa változata, ahol a bal és a jobb alfa közötti magasságkülönbség legfeljebb 1 lehet. Ha bármikor többel térnek el, akkor a állítsa vissza ezt a tulajdonságot. A keresés, beillesztés és törlés mind O (log n) időt vesz igénybe mind az átlagos, mind a legrosszabb esetben, ahol n a művelet előtti csomópontok száma a fában.
- Vörös-fekete fa : A bináris fa másik változata, hasonló az AVL fához, ez egy önkiegyensúlyozó bináris kereső fa. Ebben a fában a csomópontok pirosak vagy fekete színűek.
- Splay fa: A splash fa egy önbeállító bináris kereső fa, amelynek további tulajdonságok, amelyek nemrégiben hozzáfértek az elemekhez, gyorsan elérhetõk. A bináris keresőfán végzett összes normál műveletet egy alapművelettel kombinálják, amelyet splayingnek hívnak. A fa eljátszása egy bizonyos elemhez úgy rendezi át a fát, hogy az elem a fa gyökeréhez kerüljön.
- N-ary fa: Ebben a fában a bináris fa korlátozása megszűnik. Itt egy csomópontnak legfeljebb n gyermeke lehet. A bináris fához hasonlóan lehet teljes, teljes vagy tökéletes n-ary fa. Az N-ary valamikor erdő néven ismert.
- Trie felépítése : A számítástechnikában egy trie, más néven digitális fa és néha radix fa vagy előtagfa (mivel előtagok alapján kereshetők), egy rendezett fa adatstruktúra, amelyet dinamikus halmaz vagy asszociatív tömb tárolására használnak, ahol a kulcsok általában karakterláncok. Egy csomópont összes leszármazottjának közös előtagja van a csomóponthoz társított karakterláncnak, és a gyökér az üres karakterlánccal van társítva.
- Utótagfa : A Trie és az utótagfa szorosan összefüggenek egymással. az utótagfa (más néven PAT-fa, vagy korábbi formában a pozíciófa) egy tömörített trie, amely az adott szöveg összes utótagját tartalmazza kulcsaiként, és a szövegben lévő pozíciókat értékeikként. Az utótagfák sok fontos karakterlánc-művelet különösen gyors végrehajtását teszik lehetővé.
- Huffman-fa: A Huffman-fa egy frekvencia szerint rendezett bináris fa, amelyet széles körben használnak a tömörítésben. adat. A Huffman-fát úgy alakítják ki, hogy egy rövid kódszót rendeljen egy hosszú szöveghez annak előfordulási gyakorisága alapján.
- Halomszerkezet [Szerkesztés a javaslat szerint ]: A kupacszerkezet egy másik széles körben használt fa struktúra, sajátos rendezési tulajdonsággal. Kétféle halom létezik – Min halom és Max halom. Min. Kupacban a csomópont szülőjének kisebbnek kell lennie az összes gyermek értékénél. Hasonlóképpen max halomban a szülőnek mindig nagyobb az értéke minden gyermekéhez képest. A halom egyik gyakori megvalósítása a bináris halom, ahol minden szülő legfeljebb két gyermeket vállalhat.
Más népszerű fa struktúra a következőket tartalmazza, de nem kimerítően: B -Fa, B + – fa, R-fa, megszámlált-B fa, KD fa (vagy K- dimenziós BST), döntési fa (a n-ary fa változata), Markel fa, Fenwick fa (vagy bináris indexfa), Range Tree.
Válasz
- Sablon kódként, függőségi fa kialakításával.
Most álljon velem 5 percig, hogy részletesen elmagyarázhassam, hogyan használtuk a fát mint adatstruktúrát összetett használati esetünk megoldására.
A forgatókönyv elmagyarázásához vegyünk egy kis példát arra, hogy adatokat kapunk API-ból token alapú hitelesítéssel.
Tehát ha el akarja érni ezt a bravúrt,
- először megkapja a felhasználónevet, a jelszót és a bérlő adatait, és felhívja az API-t a token beolvasásához.
- Ezután a letöltött tokennel hívja meg az aktuális API-t úgy, hogy azt továbbítja a kérés fejlécében.
Ez most nagyon egyszerű forgatókönyv, de a dolgok meglehetősen összetetté válnak, amikor egy láncot kell végrehajtani 10 API “S mindegyike függ egymástól.
Itt találtuk ki ezt a függőségi fa megközelítést
Először létre kell hoznunk egy ehhez hasonló sablon
Most ezek után egy ilyen függőségi fát alkotunk.
Bármi, amit $ {} néven definiálunk, azt jelentette, hogy egy másik változó kimenettől függ.
A ResourceOps jelentése végrehajtandó API-kat
Így jön létre a függőségi fa
- Kiértékeljük azokat a paramétereket, amelyek függetlenek és csatolja őket a gyökérhez.
- Ezután rátérünk az erőforrás-műveletekre és megértjük, hogy ez a gyökércsomóponthoz csatolt értékektől függ. Tehát leválasztjuk őket róluk a gyökérből, majd új csomóponthoz csatoljuk őket.
- Ugyanez történik az összes erőforrásművelettel és kimenet.
Miután létrehoztuk a függőségi fát, megyünk a levélcsomópont végrehajtásához, akkor jöjjön a szülőhöz a levélcsomópont végrehajtási eredményével, majd a szülő és a szülője, amíg el nem érjük a legfelső csomópontot.
Amint elértük a legfelső csomópontot, megkapjuk az eredményt, és visszatérünk, mint http siker válasz.
Ha hiba van a végrehajtásban, akkor olvasható módon visszaküldjük a hibát.
Nem hiszem, hogy részleteket és részleteket elmagyaráztam volna, de csak azt szeretném kiemelni, hogy megoldottunk egy valós problémát a fa adatszerkezetével a dinamikus műveletek végrehajtásához anélkül, hogy egy fejlesztő valamilyen kódot írna.