Beste antwoord
Er zijn verschillende soorten boomgegevensstructuren. Sommigen van hen zijn
- Binaire boom : dit is de meest elementaire basis van een boomstructuur. Waarbij elk knooppunt maximaal twee kinderen kan hebben. Een perfecte binaire boom is een binaire boom waarin alle interne knooppunten twee kinderen hebben en alle bladeren hebben hetzelfde diepte of hetzelfde niveau. Een volledige binaire boom (soms aangeduid als een juiste [15] of vlakke binaire boom) is een boom waarin elk knooppunt in de boom ofwel 0 of 2 kinderen heeft. In een compleet binaire boom elk niveau, behalve mogelijk het laatste, is volledig gevuld, en alle knooppunten in het laatste niveau zijn zo ver mogelijk links. In de oneindig compleet binaire boom, elk knooppunt heeft twee kinderen.
- Binaire zoekboom: BST is een binaire boom met bepaalde eigenschappen zoals, en het linkerkind van het gegeven knooppunt bevat een waarde die kleiner is dan gelijk aan het gegeven knooppunt en het rechterkind bevat een knooppunt groter dan het gegeven knooppunt.
- AVL-boom of in hoogte gebalanceerde binaire boom : het is een variatie op de binaire boom waarbij het hoogteverschil tussen de linker en rechter subboom maximaal 1 kan zijn. Als ze op enig moment met meer dan één verschillen, wordt opnieuw in evenwicht gebracht herstel deze eigenschap. Opzoeken, invoegen en verwijderen nemen allemaal O (log n) tijd in zowel de gemiddelde als de slechtste gevallen, waarbij n het aantal knooppunten in de boom is voorafgaand aan de bewerking.
- Rood-zwarte boom : een andere variant van de binaire boom die lijkt op de AVL-boom, het is een zelfbalancerende binaire zoekboom. In deze boomstructuur zijn knooppunten ofwel rood of zwart gekleurd.
- Splay-boom: Een splay-boom is een zichzelf aanpassende binaire zoekboom met de extra eigenschap waartoe recentelijk gebruikte elementen snel weer toegankelijk zijn. Alle normale bewerkingen op een binaire zoekboom worden gecombineerd met één basisbewerking, genaamd splaying. Door de boom voor een bepaald element te spreiden, wordt de boom opnieuw gerangschikt zodat het element in de wortel van de boom wordt geplaatst.
- N-ary tree: In deze boom is de beperking van de binaire boom verwijderd. Hier kan een knooppunt maximaal n kinderen hebben. Net als een binaire boom kan het een volledige, complete of perfecte n-ary boom zijn. N-ary wordt ook wel bos genoemd.
- Trie-structuur : in de informatica wordt een trie, ook wel digitale boom en soms radix genoemd boom of voorvoegsel boom (zoals ze kunnen worden doorzocht op voorvoegsels), is een geordende boom datastructuur die wordt gebruikt om een dynamische set of associatieve array op te slaan waar de sleutels meestal strings zijn. Alle afstammelingen van een knoop hebben een gemeenschappelijk voorvoegsel van de tekenreeks die aan dat knooppunt is gekoppeld, en de wortel is gekoppeld aan de lege tekenreeks.
- Achtervoegselboom : Trie en achtervoegselboom zijn nauw verwant. een achtervoegselboom (ook wel PAT-boom genoemd of, in een eerdere vorm, positieboom) is een gecomprimeerde trie met alle achtervoegsels van de gegeven tekst als hun sleutels en posities in de tekst als hun waarden. Achtervoegselbomen maken bijzonder snelle implementaties van veel belangrijke tekenreeksbewerkingen mogelijk.
- Huffman-boom: Huffman-boom is een frequentie gesorteerde binaire boom die veel wordt gebruikt bij het comprimeren gegevens. De Huffman-structuur is geconstrueerd om een kort codewoord toe te wijzen aan een lange tekst op basis van de frequentie waarmee deze voorkomt.
- Heap-structuur [Bewerken zoals voorgesteld ]: Heap-structuur is een andere veelgebruikte boomstructuur met een specifieke ordeningseigenschap. Er zijn twee soorten heap – Min heap en Max heap. In een min heap moet de ouder van een knooppunt kleiner zijn dan de waarden van al zijn kinderen. Op dezelfde manier hebben de ouders in max heap altijd een grotere waarde in vergelijking met al zijn kinderen. Een veelvoorkomende implementatie van heap is binaire heap, waarbij elke ouder maximaal twee kinderen kan hebben.
Andere populaire boomstructuur omvat, maar niet uitputtend B -Tree, B + – tree, R-Tree, Counted-B Tree, KD-boom (of K- dimensionale BST), Beslissingsboom (a variant van n-ary tree), Markel tree, Fenwick tree (of binaire index tree), Range Tree.
Antwoord
- Template als code door een afhankelijkheidsboom te vormen.
Heb nu 5 minuten geduld om in detail uit te leggen hoe we de boom als datastructuur hebben gebruikt om onze complexe use-case op te lossen.
Laten we, om het scenario uit te leggen, een klein voorbeeld nemen van het verkrijgen van gegevens van een API via token-gebaseerde authenticatie.
Dus als je deze prestatie wilt bereiken,
- je krijgt eerst de gebruikersnaam, het wachtwoord en de tenant-informatie en roept de API aan om het token op te halen.
- Roep vervolgens met het opgehaalde token de actieve API aan door die in de headers van het verzoek door te geven.
Dit is een heel eenvoudig scenario, maar het wordt behoorlijk ingewikkeld als je een ketting moet uitvoeren van 10 APIs die elk van elkaar afhankelijk zijn.
Hier kwamen we met deze afhankelijkheidsboombenadering
Eerst moeten we een sjabloon zoals deze
Hierna vormen we een afhankelijkheidsboom zoals deze
Alles gedefinieerd als $ {} betekende dat het is afhankelijk van de uitvoer van andere variabelen.
ResourceOps betekent APIs die moeten worden uitgevoerd
Dit is hoe de afhankelijkheidsstructuur wordt gemaakt
- We evalueren parameters die onafhankelijk zijn en koppel ze aan de root.
- We komen dan bij resource-operaties en begrijpen dat dit afhangt van de waarden die aan de root-node zijn gekoppeld. Dus we maken ze los van de root en koppelen ze vervolgens aan een nieuw knooppunt.
- Hetzelfde zal worden gedaan voor alle bronbewerkingen en output.
Zodra we de afhankelijkheidsboom hebben gemaakt, gaan we naar de leaf-node, voer het uit en kom dan naar de bovenliggende node met het uitvoeringsresultaat van de leaf-node en dan is het “parent” en is “parent” totdat we de bovenste node bereiken.
Zodra we het bovenste knooppunt hebben bereikt, krijgen we het resultaat en keren we terug als een http-succesreactie.
Als er een fout in de uitvoering is, retourneren we de foutreactie op een leesbare manier.
Ik denk niet dat ik het stukje bij beetje had uitgelegd, maar ik wil alleen benadrukken hoe we hebben een echt probleem opgelost met de boomgegevensstructuur voor dynamische acties die moeten worden uitgevoerd zonder dat een ontwikkelaar wat code schrijft.