Какие ещё структуры данных знаешь помимо хеш-таблиц (деревья)? Какая асимптотическая сложность поиска в бинарном дереве и по какому основанию логарифм? Как достигается такая сложность (сортировка vs балансировка)?

Без конкретного кода сложно точно определить сложность алгоритма, но если в вопросе упоминается дерево, то, скорее всего, речь идет о структуре данных, где элементы организованы иерархически — каждый узел может иметь дочерние узлы.

Дерево — это структура данных, состоящая из узлов, где один узел является корнем, а остальные — потомками. Например, бинарное дерево, где у каждого узла не более двух детей.

Сложность алгоритма зависит от операции и структуры дерева. Например, обход бинарного дерева (in-order, pre-order, post-order) имеет сложность O(n), где n — количество узлов, так как каждый узел посещается один раз.

Пример обхода бинарного дерева на Go:

func inorderTraversal(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    result := inorderTraversal(root.Left)
    result = append(result, root.Val)
    result = append(result, inorderTraversal(root.Right)...) 
    return result
}

Здесь сложность O(n), так как каждый узел посещается один раз.