Удаление из BST: три случая и преемник

Если ты знаешь три случая удаления (лист / один ребёнок / два ребёнка через преемника) и понимаешь, почему преемник - это минимум правого поддерева и почему у него не больше одного ребёнка, листай до «Теперь сам».

Как думаешь, как убрать узел, не порвав дерево

Убрать лист легко - отцепил, и всё. Но что делать с узлом в СЕРЕДИНЕ дерева, у которого висят поддеревья? Просто выкинуть его нельзя: дети осиротеют, связь порвётся. Подтянуть на его место ребёнка? Если ребёнок один - да. А если ДВА, кого из них поднять, и куда денется второй? Нужен элемент, который может занять место удаляемого, НЕ нарушив порядок: он должен быть больше всего левого поддерева и меньше всего правого - ровно как удаляемый. Такой элемент есть, и он единственный «на границе» - ближайший сосед удаляемого по значению. Найти его и поставить на освободившееся место - вот ключ к удалению с двумя детьми.

На что это похоже

Начальник отдела уходит, а отдел остаётся - и слева подчинённые «поменьше», справа «побольше». Нельзя посадить в кресло случайного человека: новый начальник должен быть таким, чтобы все левые по-прежнему были «меньше» его, а все правые «больше». Идеальный кандидат - самый младший из «старших», то есть наименьший из правого крыла: он только-только больше ушедшего, значит по-прежнему больше всех левых и меньше всех остальных правых. Его повышают, а его прежнее (мелкое) место освобождается легко - под ним почти никого. Дерево поиска увольняет узлы ровно так: на место ушедшего - ближайшего большего.

Механизм: три случая

удалить(x):
    найти узел с ключом x спуском от корня
    СЛУЧАЙ 1 - лист (нет детей):
        отцепить узел от родителя (поставить пустую ссылку)
    СЛУЧАЙ 2 - один ребёнок:
        подставить этого ребёнка на место узла у родителя
    СЛУЧАЙ 3 - два ребёнка:
        найти ПРЕЕМНИКА s = минимум правого поддерева (иди вправо, потом всё влево)
        скопировать ключ s в удаляемый узел
        удалить узел s из правого поддерева   (у него нет левого ребёнка → случай 1 или 2)

Почему преемник - это МИНИМУМ правого поддерева: правое поддерево - все ключи больше x, а их минимум - ближайший больший к x. Поставив его на место x, мы сохраняем инвариант: он больше всего левого поддерева (> x > всё левое) и меньше остального правого (он там был наименьшим). И у преемника ГАРАНТИРОВАННО нет левого ребёнка - иначе тот был бы ещё меньше, и минимумом был бы он. Значит удаление преемника - это лёгкий случай 1 или 2. (Симметрично можно брать ПРЕДШЕСТВЕННИКА - максимум левого поддерева; результат столь же корректен.)

Правило

Удаление узла из BST - три случая. ЛИСТ: отцепить. ОДИН ребёнок: подставить ребёнка на место узла. ДВА ребёнка: заменить ключ узла на ПРЕЕМНИКА (минимум правого поддерева - ближайший больший ключ), затем удалить преемник из правого поддерева (у него нет левого ребёнка, поэтому это лёгкий случай 1 или 2). Всё удаление - спуск по одному пути, O(h). Преемник сохраняет инвариант, потому что он больше всего левого поддерева и меньше остального правого.

Разбор: почему нельзя просто поднять любого ребёнка при двух детях

Соблазн: удаляем узел с двумя детьми - поднимем, скажем, левого ребёнка на его место. Разберём, почему это ломает дерево. Удаляем 8 (левый ребёнок 3, правый 12). Поднимем 3 на место 8. Но у 8 было ПРАВОЕ поддерево (с 12, 10, 14) - куда его девать? Подвесить к 3 справа? Нельзя: у 3 своё правое поддерево может уже быть. Корректно подвесить его к МАКСИМУМУ левого поддерева (все ключи там меньше 8, а правые - больше) - инвариант сохранится, но дерево вытянется: мы приклеили целое поддерево на самое дно, и высота растёт на его высоту. Приём с преемником изящнее: он НЕ двигает поддеревья, а лишь ПОДМЕНЯЕТ один ключ на соседний по значению - структура почти не меняется, удаляется только один лёгкий узел. Поэтому именно преемник (или предшественник), а не произвольный ребёнок.

Разбор: почему у преемника нет левого ребёнка

Это то, что делает третий случай сводимым к первым двум. Преемник - минимум правого поддерева, а минимум мы находим, идя от корня правого поддерева ВСЁ ВРЕМЯ ВЛЕВО, пока лево не кончится. Значит у найденного узла левой ссылки НЕТ (иначе там был бы ключ ещё меньше, и это он был бы минимумом). Правый ребёнок у преемника быть может - и тогда его удаление это случай 2 (подставить правого ребёнка). Но левого точно нет - поэтому удаление преемника никогда не порождает снова «трудный» случай двух детей. Рекурсии вглубь не будет: один спуск за преемником, один лёгкий съём - и всё. Именно поэтому три случая замкнуты, а не бесконечно вложены.

Что ломается без этого

Первая ошибка - при удалении узла с двумя детьми поднять произвольного ребёнка: осиротеет второе поддерево, и либо потеряются данные, либо раздуется высота. Нужен преемник или предшественник. Вторая - взять «преемником» не минимум правого поддерева, а, скажем, правого ребёнка: если у того есть левое поддерево, инвариант нарушится (там ключи меньше подставленного). Строго минимум правого поддерева. Третья - забыть удалить СТАРЫЙ узел преемника после копирования его ключа: ключ окажется в дереве дважды. Четвёртая - при удалении листа или узла с одним ребёнком не обновить ссылку у РОДИТЕЛЯ (а только у самого узла): узел останется висеть, дерево не изменится.

Зачем это в работе

Удаление замыкает набор операций упорядоченного множества: теперь дерево умеет и добавлять, и искать, и убирать - всё за O(h). Без корректного удаления структура была бы «только на дозапись», а реальные словари и множества (std::map, TreeMap) обязаны удалять. Приём с преемником - классический и переносится дальше: в красно-чёрных деревьях и B-деревьях удаление устроено на той же идее (найти преемник, подменить, убрать лёгкий узел), только с добавочной перебалансировкой. Понимать три случая - значит понимать, почему удаление всегда сводится к удалению узла максимум с одним ребёнком, и почему даже самая «страшная» операция дерева стоит всего один спуск O(h). А ещё это первый намёк на то, что сама по себе высота h и есть цена всего - и если она вырастает до n (следующие уроки), удаление, как и всё остальное, деградирует.

Теперь сам

В дереве корень 20, слева 10, справа 30; у 30 левый ребёнок 25, правый 40. Удаляем 30 (два ребёнка). Кто станет на его место и почему? Что произойдёт с прежним узлом этого ключа?