🔴 Сложный ⏱️ 50 минут

Бинарные деревья поиска

📋 Содержание урока

Бинарные деревья поиска 🌳

Открой любую задачу, где нужно быстро искать, вставлять и удалять данные одновременно, — и ты быстро упрёшься в неприятный компромисс. Отсортированный массив даёт поиск за $O(\log n)$ бинарным поиском, но вставка нового элемента в середину требует сдвига половины массива, то есть $O(n)$. Связный список, наоборот, вставляет за $O(1)$, если ты уже стоишь в нужном месте, но чтобы это место найти, приходится идти по списку линейно, снова $O(n)$. Возникает естественный вопрос: можно ли построить структуру, которая одновременно ищет быстро и вставляет быстро? Бинарное дерево поиска — первый серьёзный ответ на этот вопрос, и именно он лежит в основе индексов баз данных, структур для геометрического поиска и, что особенно важно для тебя как будущего специалиста по данным, алгоритмов поиска ближайших соседей в многомерных пространствах.

Идея обманчиво проста: превратить бинарный поиск, который ты привык делать над статичным отсортированным массивом, в динамическую структуру. В прошлом уроке ты познакомился с деревьями как таковыми — узлы, корень, листья, высота, рекурсивная природа. Бинарное дерево поиска добавляет к этой структуре одно-единственное, но чрезвычайно мощное правило упорядоченности: для любого узла все значения в его левом поддереве строго меньше значения самого узла, а все значения в правом поддереве строго больше. Это правило, применённое рекурсивно на каждом уровне, превращает дерево в живую, постоянно обновляемую версию отсортированного массива, по которому можно двигаться так же, как ты двигался бы при бинарном поиске — только теперь вставка и удаление не требуют сдвига половины структуры.

Здесь же скрывается прямой мост к машинному обучению, который сделает эту тему не абстрактным упражнением, а рабочим инструментом. Возьми правило BST — «разделяй пространство пополам по значению координаты» — и обобщи его на несколько измерений, чередуя координату, по которой ты делишь пространство, на каждом уровне дерева. Получится KD-дерево (сокращение от «дерево, разбивающее $k$-мерное пространство») — структура, которая лежит в основе быстрого поиска $k$ ближайших соседей в алгоритме k-NN: вместо перебора расстояний до всех точек датасета ты спускаешься по дереву, отсекая целые области пространства, где точно не может быть более близкого соседа, чем уже найденный. Та же идея — быстро находить объекты, «похожие» на запрос, без полного перебора, — лежит в основе части векторных баз данных, которые ищут ближайшие эмбеддинги для рекомендательных систем и семантического поиска. Прежде чем разбираться с этими более сложными структурами, стоит досконально освоить их прародителя на одномерном случае — именно этим ты и займёшься в этом уроке.

Урок построен вокруг четырёх опор: свойства упорядоченности и того, как оно превращает поиск в спуск по дереву; операций вставки и удаления, которые обязаны сохранять это свойство; принципиальной разницы между лучшим, средним и худшим случаем сложности — и почему вырожденное дерево превращается в обычный список; и, наконец, симметричного обхода, который бесплатно выдаёт отсортированную последовательность элементов. К концу урока ты будешь свободно строить, искать, вставлять, удалять и обходить BST, а заодно поймёшь, почему в реальных системах голое BST почти никогда не используют без балансировки — это станет темой следующего урока.

История: откуда взялась эта идея

Идея упорядоченного двоичного дерева не была изобретена одним человеком в одной статье — она возникла практически одновременно у нескольких исследователей на рубеже 1950-х и 1960-х годов, когда информатика как дисциплина только формировалась, а задача эффективного поиска и сортировки данных на только что появившихся компьютерах с ограниченной памятью стояла крайне остро. В своей фундаментальной энциклопедии «Искусство программирования» Дональд Кнут прослеживает независимое появление концепции бинарного дерева поиска сразу у нескольких групп: среди первых, кто явно описал структуру и связанные с ней алгоритмы поиска и вставки, были британские исследователи Питер Уиндли, Эндрю Бут и Александр Колин, работавшие над этой идеей примерно в 1960 году, причём независимо друг от друга и от чуть более ранних набросков идеи у других авторов.

Отдельного упоминания заслуживает Томас Хиббард, который в 1962 году опубликовал статью, где не только описал операции над деревом, но и впервые формально разобрал самую деликатную из них — удаление узла с двумя детьми. Именно алгоритм замены удаляемого узла на минимум его правого поддерева (или, симметрично, на максимум левого поддерева), который ты разберёшь дальше в этом уроке, принято называть методом Хиббарда. До этой работы было не вполне очевидно, как корректно «залатать дыру» в дереве после удаления узла с двумя потомками, не нарушив при этом свойство упорядоченности — Хиббард дал первое строгое и по сей день стандартное решение.

Показательно, что сама идея — организовать данные так, чтобы каждое сравнение отбрасывало половину оставшихся вариантов, — гораздо старше информатики: именно на ней строится идея бинарного поиска в отсортированном списке. Заслуга авторов BST в том, что они перенесли эту идею с неподвижного, заранее отсортированного массива на структуру, которая может расти и меняться во время работы программы — вставляться и удаляться без полной пересборки. С этого момента и до сегодняшнего дня деревья поиска остаются одной из центральных тем информатики: следующий урок про самобалансирующиеся деревья (AVL, красно-чёрные деревья) как раз закроет главную практическую проблему, которую ты обнаружишь в этом уроке, — то, что обычное BST без дополнительных мер может в худшем случае деградировать до линейной структуры.

Свойство упорядоченности и поиск в BST

Интуиция: игра «угадай число», встроенная в структуру данных

Вспомни игру «угадай число от 1 до 100»: ты называешь число, тебе отвечают «больше» или «меньше», и за счёт того, что каждый ответ отсекает половину оставшихся вариантов, за 7 вопросов ты гарантированно находишь загаданное число. Бинарный поиск в отсортированном массиве — это ровно та же игра, формализованная в алгоритм. Бинарное дерево поиска идёт на шаг дальше: оно материализует эту игру в виде явной структуры данных, где каждый узел — это один «вопрос», а его левый и правый потомки — это ветки для ответов «меньше» и «больше». Спускаясь от корня к нужному значению, ты буквально проходишь тот же путь сравнений, что и при бинарном поиске, только идёшь не по индексам массива, а по указателям дерева.

