Come si determina l'efficienza della ricerca in un albero di dati sbilanciato?

L'efficienza della ricerca in un albero sbilanciato è determinata dalla profondità del nodo in cui si trova l'elemento cercato. Nel peggiore dei casi, se l'albero si degenera in una lista, il tempo di ricerca diventa lineare — O(n). In media, l'efficienza dipende dalla struttura dell'albero e dalla distribuzione dei dati. Per valutarla, si usa generalmente l'altezza dell'albero: più alto è l'albero, più lunga sarà la ricerca. In Go, si può implementare la ricerca in un albero binario così:

func search(node *Node, key int) *Node {
    if node == nil || node.key == key {
        return node
    }
    if key < node.key {
        return search(node.left, key)
    }
    return search(node.right, key)
}

Se l'albero non è bilanciato, la profondità può essere grande, riducendo l'efficienza.