Albero binario completo contro albero binario completo
L'albero binario è un albero in cui ogni nodo ha uno o due figli. In un albero binario, un nodo non può avere più di due figli. In un albero binario, i bambini sono chiamati bambini "sinistra" e "destra". I nodi figlio contengono un riferimento al loro genitore. Un albero binario completo è un albero binario in cui ogni livello dell'albero binario è completamente riempito tranne l'ultimo livello. Nel livello non riempito, i nodi sono collegati a partire dalla posizione più a sinistra. Un albero binario completo è un albero in cui ogni nodo dell'albero ha due figli tranne le foglie dell'albero.
Cos'è l'albero binario completo?
L'albero binario completo è un albero binario in cui ogni nodo dell'albero ha esattamente zero o due figli. In altre parole, ogni nodo nell'albero tranne le foglie ha esattamente due figli. La figura 1 di seguito mostra un albero binario completo. In un albero binario completo, il numero di nodi (n), il numero di laves (l) e il numero di nodi interni (i) è correlato in modo speciale in modo tale che se ne conosci uno puoi determinare gli altri due valori come segue:
1. Se un albero binario completo ha i nodi interni:
– Numero di foglie l=i+1
– Numero totale di nodi n=2i+1
2. Se un albero binario completo ha n nodi:
– Numero di nodi interni i=(n-1)/2
– Numero di foglie l=(n+1)/2
3. Se un albero binario completo ha l foglie:
– Numero totale di nodi n=2l-1
– Numero di nodi interni i=l-1
Cos'è l'albero binario completo?
Come mostrato nella figura 2, un albero binario completo è un albero binario in cui ogni livello dell'albero è completamente riempito tranne l'ultimo livello. Inoltre, nell'ultimo livello, i nodi dovrebbero essere collegati a partire dalla posizione più a sinistra. Un albero binario completo di altezza h soddisfa le seguenti condizioni:
– Dal nodo radice, il livello sopra l'ultimo livello rappresenta un albero binario completo di altezza h-1
– Uno o più nodi nell'ultimo livello possono avere 0 o 1 figli
– Se a, b sono due nodi nel livello sopra l'ultimo livello, allora a ha più figli di b se e solo se a è situato a sinistra di b
Qual è la differenza tra l'albero binario completo e l'albero binario completo?
Alberi binari completi e alberi binari completi hanno una chiara differenza. Mentre un albero binario completo è un albero binario in cui ogni nodo ha zero o due figli, un albero binario completo è un albero binario in cui ogni livello dell'albero binario è completamente riempito tranne l'ultimo livello. Alcune strutture di dati speciali come gli heap devono essere alberi binari completi mentre non è necessario che siano alberi binari completi. In un albero binario completo, se conosci il numero di nodi totali o il numero di lave o il numero di nodi interni, puoi trovare gli altri due molto facilmente. Ma un albero binario completo non ha una proprietà speciale che mette in relazione questi tre attributi.
