Проверка сбалансированности бинарного дерева

Проверка сбалансированности бинарного дерева

Сбалансированное бинарное дерево (Balanced Binary Tree) — это дерево, в котором для каждого узла разница в глубинах между левым и правым поддеревьями не превышает 1.

Определение структуры узла

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

Основное решение (рекурсивное)

public class BalancedBinaryTree {
    
    /**
     * Проверяет, сбалансировано ли дерево
     * 
     * @param root корень дерева
     * @return true, если дерево сбалансировано
     */
    public static boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }
    
    /**
     * Вычисляет высоту дерева и одновременно проверяет баланс
     * 
     * @param node текущий узел
     * @return высоту дерева или -1 если дерево несбалансировано
     */
    private static int getHeight(TreeNode node) {
        // Базовый случай: пустой узел имеет высоту 0
        if (node == null) {
            return 0;
        }
        
        // Рекурсивно получаем высоты левого и правого поддеревьев
        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);
        
        // Если левое поддерево несбалансировано
        if (leftHeight == -1) {
            return -1;
        }
        
        // Если правое поддерево несбалансировано
        if (rightHeight == -1) {
            return -1;
        }
        
        // Проверяем, сбалансирован ли текущий узел
        // Разница высот не должна быть больше 1
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;  // Несбалансировано
        }
        
        // Возвращаем высоту текущего узла
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

Альтернативное решение с вспомогательным классом

public class BalancedBinaryTreeV2 {
    
    /**
     * Вспомогательный класс для хранения результата
     */
    private static class BalanceInfo {
        int height;
        boolean isBalanced;
        
        BalanceInfo(int height, boolean isBalanced) {
            this.height = height;
            this.isBalanced = isBalanced;
        }
    }
    
    /**
     * Проверяет баланс дерева
     */
    public static boolean isBalanced(TreeNode root) {
        return checkBalance(root).isBalanced;
    }
    
    /**
     * Проверяет баланс и вычисляет высоту
     */
    private static BalanceInfo checkBalance(TreeNode node) {
        // Пустой узел
        if (node == null) {
            return new BalanceInfo(0, true);
        }
        
        // Проверяем левое поддерево
        BalanceInfo leftInfo = checkBalance(node.left);
        if (!leftInfo.isBalanced) {
            return new BalanceInfo(0, false);
        }
        
        // Проверяем правое поддерево
        BalanceInfo rightInfo = checkBalance(node.right);
        if (!rightInfo.isBalanced) {
            return new BalanceInfo(0, false);
        }
        
        // Проверяем баланс текущего узла
        int heightDifference = Math.abs(leftInfo.height - rightInfo.height);
        boolean isBalanced = heightDifference <= 1;
        
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        
        return new BalanceInfo(height, isBalanced);
    }
}

Наивное решение O(n²) — НЕПРАВИЛЬНО!

public class BalancedBinaryTreeNaive {
    
    // НЕПРАВИЛЬНО - O(n²) сложность!
    public static boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        // Вычисляем высоту для каждого узла (O(n) операций)
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        
        // Проверяем каждый узел в обоих поддеревьях (O(n))
        return Math.abs(leftHeight - rightHeight) <= 1 &&
               isBalanced(root.left) &&      // Пересчитываем высоты снова!
               isBalanced(root.right);       // Пересчитываем высоты снова!
    }
    
    private static int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return Math.max(getHeight(node.left), 
                       getHeight(node.right)) + 1;
    }
}

Тестирование

public class Main {
    public static void main(String[] args) {
        // Пример 1: Сбалансированное дерево
        //     3
        //    / \
        //   9  20
        //     /  \
        //    15   7
        TreeNode root1 = new TreeNode(3);
        root1.left = new TreeNode(9);
        root1.right = new TreeNode(20);
        root1.right.left = new TreeNode(15);
        root1.right.right = new TreeNode(7);
        
        System.out.println("Test 1: " + BalancedBinaryTree.isBalanced(root1)); // true
        
        // Пример 2: Несбалансированное дерево
        //        1
        //       / \
        //      2   2
        //     /
        //    3
        //   /
        //  4
        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.right = new TreeNode(2);
        root2.left.left = new TreeNode(3);
        root2.left.left.left = new TreeNode(4);
        
        System.out.println("Test 2: " + BalancedBinaryTree.isBalanced(root2)); // false
        
        // Пример 3: Пустое дерево
        System.out.println("Test 3: " + BalancedBinaryTree.isBalanced(null)); // true
        
        // Пример 4: Один узел
        TreeNode root3 = new TreeNode(1);
        System.out.println("Test 4: " + BalancedBinaryTree.isBalanced(root3)); // true
        
        // Пример 5: Линейное дерево (несбалансировано)
        //    1
        //     \
        //      2
        //       \
        //        3
        TreeNode root4 = new TreeNode(1);
        root4.right = new TreeNode(2);
        root4.right.right = new TreeNode(3);
        
        System.out.println("Test 5: " + BalancedBinaryTree.isBalanced(root4)); // false
    }
}

Визуализация алгоритма

Сбалансированное дерево:

       3           height=2, isBalanced=true
      / \
     9   20        heights: 9=1, 20=2, diff=1 ✓
    / \  / \
       15  7      All nodes balanced

Несбалансированное дерево:

         1                height=-1, isBalanced=false
        / \
       2   2             Node 2 (left): height=3
      /                  Node 2 (right): height=1
     3                   diff=2 > 1 ✗
    /
   4

Анализ сложности

Оптимальное решение (getHeight с проверкой):

Временная сложность: O(n)
- Посещаем каждый узел один раз
- Для каждого узла делаем O(1) операций
- Всего: O(n)

Пространственная сложность: O(h)
- h — высота дерева (глубина рекурсии)
- В худшем случае (линейное дерево): O(n)
- В среднем случае (сбалансированное): O(log n)

Наивное решение (НЕПРАВИЛЬНО):

Временная сложность: O(n²)
- Для каждого узла вычисляем высоту всех узлов в поддеревьях
- T(n) = T(n-1) + n = O(n²)

Это делает решение неэффективным для больших деревьев

Сравнение подходов

// Подход 1: Возвращаем -1 (простой и эффективный)
// ✅ O(n) время
// ✅ Интуитивно понятен
// ✅ Часто используется на интервью

// Подход 2: Вспомогательный класс (более явный)
// ✅ O(n) время
// ✅ Понятный код с ясными намерениями
// ⚠️ Немного больше памяти (объекты BalanceInfo)

// Подход 3: Наивный (НЕПРАВИЛЬНО!)
// ❌ O(n²) время — слишком медленно
// ❌ Пересчитываем одно и то же

Определения

• Высота узла — количество рёбер до самого глубокого листа

  • Высота листа = 0
  • Высота null = 0

• Баланс узла — разница высот левого и правого поддеревьев

  • Баланс может быть -1, 0 или 1 (для сбалансированного)

• Сбалансированное дерево — дерево высотой O(log n) вместо O(n)

  • Важно для производительности операций поиска

Практическое применение

• AVL Trees — самобалансирующиеся деревья поиска
• Red-Black Trees — используются в TreeMap/TreeSet в Java
• B-Trees — используются в базах данных

Ключевые моменты

1. Одноходовое решение — вычисляем высоту и проверяем баланс одновременно
2. Возврат -1 — элегантный способ сигнализировать о дисбалансе
3. Ранний выход — если поддерево дисбалансировано, не проверяем остальное
4. O(n) сложность — критично для больших деревьев
5. Рекурсия — естественный способ обхода дерева

Это классическая задача для проверки понимания деревьев и рекурсии на интервью.