Какие сложности вставки/записи у структуры дерева

Сложности вставки и удаления в структуре дерева

Деревья - одна из основных структур данных. Давай разберём сложности операций вставки и удаления в разных типах деревьев.

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

Структура:

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

Вставка:

public class BinarySearchTree {
    private Node root;
    
    public void insert(int value) {
        root = insertRecursive(root, value);
    }
    
    private Node insertRecursive(Node node, int value) {
        if (node == null) {
            return new Node(value);  // O(1) - создал новый узел
        }
        
        if (value < node.value) {
            node.left = insertRecursive(node.left, value);  // Идём влево
        } else {
            node.right = insertRecursive(node.right, value);  // Идём вправо
        }
        
        return node;
    }
}

Сложность вставки в BST:

• Best case (идеальное дерево): O(log n) - сбалансированное дерево
• Average case: O(log n)
• Worst case: O(n) - если дерево деградировало в список

Идеальное дерево (O(log n)):
        5
       / \
      3   7
     / \ / \
    2  4 6  8
Высота = 3, элементов = 8. log(8) = 3

Дегради в список (O(n)):
    1
     \
      2
       \
        3
         \
          4
Высота = 4, элементов = 4. 4 ≈ n

Проблемы BST: ❌ Может деградировать если вставлять отсортированные данные ❌ Нет гарантии O(log n) ❌ Сложная операция удаления

Удаление из BST:

public void delete(int value) {
    root = deleteRecursive(root, value);
}

private Node deleteRecursive(Node node, int value) {
    if (node == null) {
        return null;
    }
    
    if (value < node.value) {
        node.left = deleteRecursive(node.left, value);
    } else if (value > node.value) {
        node.right = deleteRecursive(node.right, value);
    } else {
        // Нашли узел для удаления
        
        // Случай 1: Нет детей (листовой узел)
        if (node.left == null && node.right == null) {
            return null;  // O(1)
        }
        
        // Случай 2: Один ребёнок
        if (node.left == null) {
            return node.right;  // O(1)
        }
        if (node.right == null) {
            return node.left;  // O(1)
        }
        
        // Случай 3: Два ребёнка (сложный случай!)
        // Найти inorder successor (минимум в правом поддереве)
        Node minRight = findMin(node.right);  // O(h)
        node.value = minRight.value;
        node.right = deleteRecursive(node.right, minRight.value);  // O(h)
    }
    
    return node;
}

private Node findMin(Node node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;  // O(h)
}

Сложность удаления в BST:

• O(log n) - в сбалансированном дереве
• O(n) - в худшем случае если дерево деградировало

2. AVL Tree - Самобалансирующееся дерево

AVL дерево всегда остаётся сбалансированным используя ротации.

АВЛ дерево:
       5(bf:0)
       /   \
    3(bf:0) 7(bf:0)  
    /  \    /  \
   2   4   6    8

bf (balance factor) = height(left) - height(right)
Ограничение: bf ∈ {-1, 0, 1}

Вставка в AVL:

public class AVLTree {
    public void insert(int value) {
        root = insertRecursive(root, value);
    }
    
    private Node insertRecursive(Node node, int value) {
        if (node == null) {
            return new Node(value);  // O(1)
        }
        
        if (value < node.value) {
            node.left = insertRecursive(node.left, value);
        } else {
            node.right = insertRecursive(node.right, value);
        }
        
        // Обновляем высоту
        node.height = 1 + Math.max(height(node.left), height(node.right));  // O(1)
        
        // Проверяем баланс
        int balanceFactor = height(node.left) - height(node.right);
        
        // Случай 1: Left-Left
        if (balanceFactor > 1 && value < node.left.value) {
            return rotateRight(node);  // O(1)
        }
        
        // Случай 2: Right-Right
        if (balanceFactor < -1 && value > node.right.value) {
            return rotateLeft(node);  // O(1)
        }
        
        // Случай 3: Left-Right
        if (balanceFactor > 1 && value > node.left.value) {
            node.left = rotateLeft(node.left);
            return rotateRight(node);
        }
        
        // Случай 4: Right-Left
        if (balanceFactor < -1 && value < node.right.value) {
            node.right = rotateRight(node.right);
            return rotateLeft(node);
        }
        
        return node;
    }
    
    private Node rotateRight(Node y) {
        Node x = y.left;  // O(1)
        y.left = x.right;  // O(1)
        x.right = y;  // O(1)
        
        y.height = 1 + Math.max(height(y.left), height(y.right));
        x.height = 1 + Math.max(height(x.left), height(x.right));
        
        return x;
    }
    
    private Node rotateLeft(Node x) {
        Node y = x.right;  // O(1)
        x.right = y.left;  // O(1)
        y.left = x;  // O(1)
        
        x.height = 1 + Math.max(height(x.left), height(x.right));
        y.height = 1 + Math.max(height(y.left), height(y.right));
        
        return y;
    }
}

Сложность вставки в AVL:

• O(log n) - гарантировано! Даже в худшем случае

Почему? Потому что высота AVL дерева всегда остаётся log(n).

Преимущества AVL: ✅ Гарантированная O(log n) для вставки, удаления, поиска ✅ Хорошо для частых поисков

Недостатки AVL: ❌ Много ротаций может замедлить вставку ❌ Более сложный код

3. Red-Black Tree - Красно-чёрное дерево

Красно-чёрное дерево использует цвета и правила баланса вместо высот.

