Risposta migliore
Esistono diversi tipi di strutture dati ad albero. Alcuni di loro sono
- Albero binario : questo è il più basilare della struttura ad albero. Dove ogni nodo può avere al massimo due figli. Un albero binario perfetto è un albero binario in cui tutti i nodi interni hanno due figli e tutti le foglie hanno lo stesso profondità o lo stesso livello. Un albero binario completo (a volte indicato come [15] o albero binario piano) è un albero in cui ogni nodo dellalbero ha 0 o 2 figli. In un completo albero binario ogni livello, tranne forse lultimo, è completamente riempito e tutti i nodi nellultimo livello sono il più a sinistra possibile. Nel infinito completo albero binario, ogni nodo ha due figli.
- Albero di ricerca binario: BST è un albero binario con determinate proprietà come, e il figlio sinistro del nodo dato contiene un valore minore di uguale al nodo dato e il figlio destro contiene un nodo maggiore del nodo dato.
- Albero AVL o albero binario bilanciato in altezza : è una variazione dellalbero binario in cui la differenza di altezza tra il sottoalbero sinistro e destro può essere al massimo 1. Se in qualsiasi momento differiscono di più di uno, il ribilanciamento viene eseguito per ripristinare questa proprietà. La ricerca, linserimento e leliminazione richiedono tutti il tempo O (log n) sia nel caso medio che nel peggiore, dove n è il numero di nodi nellalbero prima delloperazione.
- Albero rosso-nero : Unaltra variante di albero binario simile allalbero AVL è un albero di ricerca binario autobilanciato. In questo albero i nodi sono colorati di rosso o nero.
- Albero di apertura: Un albero di apertura è un albero di ricerca binario autoregolante con il proprietà aggiuntiva a cui gli elementi acceduti di recente sono di nuovo rapidamente accessibili. Tutte le normali operazioni su un albero di ricerca binario sono combinate con unoperazione di base, chiamata splaying. Allargare lalbero per un certo elemento riorganizza lalbero in modo che lelemento sia posizionato alla radice dellalbero.
- N-ary tree: In questo albero la limitazione dellalbero binario viene rimossa. Qui un nodo può avere al massimo n figli. Come lalbero binario, può essere un albero n-ario completo, completo o perfetto. N-ary è un po noto come foresta.
- Trie Structure : In informatica, un trie, chiamato anche albero digitale e talvolta radix albero o albero dei prefissi (poiché possono essere cercati per prefissi), è una struttura dati ad albero ordinata che viene utilizzata per memorizzare un insieme dinamico o un array associativo in cui le chiavi sono solitamente stringhe. Tutti i discendenti di un nodo hanno un prefisso comune della stringa associata a quel nodo e la radice è associata alla stringa vuota.
- Albero dei suffissi : Trie e suffix tree sono strettamente correlati. un albero dei suffissi (chiamato anche albero PAT o, in una forma precedente, albero delle posizioni) è un trie compresso contenente tutti i suffissi del testo dato come chiavi e posizioni nel testo come loro valori. Gli alberi dei suffissi consentono implementazioni particolarmente veloci di molte importanti operazioni sulle stringhe.
- Albero di Huffman: Lalbero di Huffman è un albero binario ordinato in base alla frequenza utilizzato ampiamente per dati. Lalbero di Huffman è costruito per allocare una parola in codice breve a un testo lungo in base alla sua frequenza di occorrenze.
- Struttura heap [Modifica come suggerito ]: La struttura dellheap è unaltra struttura ad albero ampiamente utilizzata con una proprietà di ordinamento specifica. Esistono due tipi di heap: heap minimo e heap massimo. In un min heap il genitore di un nodo deve essere più piccolo dei valori di tutti i suoi figli. Allo stesso modo in max heap il genitore ha sempre un valore maggiore rispetto a tutti i suoi figli. Unimplementazione comune di heap è lheap binario in cui ogni genitore può avere al massimo due figli.
Unaltra struttura ad albero popolare include, ma non in modo esaustivo, B -Albero, B + – albero, R-Tree, Counted-B Tree, KD tree (o K- dimensionale BST), Albero decisionale (un variant of n-ary tree), Markel tree, Fenwick tree (o binary index tree), Range Tree.
Risposta
- Modello come codice formando un albero delle dipendenze.
Ora abbi pazienza con me per 5 minuti per spiegare in dettaglio come abbiamo utilizzato lalbero come struttura dati per risolvere il nostro caso duso complesso.
Per spiegare lo scenario, prendiamo un piccolo esempio di come ottenere dati da unAPI tramite autenticazione basata su token.
Quindi, se vuoi ottenere questo risultato,
- ottieni prima il nome utente, la password e le informazioni sul tenant e chiama lAPI per recuperare il token.
- Quindi, con il token recuperato, chiama lAPI actial passandola nelle intestazioni della richiesta.
Questo è uno scenario molto semplice, ma le cose diventano piuttosto complesse quando devi eseguire una catena di 10 API “S, ciascuna dipendente luna dallaltra.
È qui che è venuto fuori questo approccio ad albero delle dipendenze
Per prima cosa dobbiamo formare un modello come questo
Ora, dopo questo, formiamo un albero delle dipendenze come questo
Qualsiasi cosa definita come $ {} significava che dipende dalloutput di unaltra variabile.
ResourceOps indica che le API devono essere eseguite
Questo è il modo in cui viene creato lalbero delle dipendenze
- Valutiamo parametri che sono indipendenti e allegarli alla radice.
- Veniamo quindi alle operazioni sulle risorse e comprendiamo che dipende dai valori associati al nodo radice. Quindi li scolleghiamo dalla radice e quindi li colleghiamo al nuovo nodo.
- Lo stesso verrà fatto per tutte le operazioni sulle risorse e output.
Una volta creato lalbero delle dipendenze, andiamo al nodo foglia eseguirlo, quindi passare al genitore con il risultato dellesecuzione del nodo foglia e quindi è genitore ed è genitore fino a raggiungere il nodo superiore.
Una volta raggiunto il nodo superiore, otteniamo il risultato e torniamo indietro come risposta di successo http.
Se ci sono errori in esecuzione, restituiamo la risposta dellerrore in modo leggibile.
Non credo di averlo spiegato in parte, ma voglio solo evidenziare come abbiamo risolto un problema reale con la struttura dei dati ad albero per azioni dinamiche da eseguire senza che uno sviluppatore scrivesse del codice.