Каков принцип работы дерева поиска

Дерево поиска — это структура данных, где каждый узел имеет не более двух потомков (левый и правый), причем для любого узла:

• Все элементы левого поддерева меньше значения текущего узла.
• Все элементы правого поддерева больше значения текущего узла.

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

• Поиск: начинаем с корня, сравниваем искомое значение с текущим узлом, двигаемся влево/вправо.
• Вставка: аналогично поиску, но добавляем новый узел в нужное место.
• Удаление: сложнее, зависит от количества потомков удаляемого узла.

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) при несбалансированном дереве.