Ключевое отличие от статичного отсортированного массива в том, что структура дерева не обязана быть непрерывным блоком памяти. Каждый узел хранит значение и два указателя — на левого и правого потомка (или None, если потомка нет). Благодаря этому вставка нового значения не требует сдвига остальных элементов — достаточно найти подходящее пустое место и «прицепить» туда новый узел. Именно эта гибкость и есть главная причина, ради которой стоит отказаться от простоты отсортированного массива в пользу более сложной, но динамической структуры дерева.

Определение (свойство BST). Бинарное дерево называется бинарным деревом поиска, если для каждого его узла $x$ выполняется:

  1. Все значения в левом поддереве узла $x$ строго меньше значения $x$.
  2. Все значения в правом поддереве узла $x$ строго больше значения $x$.
  3. Оба поддерева узла $x$ также являются бинарными деревьями поиска (свойство рекурсивно).

Алгоритм поиска значения $k$ начинается в корне и на каждом шаге сравнивает $k$ с текущим узлом: если равны — узел найден; если $k$ меньше — переход в левое поддерево; если $k$ больше — переход в правое. Поиск завершается либо нахождением узла, либо достижением пустого указателя (значения нет в дереве). Время работы поиска составляет $O(h)$, где $h$ — высота дерева, поскольку на каждом шаге спуск идёт ровно на один уровень вниз.

Обрати внимание на третий пункт определения — рекурсивность свойства. Это частая ловушка: недостаточно проверить, что левый ребёнок узла меньше самого узла, а правый — больше. Нужно, чтобы весь левый поддерево целиком лежало ниже значения узла, а весь правый — выше, вплоть до самых дальних листьев. Ты вернёшься к этой тонкости в разделе «Частые ошибки».

Примеры с разбором

Пример 1 (лёгкий). Дано дерево:

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

Найди в нём значение $7$, перечислив последовательность сравнений.

Начинаем в корне $8$: $7 < 8$, идём влево, попадаем в узел $3$. Сравниваем: $7 > 3$, идём вправо, попадаем в узел $6$. Сравниваем: $7 > 6$, идём вправо, попадаем в узел $7$. Значения совпали — узел найден. Всего потребовалось $4$ сравнения, что соответствует спуску на $3$ уровня вниз от корня — ровно высота пути до этого узла.

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

Пример 2 (средний). По тому же дереву определи, сколько сравнений потребуется для поиска значения $20$, которого в дереве нет, и объясни, как алгоритм понимает, что искать дальше некуда.

Спуск: $20 > 8$ → вправо в узел $10$; $20 > 10$ → вправо в узел $14$; $20 > 14$ → нужно идти вправо от узла $14$, но правого потомка у него нет (указатель None). Алгоритм останавливается и возвращает «не найдено» после $3$ сравнений. Важная деталь: поиск отсутствующего значения занимает не больше времени, чем поиск существующего значения на той же глубине — в обоих случаях время определяется исключительно длиной пути от корня, то есть высотой соответствующей ветки, а не тем, найдено значение или нет.

Пример 3 (сложный). Проверь, является ли следующее дерево корректным BST, и если нет — укажи, какое именно свойство нарушено:

        10
       /  \
      5    15
     / \   / \
    2   8 12  20
       /
      9

На первый взгляд всё выглядит правильно: у каждого узла непосредственный левый ребёнок меньше, а правый — больше. Но проверка «только непосредственных детей» здесь недостаточна. Узел $9$ находится в левом поддереве корня (поддерево с вершиной $5$), значит, по определению BST, он обязан быть меньше значения корня $10$ — и это выполняется ($9 < 10$). Но также узел $9$ находится в левом поддереве узла $8$, а значит, обязан быть меньше $8$ — а $9 > 8$. Это дерево не является корректным BST: узел $9$, будучи левым потомком узла $8$, нарушает рекурсивное свойство упорядоченности относительно всего поддерева с корнем $8$, даже несмотря на то, что локально $9 > 8$ выглядит как «правильный» правый ребёнок, а не левый — ошибка именно в том, что $9$ стоит слева от $8$, хотя больше него.

def is_valid_bst(root, low=float('-inf'), high=float('inf')):
    if root is None:
        return True
    if not (low < root.val < high):
        return False
    return (is_valid_bst(root.left, low, root.val) and
            is_valid_bst(root.right, root.val, high))

Эта функция как раз реализует правильную проверку: она передаёт вниз по рекурсии допустимый диапазон значений (low, high), сужая его на каждом шаге, а не сравнивает узел только с непосредственным родителем.

Почему это важно. Поиск — это фундамент, на котором строятся вставка и удаление: ты увидишь дальше, что обе операции начинаются с того же самого спуска по дереву, что и поиск, и лишь в конце добавляют одно действие. Понимание того, что время поиска зависит от высоты дерева, а не от числа его узлов напрямую, — ключ к пониманию всей темы этого урока: именно высота будет тем параметром, который отличает эффективное дерево от неэффективного, и именно за контроль над высотой отвечают самобалансирующиеся деревья следующего урока.

Вставка узла: как добавить значение, сохранив порядок

Интуиция: найти пустое место там же, где закончился бы неудачный поиск

Вставка нового значения в BST использует ту же логику спуска, что и поиск, с одним отличием: вместо того чтобы остановиться, обнаружив, что искомого значения нет (упёрлись в None), алгоритм именно в этом месте и создаёт новый узел. По сути, вставка значения $k$ — это «неудачный поиск» значения $k$, который заканчивается не пустым результатом, а созданием нового листа ровно там, где поиск закончился бы неудачей. Это делает вставку почти тривиальным расширением поиска: ты просто помнишь, откуда пришёл (левый или правый потомок какого узла), и в момент, когда упираешься в None, подключаешь туда новый узел.

Формула (алгоритм вставки). Чтобы вставить значение $k$ в BST с корнем root:

  1. Если дерево пусто, новый узел со значением $k$ становится корнем.
  2. Иначе сравнить $k$ с текущим узлом: если $k$ меньше — рекурсивно вставлять в левое поддерево, если больше — в правое (значения, равные существующему узлу, по распространённому соглашению не добавляются повторно или добавляются в правое поддерево — соглашение нужно фиксировать заранее).
  3. Рекурсия продолжается, пока не будет достигнут пустой указатель — туда и подключается новый узел.

Время работы вставки, как и поиска, составляет $O(h)$, где $h$ — высота дерева на момент вставки, потому что вставка — это спуск по дереву длиной не более $h$, завершающийся одним присоединением узла за $O(1)$.

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

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.val:
        root.left = insert(root.left, key)
    elif key > root.val:
        root.right = insert(root.right, key)
    # при key == root.val дерево не меняем — дубликаты не храним
    return root

