Как определяется эффективность поиска в несбалансированном дереве данных?

Эффективность поиска в несбалансированном дереве определяется глубиной узла, на котором находится искомый элемент. В худшем случае, если дерево вырождается в список, время поиска становится линейным — O(n). В среднем эффективность зависит от структуры дерева и распределения данных. Для оценки обычно используют высоту дерева: чем выше дерево, тем дольше поиск. В Go можно реализовать поиск в бинарном дереве так:

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

Если дерево несбалансированное, глубина может быть большой, что снижает эффективность.