Cel mai bun răspuns
Există diferite tipuri de structuri de date în copaci. Unele dintre ele sunt
- Arbore binar : Acesta este elementul de bază cel mai de bază din structura arborelui. Unde fiecare nod poate avea maxim doi copii. Un arbore binar perfect este un arbore binar în care toate nodurile interioare au doi copii și frunzele au același adâncime sau același nivel . A copac binar complet (uneori denumit arborele binar propriu [15] sau plan) este un copac în care fiecare nod din copac are fie 0, fie 2 copii. Într-un complet arborele binar, fiecare nivel, cu excepția eventuală a ultimului, este complet umplut și toate nodurile din ultimul nivel sunt cât mai departe posibil. În complet infinit copac binar, fiecare nod are doi copii.
- Arborele de căutare binar: BST este un copac binar cu anumite proprietăți cum ar fi, și copilul stâng al nodului dat conține o valoare mai mică decât egală cu nodul dat și copilul din mâna dreaptă conține nod mai mare decât nodul dat.
- Arborele AVL sau arborele binar echilibrat : este o variație a arborelui binar în care diferența de înălțime între arborele sub stânga și dreapta poate fi cel mult 1. Dacă în orice moment diferă cu mai mult de unul, reechilibrarea se face pentru restabiliți această proprietate. Căutarea, inserarea și ștergerea necesită tot timpul O (log n) atât în cazurile medii, cât și în cele mai rele, în care n este numărul de noduri din arborele anterior operației.
- Arborele roșu-negru : O altă variantă a arborelui binar similar cu arborele AVL este un arbore de căutare binar auto-echilibrat. În acest arbore nodurile sunt fie roșii, fie negre.
- Arborele Splay: Un arbore splay este un arbore de căutare binar auto-ajustabil cu proprietate suplimentară la care elementele accesate recent sunt rapid accesibile din nou. Toate operațiile normale pe un arbore de căutare binară sunt combinate cu o operație de bază, numită splaying. Afișarea arborelui pentru un anumit element rearanjează arborele astfel încât elementul să fie plasat la rădăcina arborelui.
- Arborele N-ary: În acest arbore se elimină limitarea arborelui binar. Aici un nod poate avea cel mult n copii. La fel ca arborele binar poate fi un copac n-ari complet, complet sau perfect. N-ary este cunoscut sub denumirea de pădure.
- Structura Trie : în informatică, un trie, numit și copac digital și uneori radix arborele sau arborele prefixului (deoarece pot fi căutate prin prefixe), este o structură de date arborescentă ordonată care este utilizată pentru a stoca un set dinamic sau o matrice asociativă unde cheile sunt de obicei șiruri. Toți descendenții unui nod au un prefix comun al șirului asociat cu acel nod, iar rădăcina este asociată șirului gol.
- Arborele sufixului : Trie și sufixul sunt strâns legate. un arbore de sufixe (numit și arbore PAT sau, într-o formă anterioară, arbore de poziție) este un trie comprimat care conține toate sufixele textului dat ca chei și pozițiile în text ca valori. Arborii sufixului permit implementări deosebit de rapide ale multor operații importante de șiruri.
- Arborele Huffman: Arborele Huffman este un arboret binar sortat în frecvență utilizat pe scară largă la comprimare date. Arborele Huffman este construit pentru a aloca un cuvânt de cod scurt unui text lung pe baza frecvenței sale de apariții.
- Structură Heap [Editați după cum este sugerat ]: Structura Heap este o altă structură de copac utilizată pe scară largă cu o proprietate specifică de ordonare. Există două tipuri de heap – Min heap și Max heap. Într-o grămadă de min, părintele unui nod trebuie să fie mai mic decât valorile tuturor copiilor săi. În mod similar, în heap maxim, părintele are întotdeauna o valoare mai mare în comparație cu toți copiii săi. O implementare obișnuită a heap-ului este heap-ul binar în care fiecare părinte poate avea cel mult doi copii.
Alte structuri populare de copac includ, dar nu exhaustiv, B -Copac, B + – copac, copac R, copac numărat-B, copac KD (sau K- dimensional BST), copac de decizie (a varianta arborelui n-ari), Arborele Markel, Arborele Fenwick (sau Arborele index binar), Arborele Range.
Răspuns
- Șablon ca cod prin formarea unui arbore de dependență.
Acum purtați-mă cu mine timp de 5 minute pentru a explica în detaliu cum am folosit arborele ca structură de date pentru a rezolva cazul nostru de utilizare complex.
Pentru a explica scenariul, să luăm un mic exemplu de obținere a datelor dintr-un API prin autentificare bazată pe token.
Deci, dacă doriți să realizați acest lucru,
- primiți mai întâi numele de utilizator, parola și informațiile chiriașului și apelați API-ul pentru a prelua jetonul.
- Apoi, cu jetonul preluat, apelați API-ul activ prin trecerea acestuia în antetele cererii.
Acum acesta este un scenariu foarte simplu, dar lucrurile devin destul de complexe atunci când trebuie să executați un lanț din 10 API „S fiecare dependent unul de altul.
Aici am venit cu această abordare a arborelui dependenței
Mai întâi trebuie să formăm un șablon ca acesta
Acum, după aceasta, formăm un arbore de dependență ca acesta
Orice a fost definit ca $ {} înseamnă că depinde de o altă ieșire de variabile.
ResourceOps înseamnă API-uri care trebuie executate
Acesta este modul în care este creat arborele dependenței
- Evaluăm parametrii independenți și atașați-le la rădăcină.
- Ajungem apoi la operațiuni de resurse și înțelegem că depinde de valorile atașate nodului rădăcină. Așa că le detașăm de ele din rădăcină și apoi le atașăm la noul nod.
- La fel se va proceda la toate operațiunile de resurse și ieșire.
Odată ce am creat arborele dependenței, mergem la nodul frunză executați-l apoi veniți la părinte cu rezultatul execuției nodului frunze și apoi este „părinte și părinte” până ajungem la nodul de sus.
Odată ce am ajuns la nodul de sus, atunci obținem rezultatul și ne întoarcem ca răspuns de succes http.
Dacă există vreo eroare în execuție, vom întoarce răspunsul de eroare în mod lizibil.
Nu cred că am explicat câte ceva, dar vreau doar să subliniez cum am rezolvat o problemă din lumea reală cu structura de date arborescentă pentru ca acțiunile dinamice să fie executate fără ca un dezvoltator să scrie un cod.