Примеры с разбором

Пример 1 (лёгкий). Построй BST, вставляя числа по порядку: $8, 3, 10, 1, 6, 14$.

Вставляем $8$ — дерево было пустым, $8$ становится корнем. Вставляем $3$: $3 < 8$, идём влево от корня, там пусто — $3$ становится левым ребёнком $8$. Вставляем $10$: $10 > 8$, идём вправо, там пусто — $10$ становится правым ребёнком $8$. Вставляем $1$: $1 < 8$ → влево к $3$; $1 < 3$ → влево от $3$, там пусто — $1$ становится левым ребёнком $3$. Вставляем $6$: $6 < 8$ → влево к $3$; $6 > 3$ → вправо от $3$, там пусто — $6$ становится правым ребёнком $3$. Вставляем $14$: $14 > 8$ → вправо к $10$; $14 > 10$ → вправо от $10$, там пусто — $14$ становится правым ребёнком $10$. Итоговое дерево:

        8
       / \
      3   10
     / \    \
    1   6    14

Пример 2 (средний). В дерево из примера 1 нужно вставить значение $6$ ещё раз (дубликат). Опиши, что произойдёт при использовании функции insert выше, и почему разработчику стоит заранее решить, как поступать с повторами.

При спуске: $6 < 8$ → влево к $3$; $6 > 3$ → вправо к $6$; попадаем в узел со значением, равным вставляемому — по условию elif key > root.val ветка не сработает (значения равны), а условие key < root.val тоже ложно, поэтому дерево вернётся без изменений: дубликат просто игнорируется. Это одно из двух распространённых соглашений; второе — трактовать равные значения как «больше» и всегда отправлять их в правое поддерево, тогда дубликаты будут накапливаться цепочкой справа от исходного узла. Какое соглашение выбрать, зависит от задачи: если BST используется как множество уникальных ключей (как в этом уроке), первое соглашение естественнее; если нужно хранить кратность значений, годится второе, либо в узле хранят счётчик повторений вместо создания дублирующих узлов.

Пример 3 (сложный). Раздели по стоимости операции сценарий, где значения $1, 2, 3, 4, 5$ вставляются по порядку возрастания, и сценарий, где те же значения вставляются в порядке $3, 1, 4, 2, 5$. Опиши получившиеся деревья и сравни высоты.

При вставке по возрастанию $1, 2, 3, 4, 5$ каждое следующее значение больше всех предыдущих, поэтому оно всегда уходит в правое поддерево последнего вставленного узла:

1
 \
  2
   \
    3
     \
      4
       \
        5

Получилось вырожденное дерево высотой $4$ (пять узлов, но структура — фактически связный список). При вставке в порядке $3, 1, 4, 2, 5$: $3$ — корень; $1<3$ — влево; $4>3$ — вправо; $2<3$, затем $2>1$ — правый ребёнок узла $1$; $5>3$, затем $5>4$ — правый ребёнок узла $4$:

      3
     / \
    1   4
     \   \
      2   5

Высота этого дерева равна $2$ — вдвое меньше при том же количестве узлов. Этот пример — прямое предвестие следующего блока урока: порядок вставки одних и тех же значений может радикально изменить высоту получившегося дерева, а значит, и стоимость всех последующих операций поиска, вставки и удаления.

Почему это важно. Вставка — это единственный способ, которым BST растёт, и именно накопленная за много вставок структура определяет, насколько эффективным окажется дерево в дальнейшем. В реальных системах — например, при построении индекса по мере поступления новых записей в базу данных, или при инкрементальном построении структуры для потоковых данных — то, в каком порядке приходят данные, напрямую влияет на производительность всей системы, если использовать наивное BST без последующей балансировки.

Удаление узла: три случая

Интуиция: не разрушить порядок, убирая часть структуры

Удаление — самая тонкая из трёх базовых операций, потому что, в отличие от поиска и вставки, оно должно разорвать часть существующей структуры, аккуратно её «залатав» так, чтобы свойство упорядоченности не пострадало. Сложность удаления зависит от того, сколько детей у удаляемого узла, поэтому его принято разбирать по трём отдельным случаям.

Формула (алгоритм удаления узла $x$).

  1. Узел-лист (нет детей): просто удаляется, указатель родителя на него заменяется на None.
  2. Один ребёнок: узел удаляется, а его единственный ребёнок подключается напрямую к родителю удаляемого узла — ребёнок «занимает место» родителя.
  3. Два ребёнка: находится минимальный элемент правого поддерева узла $x$ (это его ин-ордер преемник — следующее по величине значение после $x$ во всём дереве), значение этого минимума копируется в узел $x$, а затем сам узел-минимум (у которого гарантированно нет левого ребёнка — иначе он не был бы минимумом) удаляется из правого поддерева рекурсивно по одному из случаев 1 или 2.

Время работы удаления составляет $O(h)$: поиск удаляемого узла занимает $O(h)$, поиск минимума правого поддерева (в третьем случае) — тоже не более $O(h)$, а сама операция отсоединения/подключения указателей выполняется за $O(1)$.

Третий случай стоит того, чтобы задержаться на нём отдельно. Почему именно минимум правого поддерева — законная замена удаляемому узлу? Потому что по определению BST все значения правого поддерева больше значения $x$, а все значения левого поддерева меньше $x$. Минимум правого поддерева — это наименьшее из всех значений, которые больше $x$, то есть ближайшее к $x$ значение «сверху». Поставив его на место $x$, ты гарантированно сохраняешь свойство упорядоченности: оно по-прежнему больше всего, что осталось в левом поддереве, и по-прежнему меньше или равно всему, что осталось в правом поддереве (кроме себя самого, которое как раз удаляется). Симметрично работает и альтернативный вариант — заменить удаляемый узел на максимум левого поддерева (ин-ордер предшественник); оба варианта корректны, в этом уроке по историческому соглашению Хиббарда используется вариант с минимумом правого поддерева.

def find_min(node):
    while node.left is not None:
        node = node.left
    return node

def delete(root, key):
    if root is None:
        return None
    if key < root.val:
        root.left = delete(root.left, key)
    elif key > root.val:
        root.right = delete(root.right, key)
    else:
        # нашли узел, который нужно удалить
        if root.left is None:
            return root.right   # случай "лист" (оба None) или "один ребёнок справа"
        if root.right is None:
            return root.left    # случай "один ребёнок слева"
        # случай "два ребёнка"
        successor = find_min(root.right)
        root.val = successor.val
        root.right = delete(root.right, successor.val)
    return root

