Эквивалентность деревьев общего вида и двоичных деревьев

Модуль "Деревья" • урок 3 из 11 • ~6 минут

Суть урока. К счастью, математически доказано, что любое дерево общего вида можно изоморфно преобразовать в двоичное дерево с помощью концепции LCRS (Left-Child Right-Sibling).
Эквивалентность деревьев общего вида и двоичных деревьев в три шага: связать братьев, убрать лишние связи, повернуть фигуру вправо
Три шага превращают любое дерево общего вида в двоичное

Эквивалентность деревьев общего вида и двоичных деревьев: правило LCRS

Чтобы решить проблему сложного представления, используется концепция LCRS (Left-Child Right-Sibling), что переводится как "Левый сын - Правый брат".

Идея гениально проста. Мы оставляем в узле ровно два указателя (как в обычном двоичном дереве), но меняем их смысловую нагрузку:

  1. Указатель left теперь указывает только на самого первого (старшего) сына.
  2. Указатель right теперь указывает на следующего родного брата на том же уровне.
// Структура точно такая же, как у двоичного дерева, изменился только смысл полей!
struct node {
    int data;
    struct node* first_child; // "Левый сын"
    struct node* next_sibling; // "Правый брат"
};

Алгоритм преобразования

Чтобы визуально и логически превратить дерево общего вида в двоичное дерево, выполните следующие шаги:

  1. В каждом узле соедините линией всех его детей друг с другом (слева направо). Это будут связи "братьев".
  2. В каждом узле удалите все вертикальные связи к детям, кроме самой левой (к первому сыну).
  3. Слегка поверните получившуюся фигуру на 45 градусов вправо, чтобы братские связи (горизонтальные) стали правыми ветвями двоичного дерева, а сыновние связи (вертикальные) - левыми ветвями.
Пример преобразования LCRS: узел A с сыновьями B, C и D переезжает в двоичное дерево
Синие ветви ведут к первому сыну, красные - к следующему брату

На схеме синие ветви идут влево (это указатель first_child), а красные ветви идут вправо (это указатель next_sibling).

Интересный факт: у корня A правый указатель sibling всегда равен NULL, так как у корня дерева нет братьев. Однако, если мы объединяем несколько деревьев в лес (forest), мы можем использовать этот пустой правый указатель корня A, чтобы привязать к нему корень следующего дерева в лесу! Таким образом, любой лес деревьев тоже идеально ложится в одно двоичное дерево.

Коротко: главное

  • Концепция LCRS (Левый сын - Правый брат) позволяет переиспользовать структуру двоичного узла (с 2 указателями).
  • Все алгоритмы (обходы, балансировка), написанные для двоичных деревьев, могут быть применены к любым деревьям, если они преобразованы по правилу LCRS.

Проверьте себя

Чему равен указатель next_sibling у корневого узла дерева, если это единственное дерево (а не лес)?

Как вам урок? Спасибо за отзыв!