In informatica, un albero binario di ricerca (BST) è un struttura dati ad albero binario basato su nodi che ha le seguenti proprietà…
Il sottoalbero sinistro di un nodo contiene solo i nodi con chiavi minori rispetto alla chiave del nodo.
Il sottoalbero destrro di un nodo contiene solo i nodi con le chiavi maggiori rispetto alla chiave del nodo.
Entrambi i sottoalberi sinistro e destro devono essere anch’essi degli alberi binari di ricerca.
Dalle proprietà di cui sopra ne segue naturalmente che:
Ogni nodo (elemento nella struttura), ha una chiave diversa.
Generalmente, l’informazione rappresentata da ciascun nodo è un record piuttosto che un singolo elemento di dati. Tuttavia, per scopi di sequenziamento, i nodi vengono confrontati in base alle loro chiavi piuttosto che a qualsiasi parte del loro record associati.
Il vantaggio principale di alberi binari di ricerca sulle altre strutture di dati è che gli algoritmi di ordinamento e relativi algoritmi di ricerca come l’attraversamento ordinato (in-order) possono essere molto efficienti.
Gli alberi binari di ricerca sono una struttura dati fondamentale utilizzata per costruire strutture dati più astratte, come i sets, multisets, e gli array associativi.
Un albero di ricerca binaria di dimensioni 9 e profondità 3, con radice 8 e foglie 1, 4, 7 e 13