Примеры с разбором

Пример 1 (лёгкий, лист). В дереве

        8
       / \
      3   10
     / \    \
    1   6    14

удали узел $1$.

Узел $1$ — лист, у него нет детей. Удаление сводится к тому, что указатель left узла $3$, который раньше указывал на $1$, становится None. Дерево после удаления:

        8
       / \
      3   10
       \    \
        6    14

Никакой перестройки, кроме отсоединения одного указателя, не потребовалось — это самый дешёвый случай удаления.

Пример 2 (средний, один ребёнок). В том же дереве удали узел $10$, у которого есть только правый ребёнок $14$ (левого нет).

Поскольку у узла $10$ отсутствует левый ребёнок, по алгоритму if root.left is None: return root.right — узел $10$ заменяется на своего единственного ребёнка $14$: указатель, который раньше вёл от корня $8$ к узлу $10$, теперь ведёт напрямую к узлу $14$. Дерево:

        8
       / \
      3   14
     / \
    1   6

Обрати внимание: свойство BST сохраняется автоматически — всё, что было в поддереве узла $14$ (в данном случае само $14$, детей у него не было), и так было больше $8$ и, разумеется, больше $10$, так что перемещение на место родителя не нарушает никаких ограничений.

Пример 3 (сложный, два ребёнка). В исходном полном дереве

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

удали корень — узел $8$, у которого есть оба ребёнка ($3$ и $10$).

По алгоритму ищем минимум правого поддерева узла $8$ (поддерево с корнем $10$): спускаемся из $10$ максимально влево — у $10$ левого ребёнка нет (у него только правый ребёнок $14$), значит, минимум правого поддерева — это сам узел $10$. Копируем значение $10$ в удаляемый узел (то есть корень теперь хранит значение $10$), а затем удаляем узел со значением $10$ из правого поддерева — а у него как раз только один ребёнок ($14$), так что это удаление сводится к уже разобранному случаю 2: узел $14$ подключается на место бывшего узла $10$. Итоговое дерево:

       10
       / \
      3   14
     / \   /
    1   6 13
       / \
      4   7

Новый корень $10$ по-прежнему больше всех элементов левого поддерева ($3, 1, 6, 4, 7$) и не нарушает порядок относительно единственного оставшегося узла правого поддерева ($14$, у которого теперь в качестве левого ребёнка присоединился узел $13$, перекочевавший туда как единственный ребёнок бывшего узла $10$). Если бы вместо корня удалялся узел с более глубоким правым поддеревом, где у минимума был бы собственный правый ребёнок, процесс происходил бы точно так же — рекурсивный вызов delete(root.right, successor.val) сам разобрался бы с этим на следующем уровне, потому что у минимума поддерева никогда не может быть левого ребёнка (иначе он не был бы минимумом), а значит, его удаление всегда сводится к случаю 1 или случаю 2.

Почему это важно. Три случая удаления — это не искусственная классификация ради упражнения, а отражение того, насколько по-разному приходится «латать» структуру в зависимости от локальной формы дерева вокруг удаляемого узла. Понимание того, что случай с двумя детьми всегда сводится к более простому случаю на следующем уровне рекурсии (потому что у преемника гарантированно нет левого ребёнка), — ключевая деталь, которая делает алгоритм Хиббарда корректным и завершающимся за конечное число шагов, а не бесконечно откладывающим сложность на потом.

Худший и средний случай сложности: от $O(\log n)$ до $O(n)$

Интуиция: всё решает высота, а высота решается порядком вставки

Ты уже видел в примерах выше, что высота BST с одним и тем же набором значений может радикально различаться в зависимости от порядка вставки. Именно высота $h$, а не количество узлов $n$ напрямую, определяет стоимость поиска, вставки и удаления — все три операции работают за $O(h)$. Поэтому центральный вопрос анализа BST — не «сколько узлов в дереве», а «какая у дерева высота при заданном числе узлов».

Формула (границы высоты). Для BST с $n$ узлами высота $h$ удовлетворяет неравенству

$$\lceil \log_2(n+1) \rceil - 1 \;\le\; h \;\le\; n - 1.$$

Нижняя граница достигается на идеально сбалансированном дереве, где на каждом уровне узлы заполнены максимально плотно — тогда $h = O(\log n)$ и все три базовые операции работают за $O(\log n)$. Верхняя граница достигается на вырожденном дереве, где каждый узел имеет не более одного ребёнка — тогда дерево фактически превращается в связный список высотой $n-1$, и операции работают за $O(n)$.

Вырожденное дерево возникает не в экзотических, а в очень бытовых сценариях: если данные вставляются уже отсортированными (или почти отсортированными) — например, монотонно растущие временные метки событий, автоинкрементные идентификаторы, алфавитно упорядоченные имена — каждое новое значение больше (или каждый раз меньше) всех предыдущих, и оно неизбежно уходит на самый дальний уровень одной и той же ветки, будь то правой или левой. В результате структура, задуманная как ускоряющая поиск альтернатива списку, на таких входных данных буквально становится списком, полностью теряя своё преимущество.

Средний случай — отдельная и более тонкая история. Если значения вставляются в случайном порядке (то есть все $n!$ перестановок исходного набора значений равновероятны), ожидаемая высота получившегося BST составляет $O(\log n)$ — точнее, известный результат теории случайных деревьев поиска даёт асимптотику $\mathbb{E}[h] \approx 2\ln n \approx 1{,}39 \log_2 n$. Иными словами, «типичное» дерево, построенное на случайно перемешанных данных, оказывается лишь примерно на $39\%$ выше идеально сбалансированного, а не катастрофически хуже — и именно поэтому в учебниках часто пишут «$O(\log n)$ в среднем случае», имея в виду это усреднение по случайным порядкам вставки, а не гарантию для любых конкретных данных.

Примеры с разбором

Пример 1 (лёгкий). Вставь значения $1, 2, 3, 4, 5, 6, 7$ по возрастанию и определи высоту получившегося дерева, а также число сравнений, нужное для поиска значения $7$.

Каждое следующее значение больше всех предыдущих, поэтому дерево вырождается в цепочку, уходящую вправо:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           \
            7

Высота дерева равна $6$ (семь узлов, каждый уровень — один узел). Поиск значения $7$ требует спуска через все $7$ узлов — столько же сравнений, сколько потребовал бы линейный перебор в обычном списке. BST здесь не даёт вообще никакого преимущества перед списком.

