Какая скорость в бинарном дереве

Скорость операций в бинарном дереве зависит от его сбалансированности. В идеально сбалансированном дереве (например, AVL или красно-черном) время операций составляет O(log n), где n — количество узлов. В несбалансированном дереве (вырожденном в список) — O(n).

Основные операции:

• Поиск: O(log n) / O(n)
• Вставка: O(log n) / O(n)
• Удаление: O(log n) / O(n)

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

# Пример несбалансированного дерева (вырождается в список)
root = Node(1)
root.right = Node(2)
root.right.right = Node(3)  # O(n) для поиска 3