Регулировки:
1. Каждый узел красный или чёрный
2. Корень чёрный
3. Листья (NIL) чёрные
4. Красный узел имеет чёрных детей
5. Все пути от узла к листьям имеют одинаковое количество чёрных узлов

Вставка в Red-Black Tree:

public class RedBlackTree {
    private static final boolean RED = true;
    private static final boolean BLACK = false;
    
    public void insert(int value) {
        Node newNode = new Node(value, RED);  // O(1)
        root = insertRecursive(root, newNode);  // O(log n) поиск
        fixInsert(newNode);  // O(log n) балансировка
    }
    
    private Node insertRecursive(Node node, Node newNode) {
        if (node == null) {
            return newNode;
        }
        
        if (newNode.value < node.value) {
            node.left = insertRecursive(node.left, newNode);
            newNode.parent = node;
        } else {
            node.right = insertRecursive(node.right, newNode);
            newNode.parent = node;
        }
        
        return node;
    }
    
    private void fixInsert(Node node) {
        while (node.parent != null && node.parent.color == RED) {  // O(log n)
            if (node.parent == node.parent.parent.left) {
                Node uncle = node.parent.parent.right;
                
                if (uncle != null && uncle.color == RED) {
                    // Случай 1: Дядя красный
                    node.parent.color = BLACK;
                    uncle.color = BLACK;
                    node.parent.parent.color = RED;
                    node = node.parent.parent;
                } else {
                    // Случай 2-3: Дядя чёрный, нужна ротация
                    if (node == node.parent.right) {
                        node = node.parent;
                        rotateLeft(node);  // O(1)
                    }
                    node.parent.color = BLACK;
                    node.parent.parent.color = RED;
                    rotateRight(node.parent.parent);  // O(1)
                }
            } else {
                // Зеркальный случай
                // ...
            }
        }
        root.color = BLACK;
    }
}

Сложность вставки в Red-Black:

• O(log n) - гарантировано

Преимущества Red-Black: ✅ O(log n) гарантированно ✅ Меньше ротаций чем AVL (быстрее вставка) ✅ Используется в практике (HashMap, TreeMap в Java)

Недостатки: ❌ Сложнее понять и реализовать ❌ Немного медленнее на поиск чем AVL

4. B-Tree - Дерево многих разветвлений

B-дерево используется в БД для минимизации дисковых операций.

B-дерево порядка 3 (max 3 ключа в узле):

        [30, 70]
       /    |    \
    [10]  [40,50] [80,90]

Вставка в B-Tree:

public class BTree {
    private static final int ORDER = 3;  // Max ключи = ORDER - 1
    
    public void insert(int value) {
        if (root.size() == 2 * ORDER - 1) {  // O(1)
            // Корень полон, создаём новый
            Node newRoot = new Node();  // O(1)
            newRoot.children.add(root);  // O(1)
            splitChild(newRoot, 0);  // O(ORDER)
            root = newRoot;
        }
        insertNonFull(root, value);  // O(log n)
    }
    
    private void insertNonFull(Node node, int value) {
        int index = node.keys.size() - 1;  // O(ORDER)
        
        if (node.isLeaf()) {
            // Вставляем в отсортированный порядок
            while (index >= 0 && node.keys.get(index) > value) {  // O(ORDER)
                node.keys.add(index + 1, node.keys.get(index));
                index--;
            }
            node.keys.add(index + 1, value);  // O(1)
        } else {
            // Найти child для спуска
            while (index >= 0 && node.keys.get(index) > value) {  // O(ORDER)
                index--;
            }
            index++;
            
            Node child = node.children.get(index);
            
            if (child.isFull()) {
                splitChild(node, index);  // O(ORDER)
                if (node.keys.get(index) < value) {
                    index++;
                }
            }
            insertNonFull(node.children.get(index), value);
        }
    }
    
    private void splitChild(Node parent, int index) {
        Node fullChild = parent.children.get(index);
        Node newChild = new Node();  // O(1)
        
        // Копируем вторую половину ключей
        for (int i = 0; i < ORDER - 1; i++) {  // O(ORDER)
            newChild.keys.add(fullChild.keys.get(i + ORDER));
        }
        
        // Удаляем вторую половину из fullChild
        fullChild.keys.subList(ORDER, fullChild.keys.size()).clear();  // O(ORDER)
        
        // Поднимаем средний ключ
        parent.keys.add(index, fullChild.keys.get(ORDER - 1));  // O(1)
        parent.children.add(index + 1, newChild);  // O(1)
    }
}

Сложность вставки в B-Tree:

• O(log n) - где n = количество элементов
• На практике O(logB n) где B = порядок дерева

Преимущества B-Tree: ✅ Минимум дисковых операций (важно для БД) ✅ Хорошо для больших наборов данных ✅ Используется в реальных БД (PostgreSQL, MySQL)

Недостатки: ❌ Сложнее реализовать ❌ Медленнее для небольших данных в памяти

Таблица сравнения

Практический совет

Когда использовать:

• BST: Простые случаи, контролируешь данные
• AVL: Часто ищешь, редко вставляешь
• Red-Black: Частые вставки и удаления (используется в Java HashMap, TreeMap)
• B-Tree: Работаешь с БД или огромным объёмом данных

В Java:

// TreeMap использует Red-Black дерево
Map<String, Integer> map = new TreeMap<>();  // Red-Black

// TreeSet тоже
Set<Integer> set = new TreeSet<>();  // Red-Black