При каком условии бинарное дерево превращается в бинарный список

Преобразование бинарного дерева в бинарный список

Бинарное дерево превращается в бинарный список (или вырождается) при следующих ключевых условиях:

Основные условия трансформации

Главное условие: Бинарное дерево становится бинарным списком, когда в каждом узле есть максимум одного потомка — либо только левый ребёнок, либо только правый. Такая структура называется вырожденным деревом (skewed tree).

Это может произойти двумя способами:

1. Левостороннее вырождение — каждый узел имеет только левого потомка
2. Правостороннее вырождение — каждый узел имеет только правого потомка

В обоих случаях структура эквивалентна однонаправленному связному списку.

Примеры вырожденного дерева

Правостороннее вырождение (список):

     1
      \
       2
        \
         3
          \
           4

Левостороннее вырождение (список):

     1
    /
   2
  /
 3
/
4

Когда это происходит на практике

• При вставке упорядоченных данных в простое бинарное дерево поиска (BST). Если вставлять отсортированные значения, дерево станет полностью несбалансированным
• При удалении большинства узлов — если удалять узлы так, чтобы осталась только одна линия потомков
• При работе с несбалансированными структурами без механизмов переоснащения

Код проверки вырождения

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public boolean isSkewedTree(TreeNode root) {
    if (root == null) return true;
    
    // Оба потомка существуют — это не вырождение
    if (root.left != null && root.right != null) {
        return false;
    }
    
    // Проверяем поддеревья
    if (root.left != null) {
        return isSkewedTree(root.left);
    }
    
    if (root.right != null) {
        return isSkewedTree(root.right);
    }
    
    return true; // Лист
}

Практические последствия

Когда дерево вырождается в список, теряется главное преимущество дерева:

• Поиск: O(n) вместо O(log n) на сбалансированном дереве
• Вставка: O(n) вместо O(log n)
• Удаление: O(n) вместо O(log n)

Это делает структуру неэффективной для больших объёмов данных.

Решение: балансировка

Для предотвращения вырождения используются самобалансирующиеся деревья:

• AVL-дерево — гарантирует разницу высоты не более 1
• Red-Black дерево — менее строгое, но быстрее в операциях
• B-дерево — для работы с диском

Эти структуры автоматически перестраиваются при вставке/удалении, предотвращая вырождение.