Alberi binari e alberi di ricerca binaria utilizzati negli algoritmi - manichini

Un tipo speciale di struttura ad albero è il heap binario, che colloca ciascuno degli elementi del nodo in un ordine speciale. Gli alberi di ricerca ti consentono di cercare rapidamente i dati. Ottenere gli elementi di dati, ordinarli in un albero e poi cercarli è uno dei modi più rapidi per trovare informazioni.

In un heap binario, il nodo radice contiene sempre il valore più piccolo. Quando osservi i rami, vedi che i rami di livello superiore sono sempre un valore inferiore rispetto ai rami e alle foglie di livello inferiore. L'effetto è di mantenere l'albero equilibrato e in un ordine prevedibile in modo che la ricerca diventi estremamente efficiente. Il costo è nel mantenere l'albero equilibrato.

Di tutte le attività che le applicazioni fanno, la ricerca richiede più tempo e anche la più richiesta. Anche se l'aggiunta di dati (e l'ordinamento successivo) richiede un po 'di tempo, il vantaggio di creare e mantenere un set di dati deriva dall'utilizzarlo per svolgere un lavoro utile, il che significa cercarlo per informazioni importanti. Di conseguenza, a volte è possibile ottenere una funzionalità CRUD meno efficiente e persino una routine di ordinamento non ottimale, ma le ricerche devono procedere nel modo più efficiente possibile. L'unico problema è che nessuno ricerca esegue tutte le attività con assoluta efficienza, quindi è necessario valutare le opzioni in base a ciò che si prevede di fare come parte delle routine di ricerca.

Due dei metodi più efficienti di ricerca riguardano l'uso dell'albero di ricerca binario (BST) e dell'heap binario. Entrambe le tecniche di ricerca si basano su una struttura ad albero per contenere le chiavi utilizzate per accedere agli elementi di dati. Tuttavia, la disposizione dei due metodi è diversa, motivo per cui uno ha vantaggi rispetto all'altra quando si eseguono determinati compiti. Questa figura mostra la disposizione per un BST.

La disposizione dei tasti quando si utilizza un BST.

Nota come i tasti seguono un ordine in cui i numeri minori appaiono a sinistra e i numeri più grandi appaiono a destra. Il nodo radice contiene un valore che si trova nel mezzo dell'intervallo di chiavi, dando al BST un approccio bilanciato facilmente comprensibile per l'archiviazione delle chiavi. Confrontate questa disposizione con l'heap binario mostrato qui.

La disposizione delle chiavi quando si utilizza un heap binario.

Ogni livello contiene valori inferiori al livello precedente e la radice contiene il valore chiave massimo per l'albero. Inoltre, in questo caso particolare, i valori minori appaiono a sinistra e quelli maggiori a destra (sebbene questo ordine non sia rigorosamente applicato). La figura mostra in realtà un heap binario massimo. È inoltre possibile creare un heap minuscolo in cui la radice contiene il valore della chiave più basso e ogni livello si basa su valori più alti, con i valori più alti che appaiono come parte delle foglie.

Come notato in precedenza, il BST ha alcuni vantaggi rispetto all'heap binario quando viene utilizzato per eseguire una ricerca. Il seguente elenco fornisce alcuni dei punti salienti di questi vantaggi:

• La ricerca di un elemento richiede tempo O (log n), in contrasto con il tempo O (n) per un heap binario.
• La stampa degli elementi in ordine richiede solo il tempo O (log n), in contrasto con O (n log n) per un heap binario.
• La ricerca del pavimento e del soffitto richiede O (log n) tempo.
• L'individuazione del Kth elemento più piccolo / più grande richiede O (log n) tempo quando l'albero è configurato correttamente.

Se questi tempi sono importanti dipende dalla tua applicazione. BST tende a funzionare meglio in situazioni in cui si impiegano più tempo a cercare e meno tempo a costruire l'albero. Un heap binario tende a funzionare meglio in situazioni dinamiche in cui le chiavi cambiano regolarmente. L'heap binario offre anche vantaggi, come descritto nel seguente elenco:

• La creazione delle strutture richieste richiede meno risorse perché gli heap binari si basano sugli array, rendendoli anche più amichevoli nella cache.
• La compilazione di un heap binario richiede tempo O (n), in contrasto con BST, che richiede tempo O (n log n).
• L'uso di puntatori per implementare l'albero non è necessario.
• Affidarsi alle variazioni dell'heap binario (ad esempio, l'heap di Fibonacci) offre vantaggi come l'aumento e la diminuzione dei tempi di chiave del tempo O (1).