Что такое бинарное дерево?

# Бинарное дерево: Полное руководство

Бинарное дерево (Binary Tree) — это фундаментальная структура данных в программировании, особенно важная для Java разработчиков.

Определение

Бинарное дерево — это иерархическая структура данных, где каждый узел (node) имеет максимум двух детей: левого ребенка (left child) и правого ребенка (right child).

Основные термины

        1 (корень / root)
       / \
      2   3 (потомки / children)
     / \
    4   5
   /
  6

Терминология:
- 1 — корневой узел (root node)
- 2, 3 — внутренние узлы (internal nodes)
- 4, 5, 6 — листья (leaf nodes) — нет детей
- 2 — левый потомок узла 1
- 3 — правый потомок узла 1
- 1 — родитель (parent) узла 2 и 3
- Высота дерева — 3 (максимальная глубина)
- Уровень узла 4 — 2 (расстояние от корня)

Представление в Java

Класс Node (узел)

public class TreeNode {
    public int value;              // значение узла
    public TreeNode left;          // левый потомок
    public TreeNode right;         // правый потомок
    
    public TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

Создание бинарного дерева

public class BinaryTree {
    public TreeNode root;
    
    public BinaryTree() {
        root = null;
    }
    
    // Добавление элемента
    public void insert(int value) {
        root = insertRecursive(root, value);
    }
    
    private TreeNode insertRecursive(TreeNode node, int value) {
        if (node == null) {
            return new TreeNode(value);
        }
        
        if (value < node.value) {
            node.left = insertRecursive(node.left, value);
        } else if (value > node.value) {
            node.right = insertRecursive(node.right, value);
        }
        
        return node;
    }
}

// Использование
BinaryTree tree = new BinaryTree();
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.insert(60);
tree.insert(80);

//       50
//      /  \
//    30    70
//   / \    / \
//  20 40  60 80

Типы бинарных деревьев

1. Полное бинарное дерево (Full Binary Tree)

Все узлы имеют либо 0, либо 2 потомков.

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

2. Совершенное бинарное дерево (Perfect Binary Tree)

Все листья находятся на одном уровне, и все внутренние узлы имеют двух потомков.

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

3. Сбалансированное бинарное дерево (Balanced Binary Tree)

Для каждого узла высота левого и правого поддеревьев отличается максимум на 1.

          1
        /   \
       2     3
      / \     \
     4   5     6

4. Бинарное дерево поиска (Binary Search Tree, BST)

Для каждого узла: все значения слева < значение узла < все значения справа

           50
          /  \
        30    70
       / \    / \
      20 40  60 80

Обход деревьев (Tree Traversal)

1. Обход в глубину (DFS — Depth-First Search)

а) Inorder (левый -> корень -> правый)

Для BST дает отсортированный порядок.

public void inorderTraversal(TreeNode node) {
    if (node == null) return;
    
    inorderTraversal(node.left);      // левый
    System.out.print(node.value + " ");  // корень
    inorderTraversal(node.right);     // правый
}

// Для примера выше: 20 30 40 50 60 70 80

б) Preorder (корень -> левый -> правый)

Полезно для копирования дерева.

public void preorderTraversal(TreeNode node) {
    if (node == null) return;
    
    System.out.print(node.value + " ");  // корень
    preorderTraversal(node.left);      // левый
    preorderTraversal(node.right);     // правый
}

// Для примера выше: 50 30 20 40 70 60 80

в) Postorder (левый -> правый -> корень)

Полезно для удаления дерева.

public void postorderTraversal(TreeNode node) {
    if (node == null) return;
    
    postorderTraversal(node.left);      // левый
    postorderTraversal(node.right);     // правый
    System.out.print(node.value + " ");  // корень
}

// Для примера выше: 20 40 30 60 80 70 50

2. Обход в ширину (BFS — Breadth-First Search)

Обход по уровням.

import java.util.Queue;
import java.util.LinkedList;

public void levelOrderTraversal(TreeNode root) {
    if (root == null) return;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.value + " ");
        
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
}

// Для примера выше: 50 30 70 20 40 60 80

Основные операции

Поиск значения

