¿Cómo se determina la eficiencia de la búsqueda en un árbol de datos no balanceado?

La eficiencia de la búsqueda en un árbol no balanceado se determina por la profundidad del nodo donde se encuentra el elemento buscado. En el peor caso, si el árbol se degenera en una lista, el tiempo de búsqueda se vuelve lineal — O(n). En promedio, la eficiencia depende de la estructura del árbol y la distribución de los datos. Para evaluarlo, generalmente se usa la altura del árbol: cuanto más alto, más larga será la búsqueda. En Go, se puede implementar la búsqueda en un árbol binario así:

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)
}

Si el árbol no está balanceado, la profundidad puede ser grande, lo que reduce la eficiencia.