Como é determinada a eficiência da pesquisa numa árvore de dados desequilibrada?

A eficiência da pesquisa numa árvore não balanceada é determinada pela profundidade do nó onde o elemento procurado se encontra. No pior caso, se a árvore se degenerar numa lista, o tempo de pesquisa torna-se linear — O(n). Em média, a eficiência depende da estrutura da árvore e da distribuição dos dados. Para avaliação, geralmente usa-se a altura da árvore: quanto mais alta, mais longa será a pesquisa. Em Go, pode-se implementar a pesquisa numa árvore binária assim:

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 a árvore não estiver balanceada, a profundidade pode ser grande, o que reduz a eficiência.