Пример 2 (средний). Вставь те же семь значений в порядке $4, 2, 6, 1, 3, 5, 7$ и определи высоту получившегося дерева.

Строим дерево: $4$ — корень; $2 < 4$ — влево; $6 > 4$ — вправо; $1<4$, $1<2$ — левый ребёнок узла $2$; $3<4$, $3>2$ — правый ребёнок узла $2$; $5>4$, $5<6$ — левый ребёнок узла $6$; $7>4$, $7>6$ — правый ребёнок узла $6$:

        4
       / \
      2   6
     / \ / \
    1  3 5  7

Дерево получилось идеально сбалансированным: высота равна $2$ вместо $6$ из примера 1 — при тех же семи значениях. Поиск любого из семи значений теперь требует не более $3$ сравнений вместо возможных $7$. Этот пример наглядно показывает, что дело не в самих значениях, а исключительно в порядке, в котором они поступили на вставку.

Пример 3 (сложный). Оцени, сколько сравнений потребуется для поиска в худшем и в среднем случае при $n = 10^6$ элементов, и сравни это с линейным перебором.

При вырожденном дереве (худший случай) высота $h = n - 1 = 999\,999$, то есть в худшем случае поиск может потребовать почти миллион сравнений — практически столько же, сколько линейный перебор по несортированному списку. При идеально сбалансированном дереве высота $h \approx \log_2(10^6) \approx 19{,}93$, то есть не более $20$ сравнений. При случайном порядке вставки ожидаемая высота $\approx 1{,}39 \cdot 19{,}93 \approx 27{,}7$, то есть в среднем около $28$ сравнений — всё ещё на пять порядков быстрее, чем миллион сравнений худшего случая. Разница между $O(\log n)$ и $O(n)$ при $n = 10^6$ — это разница между «мгновенно» и «заметно медленно», и именно эта пропасть объясняет, почему инженеры баз данных и разработчики библиотек структур данных прикладывают столько усилий, чтобы гарантировать логарифмическую высоту, а не полагаться на удачный порядок вставки или статистическую случайность входных данных.

Почему это важно. Именно этот разрыв между средним и худшим случаем — главный практический недостаток «наивного» BST и главный мотив для следующего урока. Полагаться на то, что реальные входные данные «в среднем» будут перемешаны случайно, опасно: злоумышленник, зная алгоритм, может специально подать отсортированные данные, чтобы намеренно замедлить систему (это реальный класс атак на алгоритмическую сложность), а обычные, ничем не злонамеренные датасеты — та же монотонно растущая временная метка — вызывают вырождение без всякого злого умысла. Самобалансирующиеся деревья (AVL-деревья, красно-чёрные деревья), с которыми ты познакомишься в уроке 258, решают эту проблему, гарантируя $O(\log n)$ высоту в любом случае, а не только в среднем, за счёт дополнительных операций перебалансировки при каждой вставке и удалении.

Симметричный обход: как получить отсортированную последовательность

Интуиция: пройти дерево так же, как ты читал бы отсортированный список

Одно из самых красивых и практически полезных свойств BST — то, что оно «бесплатно» умеет выдавать все свои элементы в отсортированном порядке. Для этого используется симметричный обход дерева: рекурсивно обойти левое поддерево, затем посетить сам узел, затем рекурсивно обойти правое поддерево. Поскольку в BST левое поддерево всегда содержит меньшие значения, а правое — большие, такой порядок обхода автоматически выстраивает все значения по возрастанию, без единой дополнительной операции сравнения сверх тех, что уже были потрачены при построении дерева.

Формула (симметричный обход). Для узла node симметричный обход определяется рекурсивно:

$$\text{inorder}(\text{node}) = \text{inorder}(\text{node.left}) \;\Vert\; [\text{node.val}] \;\Vert\; \text{inorder}(\text{node.right}),$$

где $\Vert$ обозначает конкатенацию списков, а $\text{inorder}(\text{None}) = []$ (пустой список — база рекурсии). Время работы обхода составляет $O(n)$: каждый из $n$ узлов посещается и обрабатывается ровно один раз, независимо от высоты дерева.

Обрати внимание на отличие от поиска, вставки и удаления: те работают за $O(h)$, потому что затрагивают лишь один путь от корня вниз. Обход же обязан посетить каждый узел хотя бы раз, поэтому его сложность всегда $O(n)$ — вне зависимости от того, сбалансировано дерево или вырождено. Это единственная из рассмотренных в этом уроке операций, чья сложность не зависит от формы дерева, а только от числа его элементов.

def inorder(root, result=None):
    if result is None:
        result = []
    if root is not None:
        inorder(root.left, result)
        result.append(root.val)
        inorder(root.right, result)
    return result

Примеры с разбором

Пример 1 (лёгкий). Выполни симметричный обход дерева

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

и убедись, что результат отсортирован.

Рекурсия спускается в самое левое поддерево первой: от $8$ идём влево к $3$, от $3$ — влево к $1$, у $1$ левого ребёнка нет, значит, посещаем сам узел $1$ (первый элемент результата), у него нет правого ребёнка, возвращаемся к $3$ — посещаем $3$ (второй элемент), идём в правое поддерево $3$, то есть к узлу $6$: сначала его левый ребёнок $4$ (третий элемент), затем сам $6$ (четвёртый), затем его правый ребёнок $7$ (пятый). Возвращаемся к корню $8$ — посещаем сам корень (шестой элемент). Идём в правое поддерево корня, узел $10$: левого ребёнка нет, посещаем сам $10$ (седьмой), идём вправо к $14$: сначала его левый ребёнок $13$ (восьмой), затем сам $14$ (девятый). Итоговая последовательность: $[1, 3, 4, 6, 7, 8, 10, 13, 14]$ — строго возрастающая, как и ожидалось, при том что структура дерева заранее не была никак «подсказана» этому алгоритму, кроме самого свойства упорядоченности BST.

Пример 2 (средний). Используй симметричный обход, чтобы проверить, является ли дерево корректным BST — как альтернативу функции с диапазонами (low, high) из первого блока урока.

Идея: выполнить inorder-обход и убедиться, что получившаяся последовательность строго возрастает (без повторов, если дубликаты запрещены). Если хотя бы одно значение в последовательности не больше предыдущего — дерево нарушает свойство BST.

def is_valid_bst_inorder(root):
    values = inorder(root)
    return all(values[i] < values[i+1] for i in range(len(values) - 1))

