Дерево поиска — это структура данных, где каждый узел имеет не более двух потомков (левый и правый), причем для любого узла: - Все элементы левого поддерева меньше значения текущего узла. - Все элементы правого поддерева больше значения текущего узла. **Основные операции:** - **Поиск**: начинаем с корня, сравниваем искомое значение с текущим узлом, двигаемся влево/вправо. - **Вставка**: аналогично поиску, но добавляем новый узел в нужное место. - **Удаление**: сложнее, зависит от количества потомков удаляемого узла. ``` class Node: def __init__(self, key): self.left = None self.right = None self.val = key def insert(root, key): if root is None: return Node(key) else: if root.val < key: root.right = insert(root.right, key) else: root.left = insert(root.left, key) return root ``` **Сложность операций**: в среднем O(log n), но может деградировать до O(n) при несбалансированном дереве.