public boolean search(TreeNode node, int value) {
    if (node == null) return false;
    
    if (value == node.value) return true;
    if (value < node.value) return search(node.left, value);
    return search(node.right, value);
}

// Для BST: O(log n) в среднем, O(n) в худшем

Нахождение минимального значения

public int findMin(TreeNode node) {
    if (node == null) throw new IllegalArgumentException();
    
    while (node.left != null) {
        node = node.left;  // идем влево пока можем
    }
    return node.value;
}

Нахождение максимального значения

public int findMax(TreeNode node) {
    if (node == null) throw new IllegalArgumentException();
    
    while (node.right != null) {
        node = node.right;  // идем вправо пока можем
    }
    return node.value;
}

Высота дерева

public int getHeight(TreeNode node) {
    if (node == null) return 0;
    
    int leftHeight = getHeight(node.left);
    int rightHeight = getHeight(node.right);
    
    return Math.max(leftHeight, rightHeight) + 1;
}

Количество узлов

public int countNodes(TreeNode node) {
    if (node == null) return 0;
    
    return 1 + countNodes(node.left) + countNodes(node.right);
}

Удаление узла

public TreeNode delete(TreeNode node, int value) {
    if (node == null) return null;
    
    if (value < node.value) {
        node.left = delete(node.left, value);
    } else if (value > node.value) {
        node.right = delete(node.right, value);
    } else {
        // Узел найден
        
        // Случай 1: нет детей (листовой узел)
        if (node.left == null && node.right == null) {
            return null;
        }
        
        // Случай 2: один ребенок
        if (node.left == null) return node.right;
        if (node.right == null) return node.left;
        
        // Случай 3: два ребенка
        // Найти минимальный в правом поддереве (inorder successor)
        TreeNode minRight = findMinNode(node.right);
        node.value = minRight.value;
        node.right = delete(node.right, minRight.value);
    }
    
    return node;
}

private TreeNode findMinNode(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

Сложность операций

Практические примеры

Пример 1: Проверка, является ли дерево сбалансированным

public boolean isBalanced(TreeNode node) {
    if (node == null) return true;
    
    int leftHeight = getHeight(node.left);
    int rightHeight = getHeight(node.right);
    
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return false;
    }
    
    return isBalanced(node.left) && isBalanced(node.right);
}

Пример 2: LCA (Lowest Common Ancestor)

Найти самого близкого общего предка для двух узлов.

public TreeNode findLCA(TreeNode node, int p, int q) {
    if (node == null) return null;
    
    if (p < node.value && q < node.value) {
        return findLCA(node.left, p, q);  // оба слева
    }
    if (p > node.value && q > node.value) {
        return findLCA(node.right, p, q);  // оба справа
    }
    
    return node;  // один слева, один справа (или равен узлу)
}

Пример 3: Сумма всех узлов

public int sumAll(TreeNode node) {
    if (node == null) return 0;
    
    return node.value + sumAll(node.left) + sumAll(node.right);
}

Использование в Java Collections

// TreeMap использует Red-Black Tree (частный случай BST)
Map<Integer, String> treeMap = new TreeMap<>();
treeMap.put(50, "fifty");
treeMap.put(30, "thirty");
treeMap.put(70, "seventy");
// Итерация будет в отсортированном порядке: 30, 50, 70

// TreeSet тоже использует красно-черное дерево
Set<Integer> treeSet = new TreeSet<>();
treeSet.add(50);
treeSet.add(30);
treeSet.add(70);
// Элементы хранятся отсортированными

Когда использовать бинарные деревья

1. Поиск данных — BST для быстрого поиска
2. Сортированные данные — TreeMap, TreeSet
3. Индексирование — Индексные структуры в БД
4. Выражения — парсинг математических выражений
5. Иерархические данные — файловые системы, DOM в браузере
6. Компрессия — Huffman кодирование

Итог

Бинарное дерево — это мощная структура данных, позволяющая эффективно хранить и искать иерархические данные. BST обеспечивает поиск за O(log n), а различные типы балансировки (AVL, Red-Black) гарантируют оптимальную производительность даже при неправильном входе данных. В Java используются красно-черные деревья в TreeMap и TreeSet для обеспечения стабильной производительности.