Junior
Cos'è un albero binario?
sobes.tech AI
Risposta dell'AI
Un albero binario è una struttura dati a forma di albero in cui ogni nodo ha al massimo due discendenti: sinistro e destro.
Proprietà principali:
- Radice (Root): Il nodo superiore dell’albero.
- Nodo (Node): Elemento dell’albero che contiene dati e collegamenti ai suoi discendenti.
- Figlio (Child): Nodo che si trova direttamente sotto un altro nodo (genitore).
- Genitore (Parent): Nodo che ha uno o più discendenti direttamente sotto di sé.
- Foglia (Leaf): Nodo che non ha discendenti.
- Ramo (Branch): Percorso dalla radice alla foglia.
- Sottostruttura (Subtree): Albero costituito da un nodo e tutti i suoi discendenti.
Tipi diversi di alberi binari:
- Albero binario completo (Full Binary Tree): Ogni nodo ha 0 o 2 discendenti.
- Albero binario perfetto (Perfect Binary Tree): Tutti i livelli, tranne l’ultimo, sono completamente riempiti, e all’ultimo livello tutti i nodi sono disposti il più a sinistra possibile.
- Albero binario bilanciato (Balanced Binary Tree): L’altezza dei sottoalberi sinistro e destro di qualsiasi nodo differisce di al massimo 1. Esempio: albero AVL, albero rosso-nero.
- Albero binario degenerato (Degenerate Binary Tree): Ogni nodo ha al massimo un discendente. Essenzialmente, è una lista collegata.
Viene utilizzato in vari algoritmi e strutture dati, come alberi di ricerca binari, heap, alberi sintattici.