Для дерева из «Примера 3» первого блока урока (узел $9$, ошибочно стоящий слева от $8$, хотя и меньше корня $10$) симметричный обход выдаст последовательность $[2, 5, 9, 8, 10, 12, 15, 20]$ — и сразу видно, что $9$ стоит перед $8$, хотя должно быть наоборот, поскольку $9 > 8$: условие строгого возрастания нарушается на этой паре, и функция вернёт False, точно так же, как и подход с диапазонами. Этот способ проверки более лаконичен в коде, но требует $O(n)$ дополнительной памяти на список значений, тогда как подход с диапазонами работает за $O(h)$ дополнительной памяти (глубина стека рекурсии).

Пример 3 (сложный). Используя симметричный обход, найди $k$-й по величине (наименьший) элемент дерева без построения полного отсортированного списка, если известно, что $k$ гораздо меньше $n$.

Наивный способ — построить весь список inorder(root) и взять result[k-1], но это требует обхода всех $n$ узлов, даже если $k$ мало. Эффективнее — остановить обход, как только найден $k$-й элемент, используя счётчик и раннее прерывание:

def kth_smallest(root, k):
    stack = []
    node = root
    count = 0
    while stack or node is not None:
        while node is not None:
            stack.append(node)
            node = node.left
        node = stack.pop()
        count += 1
        if count == k:
            return node.val
        node = node.right
    return None  # k больше числа узлов в дереве

Эта итеративная версия симметричного обхода с явным стеком выполняет ровно столько шагов, сколько нужно, чтобы дойти до $k$-го элемента в порядке возрастания, и останавливается сразу же, не продолжая обход оставшейся части дерева. В худшем случае (если нужен последний, самый большой элемент) она всё равно посетит все $n$ узлов, но в типичном случае, когда $k \ll n$, реальная работа окажется значительно меньше полного обхода — на практике такая задача возникает, например, при вычислении медианы или произвольного перцентиля потока данных, хранящегося в BST.

Почему это важно. Симметричный обход — это не просто способ «вывести дерево на экран»: он лежит в основе целого класса алгоритмов, где нужно работать с данными в отсортированном порядке, не пересортировывая их с нуля каждый раз, — диапазонные запросы («выдай все значения между $a$ и $b$»), нахождение $k$-й порядковой статистики, поиск ближайшего меньшего или большего элемента, слияние нескольких BST в один отсортированный список. Более того, именно строгая монотонность результата симметричного обхода — самый универсальный и часто самый простой способ протестировать корректность реализации BST после вставок и удалений: если после серии операций обход перестал быть строго возрастающим, значит, где-то в логике вставки или удаления закралась ошибка.

Практика: 30 заданий

Базовые (задания 1–10)

Задание 1. Построй BST, вставляя значения в порядке $[5, 2, 8, 1, 3, 7, 9]$, и нарисуй итоговую структуру.

Задание 2. В дереве из задания 1 найди элемент $7$. Сколько сравнений потребуется?

Задание 3. Какую последовательность выведет симметричный обход дерева из задания 1?

Задание 4. Является ли следующее дерево корректным BST?

    10
   /  \
  5    15
 / \   / \
2   7 12  20

Задание 5. Дано пустое дерево. В каком порядке нужно вставить элементы $[1, 2, 3, 4, 5]$, чтобы получившееся дерево было максимально сбалансированным?

Задание 6. Оцени сложность поиска в вырожденном BST, полученном вставкой элементов $[1,2,3,4,5,6,7,8,9,10]$ по возрастанию. Почему это плохо?

Задание 7. Дано BST с $n$ узлами. Опиши идею алгоритма, который находит $k$-й наименьший элемент за $O(h+k)$, где $h$ — высота дерева.

Задание 8. В дереве

    10
   /  \
  5    15
   \
    7

удали узел $5$, у которого только один ребёнок ($7$).

Задание 9. Объясни своими словами, почему недостаточно при проверке BST сравнивать каждый узел только с его непосредственными детьми.

Задание 10. Сформулируй, чем принципиально отличается сложность операции симметричного обхода от сложности операций поиска, вставки и удаления.

Средние (задания 11–20)

Задание 11. В дереве

        8
       / \
      3   10
     / \    \
    1   6    14

удали узел $3$, у которого есть два ребёнка ($1$ и $6$).

Задание 12. Дано BST, построенное вставкой $50, 30, 70, 20, 40, 60, 80$. Найди высоту этого дерева и объясни, почему она минимальна для семи узлов.

Задание 13. Объясни, почему время работы поиска в BST принято записывать как $O(h)$, а не сразу как $O(\log n)$.

Задание 14. Используя итеративный (не рекурсивный) подход со стеком, опиши, как выполнить симметричный обход дерева без рекурсии, и объясни, зачем это может понадобиться.

Задание 15. База данных вставляет записи с автоинкрементным идентификатором ($1, 2, 3, \dots$) в BST-индекс. Объясни, какая проблема возникнет через некоторое время работы системы, и предложи направление решения.

Задание 16. Дан отсортированный массив $[1,2,3,4,5,6,7]$. Опиши рекурсивный алгоритм построения BST минимально возможной высоты из этого массива и оцени его сложность.

Задание 17. В дереве с $n=1000$ узлами известно, что оно построено вставкой значений в случайном порядке. Оцени ожидаемую высоту дерева, используя приближение $\mathbb{E}[h]\approx 1{,}39\log_2 n$, и сравни с высотой идеально сбалансированного дерева.

Задание 18. Объясни, почему при удалении узла с двумя детьми корректно заменять его значение именно минимумом правого поддерева, а не произвольным узлом из правого поддерева.

Задание 19. Докажи, что узел-минимум любого непустого поддерева в BST никогда не имеет левого ребёнка.

Задание 20. Объясни, почему благодаря факту из задания 19 удаление узла с двумя детьми (случай 3) всегда корректно сводится к случаю 1 или случаю 2, а не порождает новый, более сложный случай.

Продвинутые (задания 21–30)

Задание 21. Реализуй функцию, которая находит наименьший элемент, больший заданного значения $x$ (ближайший больший сосед, ceiling), используя структуру BST.

Задание 22. В дереве с $n$ узлами и высотой $h$ оцени, сколько операций в худшем случае потребует последовательность из $m$ вставок подряд в изначально пустое дерево, если все $m$ значений вставляются в возрастающем порядке.

Задание 23. Опиши, как с помощью симметричного обхода двух разных BST можно проверить, что они содержат ровно одинаковый набор значений, даже если структуры деревьев (форма) различаются.

