Какова сложность поиска в несбалансированном двоичном дереве поиска?

Сложность поиска в несбалансированном двоичном дереве поиска (BST) сильно зависит от его структуры.

• 
  

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

  
  
• 
  

  Средний случай: O(log n)
  
  Для случайно построенного дерева высота в среднем составляет log n, что обеспечивает быстрый поиск.

  
  

Пример вырожденного дерева на Go:

type Node struct {
    Value int
    Left  *Node
    Right *Node
}

// Вставка 1, 2, 3, 4 приведет к вырожденному дереву:
// 1 -> Right: 2 -> Right: 3 -> Right: 4

// Поиск в таком дереве эквивалентен поиску в связном списке
func search(root *Node, target int) bool {
    current := root
    for current != nil {
        if current.Value == target {
            return true
        }
        if target < current.Value {
            current = current.Left
        } else {
            current = current.Right
        }
    }
    return false
}

Вывод: Из-за риска деградации до O(n) на практике часто используют сбалансированные деревья (например, АВЛ-деревья или красно-чёрные деревья), которые гарантируют сложность поиска, вставки и удаления O(log n) даже в худшем случае.