Bedste svar
Der findes forskellige typer trædatastrukturer. Nogle af dem er
- Binært træ : Dette er den mest basale basis fra træstruktur. Hvor hver knude kan have størst to børn. Et perfekt binært træ er et binært træ, hvor alle indvendige noder har to børn og alle blade har samme dybde eller samme niveau. A fuldt binært træ (undertiden benævnt et ordentligt [15] eller plan binært træ) er et træ, hvor hver knude i træet enten har 0 eller 2 børn. I en komplet binært træ hvert niveau, undtagen muligvis det sidste, er fuldstændigt udfyldt, og alle noder i det sidste niveau er så langt tilbage som muligt. I uendelig komplet binært træ, hver knude har to børn.
- Binært søgetræ: BST er et binært træ med visse egenskaber såsom og venstre barn til den givne knude indeholder værdi mindre end lig med den givne knude og højre hånd barn indeholder knude større end den givne knude.
- AVL-træ eller højdeabalanceret binært træ : Det er en variation af det binære træ, hvor højdeforskellen mellem venstre og højre undertræ højst kan være 1. Hvis de på et hvilket som helst tidspunkt adskiller sig med mere end et, foretages rebalancering for at gendanne denne ejendom. Opslag, indsættelse og sletning tager alt sammen O (log n) tid i både gennemsnitlige og værste tilfælde, hvor n er antallet af noder i træet før operationen.
- Rød-sort træ : En anden variant af binært træ svarende til AVL-træ, det er et selvbalancerende binært søgetræ. I dette træ er noder enten farvet rød eller sort.
- Splay-træ: Et splay-træ er et selvjusterende binært søgetræ med ekstra egenskab, der for nylig har fået adgang til elementer, er hurtig at få adgang til igen. Alle normale operationer på et binært søgetræ kombineres med en grundlæggende operation, kaldet splaying. Afspilning af træet for et bestemt element omarrangerer træet, så elementet placeres ved roden af træet.
- N-ary træ: I dette træ fjernes begrænsningen af det binære træ. Her kan en node højst have n børn. Ligesom binært træ kan det være fuldt, komplet eller perfekt n-ary træ. N-ary er noget tid kendt som skov.
- Trie Structure : I datalogi er en trie, også kaldet digitalt træ og undertiden radix træ eller præfiksetræ (da de kan søges med præfikser), er en ordnet trædatastruktur, der bruges til at gemme et dynamisk sæt eller associerende matrix, hvor nøglerne normalt er strenge. Alle efterkommere af en node har et fælles præfiks for den streng, der er knyttet til den node, og roden er knyttet til den tomme streng.
- Suffikstræ : Trie og suffiksetræ er nært beslægtede. et suffiksetræ (også kaldet PAT-træ eller, i en tidligere form, positionstræ) er et komprimeret trie, der indeholder alle suffikser af den givne tekst som deres nøgler og positioner i teksten som deres værdier. Suffikstræer tillader særligt hurtige implementeringer af mange vigtige strengoperationer.
- Huffman-træ: Huffman-træ er et frekvenssorteret binært træ, der bruges meget i komprimering data. Huffman-træet er konstrueret til at tildele et kort kodeord til en lang tekst baseret på dets hyppighed af forekomster.
- Bunkestruktur [Rediger som foreslået ]: Heapstruktur er en anden meget brugt trestruktur med en bestemt bestillingsegenskab. Der er to typer bunke – Min bunke og Max bunke. I en min bunke skal forældren til en node være mindre end værdierne for alle dens børn. På samme måde har forældrene altid større værdi sammenlignet med alle sine børn. En almindelig implementering af bunke er binær bunke, hvor hver forælder højst kan have to børn.
Andre populære træstrukturer inkluderer, men ikke udtømmende, B -Tree, B + – tree, R-Tree, Counted-B Tree, KD-træ (eller K- dimensionel BST), Beslutningstræ (a variant af n-ary-træ), Markeltræ, Fenwick-træ (eller binært indekstræ), Range Tree.
Svar
- Skabelon som kode ved at danne et afhængighedstræ.
Bær mig nu i 5 minutter for at forklare detaljeret, hvordan vi brugte træ som datastruktur til at løse vores komplekse brugssag.
For at forklare scenariet, lad os tage et lille eksempel på at få data fra en API via tokenbaseret godkendelse.
Så hvis du vil opnå denne bedrift,
- først får du brugernavnet, adgangskoden og lejeroplysningerne og kalder APIet for at hente tokenet.
- Derefter skal du ringe til det actiale API med det hentede token ved at sende det i overskrifterne på anmodningen.
Nu er dette meget simpelt scenario, men tingene bliver ret komplekse, når du skal udføre en kæde af 10 APIer, der hver er afhængige af hinanden.
Det er her, vi kom op med denne afhængighedstræ tilgang
Først skal vi danne en skabelon som denne
Nu efter dette danner vi et afhængighedstræ som dette
Alt defineret som $ {} betød at det er afhængigt af et andet variabels output.
ResourceOps betyder APIer, der skal udføres
Sådan oprettes afhængighedstræet
- Vi vurderer parametre, der er uafhængige og vedhæft dem til roden.
- Vi kommer så til ressourcehandlinger og forstår, at det afhænger af de værdier, der er knyttet til rodnoden. Så vi løsner dem fra dem fra roden og vedhæfter dem derefter til en ny knude.
- Det samme gøres for alle ressourcehandlinger og output.
Når vi opretter afhængighedstræet, går vi til bladnoden udfør det, kom derefter til forælderen med resultatet af eksekvering af bladnoden, og derefter er det forælder, og det er forælder, indtil vi når den øverste node.
Når vi når den øverste knude, får vi resultatet og vender tilbage som et http-succesrespons.
Hvis der er nogen fejl i udførelsen, returnerer vi derefter fejlsvaret på en læsbar måde.
Jeg tror ikke, jeg havde forklaret det lidt, men jeg vil bare fremhæve, hvordan vi løste et virkeligt verdensproblem med treddatastruktur, så dynamiske handlinger kunne udføres uden, at en udvikler skrev noget kode.