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

Сложность поиска в двоичном дереве поиска (Binary Search Tree, BST) напрямую зависит от его сбалансированности, то есть от высоты дерева h — O(h).

• 
  

  Сбалансированное дерево: O(log n)
  
  В сбалансированном дереве (например, АВЛ-дерево или красно-чёрное дерево) высота h пропорциональна log n, где n — количество узлов. Это обеспечивает очень эффективный поиск, вставку и удаление.

  
  
• 
  

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

  
  

Поэтому при практическом использовании BST ключевой задачей является поддержание его сбалансированности.

Пример реализации поиска в простом BST на Go:

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

// Search ищет значение в дереве, начиная с корня root
func Search(root *Node, value int) bool {
    if root == nil {
        return false
    }

    if value < root.Value {
        return Search(root.Left, value)
    } else if value > root.Value {
        return Search(root.Right, value)
    }

    // Если value == root.Value
    return true
}