Что такое двоичное дерево поиска

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

1. Все значения в левом поддереве меньше значения узла
2. Все значения в правом поддереве больше значения узла
3. Оба поддерева также являются BST

Основные операции (в среднем O(log n)):

• Поиск
• Вставка
• Удаление

Пример реализации узла:

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

Пример поиска:

def search(root, val):
    if not root or root.val == val:
        return root
    if val < root.val:
        return search(root.left, val)
    return search(root.right, val)

Преимущества: эффективный поиск, сортировка при обходе inorder. Недостатки: может выродиться в связный список (O(n) операций) при неудачной последовательности вставок.