diamo una definizione più rigorosa di albero binario:
un albero può dirsi binario se è vuoto oppure se la sua radice ha al massimo due nodi i quali sono a loro volta degli alberi binari.
in particolare si parla di albero binario completo se ogni nodo (escluse naturalmente le foglie) ha esattamente due figli e tutte le foglie sono allo stesso livello, quindi raggiungibili dalla radice con cammini di pari lunghezza.
in particolare possiamo notare che in un albero binario il tempo di accesso a ogni elemento è limitato dal logaritmo del numero di nodi, quindi è O(log n).
ciò rende gli alberi vantaggiosi per operazioni di inserimento/ricerca di elementi, non per niente si è parlato di alberi binari di ricerca
naturalmente bisogna cercare di bilanciare il più possibile gli elementi all'interno di un albero, poiché in una situazione simile a questa:
la ricerca di un elemento ha tempo lineare (come si usasse una lista). esistono alberi bilanciati, tra i quali gli alberi red&black e i b-alberi (questi però non sono binari).
per ora mi fermo qui