Задание 24. Векторная база данных хранит эмбеддинги товаров и должна быстро находить товары, «похожие» на заданный запрос, по нескольким числовым признакам одновременно (например, цена и рейтинг). Объясни, почему обычное одномерное BST здесь напрямую не подходит, и какая структура обобщает его идею на несколько измерений.

Задание 25. В дереве, построенном вставкой значений $[15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9]$, найди путь поиска (последовательность посещённых узлов) для значения $13$.

Задание 26. В дереве из задания 25 удали узел $6$, у которого есть два ребёнка ($3$ и $7$, причём у $7$ есть собственный правый ребёнок $13$). Опиши результат.

Задание 27. Объясни, почему алгоритм k-NN, использующий KD-дерево для поиска ближайших соседей, теряет эффективность при очень большом числе измерений (десятки и сотни признаков), несмотря на то, что сама идея дерева обобщает BST корректно.

Задание 28. Реализуй функцию подсчёта числа узлов в поддереве, значения которых лежат в диапазоне $[a, b]$, используя свойство упорядоченности BST для отсечения заведомо ненужных поддеревьев.

Задание 29. Рекомендательная система хранит товары, отсортированные по рейтингу, в BST, чтобы быстро выдавать «топ-$k$ товаров с рейтингом выше $x$». Объясни, как сочетание операции из задания 21 (ceiling) и симметричного обхода поможет решить эту задачу эффективно.

Задание 30. Сравни три структуры данных для задачи «хранить $n$ товаров и поддерживать быструю вставку, удаление и диапазонные запросы по рейтингу»: обычный отсортированный массив, обычное BST без балансировки и KD-дерево. Для каждой укажи сильные и слабые стороны применительно к этой одномерной задаче.

Частые ошибки

❌ Ошибка: Считать, что BST всегда работает за $O(\log n)$, независимо от того, как данные были вставлены.

✅ Правильно: Помнить, что реальная сложность всех операций — $O(h)$, и высота $h$ зависит от порядка вставки; при отсортированных или почти отсортированных входных данных дерево вырождается, и сложность становится $O(n)$.

💡 Почему: Логарифмическая оценка справедлива только для сбалансированных или случайно построенных деревьев — это самая частая и самая дорогостоящая ошибка при проектировании систем на BST, включая забывание о вырожденном случае при плохо перемешанных входных данных.

❌ Ошибка: При проверке, является ли дерево корректным BST, сравнивать узел только с его непосредственными детьми, а не со всем допустимым диапазоном значений.

✅ Правильно: Передавать вниз по рекурсии границы (low, high), сужающиеся на каждом шаге, либо проверять строгое возрастание результата симметричного обхода.

💡 Почему: Свойство BST рекурсивно и охватывает весь поддерево, а не только соседний уровень; узел может «локально» выглядеть правильно расположенным относительно родителя, но нарушать порядок относительно более далёких предков.

❌ Ошибка: При удалении узла с одним ребёнком забывать корректно переподключить указатель родителя, оставляя «оборванную» ссылку или теряя целое поддерево.

✅ Правильно: Всегда явно возвращать ребёнка удаляемого узла на место родительского указателя, как это сделано в функции delete этого урока (return root.right или return root.left).

💡 Почему: Ошибка в переподключении указателей не вызывает явного падения программы сразу, но делает часть дерева недостижимой — потерянные узлы будут «висеть» в памяти, а структура тихо станет некорректной.

❌ Ошибка: При удалении узла с двумя детьми заменять его значение случайным узлом правого поддерева, а не именно минимумом.

✅ Правильно: Всегда брать минимум правого поддерева (или симметрично — максимум левого, если выбрано это соглашение), поскольку только он гарантированно сохраняет свойство упорядоченности.

💡 Почему: Любое другое значение правого поддерева может оказаться больше, чем часть оставшихся элементов того же поддерева, что напрямую нарушит инвариант BST после замены.

❌ Ошибка: Не учитывать случай пустого дерева (None) как базовый случай в рекурсивных функциях поиска, вставки, удаления и обхода.

✅ Правильно: Всегда явно проверять root is None в начале рекурсивной функции и возвращать корректное значение по умолчанию (None, пустой список, исходный узел без изменений).

💡 Почему: Базовый случай рекурсии — это не формальность, а условие, без которого рекурсия либо не завершится, либо упадёт с ошибкой обращения к атрибуту None.

❌ Ошибка: Путать среднюю сложность $O(\log n)$ (при случайном порядке вставки) с гарантированной сложностью в худшем случае.

✅ Правильно: Явно указывать, о каком случае идёт речь — среднем или худшем, — и не полагаться на «в среднем всё будет хорошо» в системах, где входные данные могут быть намеренно или случайно неблагоприятными (отсортированными).

💡 Почему: В критичных по производительности или по безопасности системах разница между средним и худшим случаем — это разница между работающей и полностью деградировавшей системой; именно поэтому в продакшене выбирают самобалансирующиеся деревья, а не полагаются на удачу.

Главное запомнить

✅ Свойство BST: для каждого узла всё левое поддерево строго меньше узла, всё правое — строго больше, и это свойство рекурсивно относится ко всему поддереву, а не только к непосредственным детям

✅ Поиск, вставка, удаление работают за $O(h)$, где $h$ — высота дерева, а не за $O(\log n)$ напрямую — логарифмическая оценка верна только при сбалансированности

✅ Вставка — это «неудачный поиск», который вместо возврата пустого результата создаёт новый узел ровно там, где поиск закончился бы неудачей

✅ Удаление разбирается на три случая: лист (удалить напрямую), один ребёнок (подключить ребёнка на место родителя), два ребёнка (заменить значением минимума правого поддерева и рекурсивно удалить этот минимум)

✅ Минимум правого поддерева никогда не имеет левого ребёнка, поэтому удаление в случае двух детей всегда сводится к случаю 1 или 2

✅ Худший случай — вырожденное дерево высотой $n-1$ (например, при вставке уже отсортированных данных), где все операции деградируют до $O(n)$

✅ Средний случай при случайном порядке вставки — ожидаемая высота $\approx 1{,}39\log_2 n$, то есть $O(\log n)$, но без гарантии для конкретных, специально подобранных входных данных

✅ Симметричный обход — левое поддерево → узел → правое поддерево — всегда выдаёт элементы BST в отсортированном порядке за $O(n)$, независимо от формы дерева

✅ KD-дерево обобщает идею BST на несколько измерений, чередуя координату разбиения по уровням — основа быстрого поиска ближайших соседей в k-NN и части векторных баз данных для похожих эмбеддингов

