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

Временная сложность поиска узла в бинарном дереве зависит от его структуры:

• В обычном бинарном дереве (без упорядочивания) поиск может потребовать обхода всех узлов, то есть сложность в худшем случае — O(n), где n — количество узлов.

• В бинарном дереве поиска (BST), если дерево сбалансировано, поиск выполняется за O(log n), так как на каждом шаге мы отбрасываем половину дерева.

• В худшем случае, если BST вырождается в список (например, все узлы идут в одну сторону), сложность поиска становится O(n).

Пример поиска в сбалансированном BST на Python:

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def search(root, key):
    if root is None or root.val == key:
        return root
    if key < root.val:
        return search(root.left, key)
    else:
        return search(root.right, key)

Здесь поиск работает за O(log n) при сбалансированном дереве.