TechCodeview

Innanzitutto, capiremo il albero binario E albero di ricerca binario separatamente, quindi esamineremo le differenze tra un albero binario e un albero di ricerca binario.

Cos'è un albero binario?

UN Albero binario è unPuntatore al bambino sinistro:Memorizza il riferimento del nodo figlio sinistro.Puntatore al bambino giusto:Memorizza il riferimento del nodo figlio destro.Elemento dati:L'elemento dati è il valore dei dati memorizzati dal nodo.

L'albero binario può essere rappresentato come:

Nella figura sopra, possiamo osservare che ogni nodo contiene al massimo 2 figli. Se qualsiasi nodo non contiene il figlio sinistro o destro, il valore del puntatore rispetto a quel figlio sarebbe NULL.

Le terminologie di base utilizzate in un albero binario sono:

Nodo radice:Il nodo radice è il primo o il nodo più in alto in un albero binario.Nodo principale:Quando un nodo è connesso a un altro nodo tramite i bordi, quel nodo è noto come nodo genitore. In un albero binario, il nodo genitore può avere un massimo di 2 figli.Nodo figlio:Se un nodo ha un suo predecessore, quel nodo è conosciuto come a nodo figlio .Nodo foglia:Il nodo che non contiene alcun figlio noto come a nodo fogliare .Nodo interno:Il nodo che ha almeno 2 figli noto come an nodo interno .Profondità di un nodo:La distanza dal nodo radice al nodo dato è nota come a profondità di un nodo . Forniamo etichette a tutti i nodi come il nodo radice è etichettato con 0 poiché non ha profondità, i figli dei nodi radice sono etichettati con 1, i figli del figlio radice sono etichettati con 2.Altezza:La distanza più lunga dal nodo radice al nodo foglia è la altezza del nodo .

In un albero binario c'è un albero conosciuto come a albero binario perfetto . È un albero in cui tutti i nodi interni devono contenere due nodi e tutti i nodi foglia devono essere alla stessa profondità. Nel caso di un albero binario perfetto, il numero totale di nodi esistenti in un albero binario può essere calcolato utilizzando la seguente equazione:

n = 2^m+1-1

dove n è il numero di nodi, m è la profondità di un nodo.

Cos'è un albero di ricerca binaria?

UN Albero di ricerca binario è un albero che segue un certo ordine per disporre gli elementi, mentre l'albero binario non segue alcun ordine. In un albero di ricerca binario, il valore del nodo sinistro deve essere minore del nodo genitore e il valore del nodo destro deve essere maggiore del nodo genitore.

Comprendiamo il concetto di albero di ricerca binario attraverso esempi.

Nella figura sopra, possiamo osservare che il valore del nodo radice è 15, che è maggiore del valore di tutti i nodi nel sottoalbero sinistro. Il valore del nodo radice è inferiore ai valori di tutti i nodi in un sottoalbero destro. Ora passiamo al figlio sinistro del nodo radice. 10 è maggiore di 8 e minore di 12; soddisfa anche la proprietà dell'albero di ricerca binario. Ora passiamo al figlio destro del nodo radice; il valore 20 è maggiore di 17 e minore di 25; soddisfa anche la proprietà dell'albero di ricerca binario. Pertanto, possiamo dire che l'albero mostrato sopra è l'albero di ricerca binario.

Ora, se cambiamo il valore da 12 a 16 nell'albero binario sopra, dobbiamo scoprire se è ancora un albero di ricerca binario o meno.

Il valore del nodo radice è 15 che è maggiore di 10 ma minore di 16, quindi non soddisfa la proprietà dell'albero di ricerca binario. Pertanto, non è un albero di ricerca binario.

Operazioni sull'albero binario di ricerca

Possiamo eseguire operazioni di inserimento, eliminazione e ricerca sull'albero di ricerca binario. Capiamo come viene eseguita una ricerca su una ricerca binaria. Di seguito è riportato l'albero binario sul quale dobbiamo effettuare l'operazione di ricerca:

Supponiamo di dover cercare 10 nell'albero binario sopra. Per eseguire la ricerca binaria, prenderemo in considerazione tutti i numeri interi di un array ordinato. Per prima cosa creiamo un elenco completo in uno spazio di ricerca e tutti i numeri esisteranno nello spazio di ricerca. Lo spazio di ricerca è contrassegnato da due puntatori, ovvero inizio e fine. L'array dell'albero binario sopra può essere rappresentato come

Per prima cosa calcoleremo l'elemento centrale e confronteremo l'elemento centrale con l'elemento da cercare. L'elemento centrale viene calcolato utilizzando n/2. Il valore di n è 7; pertanto, l'elemento centrale è 15. L'elemento centrale non è uguale all'elemento cercato, ovvero 10.

Nota: se l'elemento da cercare è inferiore all'elemento centrale, la ricerca verrà eseguita nella metà sinistra; altrimenti la ricerca verrà effettuata nella metà destra. In caso di uguaglianza, l'elemento viene trovato.

Poiché l'elemento da cercare è inferiore all'elemento centrale, la ricerca verrà eseguita sull'array di sinistra. Ora la ricerca è ridotta alla metà, come mostrato di seguito:

L'elemento centrale nell'array di sinistra è 10, che è uguale all'elemento cercato.

Complessità temporale

In una ricerca binaria ci sono n elementi. Se l'elemento centrale non è uguale all'elemento cercato, lo spazio di ricerca si riduce a n/2 e continueremo a ridurre lo spazio di ricerca di n/2 finché non avremo trovato l'elemento. Nell'intera riduzione, se ci spostiamo da n a n/2 a n/4 e così via, allora occuperà log₂n passi.

Differenze tra albero binario e albero di ricerca binario