✅ Проблема вырождения решается самобалансирующимися деревьями (AVL, красно-чёрные деревья) — тема следующего урока, гарантирующая $O(\log n)$ высоту в любом случае, а не только в среднем

Связь с темами курса

🔙 Откуда пришли: из урока 256 — общее определение дерева, терминология (корень, лист, высота, поддерево) и классификация видов деревьев, среди которых BST был упомянут как один из видов; из более ранних уроков — рекурсия и указатели, на которых строится вся реализация операций BST

🔜 Куда идём:

  • Сбалансированные деревья (урок 258) — AVL-деревья и красно-чёрные деревья, которые решают главную практическую проблему этого урока: гарантируют $O(\log n)$ высоту при любом порядке вставки, а не только в среднем случае
  • Графы и их обходы (уроки 259–261) — более общая структура, обобщающая деревья, с собственными алгоритмами поиска (DFS, BFS), идейно продолжающими логику спуска по BST
  • Хеш-таблицы (урок 255, уже пройден) — альтернативный подход к быстрому поиску за $O(1)$ в среднем, но без поддержания порядка элементов, которым обладает BST благодаря симметричному обходу

🎯 В машинном обучении: KD-дерево — прямое многомерное обобщение идеи BST, лежащее в основе быстрого поиска $k$ ближайших соседей в алгоритме k-NN (sklearn.neighbors.KDTree) и части индексов приближённого поиска в векторных базах данных, которые обслуживают рекомендательные системы и семантический поиск по эмбеддингам; решающие деревья и построенные на них ансамбли (случайный лес, градиентный бустинг) используют родственную идею рекурсивного разбиения пространства признаков, хотя правило разбиения в узле там выбирается по критерию информативности, а не по значению ключа, как в BST.

Интересные факты

📌 Алгоритм корректного удаления узла с двумя детьми был впервые строго описан Томасом Хиббардом в 1962 году — до этого исследователи явно упоминали лишь операции поиска и вставки, а удаление считалось заметно более сложной, «незакрытой» задачей: неверная реализация легко нарушает свойство упорядоченности или теряет часть узлов дерева.

📌 Ожидаемая высота случайного BST, построенного вставкой $n$ значений в случайном порядке, была строго доказана математически и составляет асимптотически $\approx 2\ln n \approx 1{,}39\log_2 n$ — этот результат из теории случайных деревьев остаётся одним из классических примеров того, как усреднение по всем возможным перестановкам входных данных даёт куда более оптимистичную оценку, чем анализ единственного наихудшего случая.

📌 KD-дерево было предложено Джоном Луисом Бентли в 1975 году именно как способ обобщить одномерный бинарный поиск на многомерные данные для геометрических и графических задач — сегодня та же самая идея используется, например, в scipy.spatial.KDTree и sklearn.neighbors.KDTree для ускорения поиска ближайших соседей во множестве прикладных ML-задач, от классификации методом k-NN до кластеризации.

📌 Идея превращения дерева в отсортированную последовательность лежит в основе алгоритма сортировки treesort (или «сортировка через дерево»): все элементы вставляются в BST по одному, а затем считываются симметричным обходом. В среднем случае это даёт сложность $O(n\log n)$, как у быстрой сортировки, но в худшем случае (при неудачном порядке входных данных и без балансировки) деградирует до $O(n^2)$ — ещё одна иллюстрация того, почему вопрос высоты дерева, разобранный в этом уроке, имеет практические последствия далеко за пределами одной лишь операции поиска.

Лайфхаки и полезные трюки

💡 Перед тем как встраивать BST в реальный проект, задай себе один вопрос: могут ли входные данные прийти в уже отсортированном или почти отсортированном порядке (временные метки, автоинкрементные ID, алфавитный список)? Если да — сразу закладывайся на самобалансирующуюся структуру, а не на голое BST, чтобы не столкнуться с деградацией в проде уже после того, как система набрала объём данных.

💡 При отладке операций вставки и удаления держи под рукой быстрый «санитарный чек»: выполни симметричный обход дерева после серии изменений и проверь, что результат строго возрастает. Если это не так — ошибка гарантированно в логике вставки или удаления, а не где-то ещё, и это самый быстрый способ локализовать баг, не перечитывая весь код заново.

💡 Если задача требует не только поиска, но и быстрого получения диапазона значений («все товары с рейтингом от $4{,}0$ до $4{,}8$»), не строй решение через полный симметричный обход с последующей фильтрацией — используй отсечение поддеревьев по границам диапазона, как в задании 28: это превращает запрос из $O(n)$ в $O(h+k)$, где $k$ — размер самого результата, а не всего дерева.

💡 Когда сравниваешь BST с KD-деревом для конкретной задачи, сначала спроси себя, сколько измерений в данных. Если один — KD-дерево ничего не даст сверх обычного BST (задание 30); если несколько — KD-дерево может резко ускорить поиск, но помни про проклятие размерности (задание 27): при десятках и сотнях признаков стоит сразу присматриваться к приближённым методам поиска соседей, а не рассчитывать на точный KD-дерево-перебор.

💡 Реализуя рекурсивные операции над деревом (поиск, вставка, удаление, обход), сразу пиши базовый случай if root is None: ... первой строкой функции, а не в конце — это не только стилистическая привычка, но и способ не забыть его вовсе, что является одной из самых частых причин падений при работе с деревьями на собеседованиях и в реальном коде.

Бинарное дерево поиска — редкий пример структуры данных, идею которой можно объяснить за одну минуту («левое меньше, правое больше»), но за которой стоит целый пласт содержательных вопросов: как аккуратно вставлять и удалять, не разрушая порядок, почему одна и та же структура может работать и мгновенно, и удручающе медленно в зависимости от истории вставок, и как получить отсортированный результат почти бесплатно благодаря самой форме дерева. Ты теперь умеешь искать, вставлять и удалять в BST, понимаешь разницу между средним и худшим случаем сложности и знаешь, откуда берётся эта разница — а заодно увидел, как та же самая идея, обобщённая на несколько измерений, превращается в KD-дерево и работает внутри алгоритмов поиска ближайших соседей и похожих эмбеддингов. Следующий урок закроет главный практический пробел этого — самобалансирующиеся деревья, которые гарантируют логарифмическую высоту не только «в среднем», а всегда, вне зависимости от того, в каком порядке к дереву придут данные.

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку
💬 Есть вопрос? Спроси бота!