How to become an author
Search
Write a publication
Pull to refresh

Бинарные деревья — решение алгоритмических задач, часть 1

Level of difficultyEasy
Reading time7 min
Views14K
Programming*Java*Algorithms*

Есть много статей, в том числе и на хабре, где подробно рассказывается про бинарные деревья как про структуру данных. В этой статье я больше сосредоточусь на подходах к решению алгоритмических задач, где используются бинарные деревья.

Немного теории для общего понимания сути.

Бинарное дерево - это иерархические структура данных, в которой каждый узел имеет не более двух дочерних узлов. Узлы обычно называются правыми и левыми потомками. При этом каждый из потомков, в свою очередь тоже является узлом, который может иметь двух потомков. Если у узла нет потомков, такой узел называют листом.

Бинарное дерево, рис 1.
Бинарное дерево, рис 1.

Не путать бинарное дерево с бинарным деревом поиска. Второе отличается тем, что хранит данные в отсортированном виде и обладает следующими свойствами:

  • Все значения в узлах левого дочернего поддерева меньше значения родительского узла

  • Все значения в узлах правого дочернего поддерева больше значения родительского узла

  • Каждый дочерний узел тоже является бинарным деревом поиска

Бинарное дерево поиска, рис.2
Бинарное дерево поиска, рис.2

Кстати, у меня есть телеграм-канал, где пишу подходы к решениям всяких задачек с LeetCode, там больше разборов конкретных задач, чем здесь, потому что не всегда нужна статья. В общем, если интересно - жду здесь - t.me/crushiteasy :)


Для решения задач на бинарные деревья существует всего два варианта:

  • Обход дерева в глубину (depth-first search, DFS)

  • Обход дерева в ширину (breadth-first search, BFS)


В этой части статьи рассмотрю обход дерева в глубину. Существует три вида обхода в глубину:

  • Прямой обход (NLR)

  • Центрированный обход (LNR)

  • Обратный обход (LRN)

L - левый узел (left), R - правый узел (right), N - родительский узел (node)

Обход дерева в глубину осуществляется двумя способами:

  • Рекурсивный способ

  • Итеративный способ

Преимущества

Недостатки

Рекурсивный подход

1. Простота и читаемость кода:
Код, использующий рекурсию, обычно короче и проще для понимания, особенно при решении задач, связанных с деревьями и графами, где рекурсия естественно отображает структуру данных.

2. Соответствие математическим описаниям:
Рекурсия хорошо соответствует математическим описаниям алгоритмов, таких как обход деревьев.

1. Переполнение стека:
Если глубина рекурсии становится слишком большой (например, при очень высоких или глубоких деревьях), может произойти переполнение стека вызовов (StackOverflowError).

2. Накладные расходы на вызовы функций:
Каждый рекурсивный вызов требует создания новой записи в стеке вызовов, что увеличивает накладные расходы и может замедлить выполнение программы.

3. Ограниченная масштабируемость:
В отличие от итеративного подхода, рекурсивный может быть ограничен максимальной глубиной стека, что делает его менее подходящим для больших данных.

Итеративный подход

1. Контроль над стеком:
В итеративном подходе вы сами управляете стеком (или его эквивалентом, как в случае с ArrayDeque или ArrayList, далее будет про них), что позволяет избежать переполнения стека вызовов и лучше управлять памятью.

2. Более высокая производительность: Итеративные алгоритмы могут быть быстрее, так как отсутствуют накладные расходы на вызов функций и создание новых записей в стеке вызовов.

3. Большая гибкость: Итеративные алгоритмы могут быть более гибкими и позволять более сложные манипуляции с состоянием, что сложно реализовать в рекурсии.

1. Более сложный код и менее наглядный код:
Итеративные решения часто требуют более сложного кода с использованием явных структур данных, что может быть сложнее для понимания и сопровождения.

Сейчас рассмотрим рекурсивный обход дерева в коде на java. Сделаю сразу с отсылкой к задаче на leetcode: https://leetcode.com/problems/binary-tree-preorder-traversal/

Требуется обойти дерево в глубину прямым обходом (NLR) и вернуть последовательность узлов в виде списка.

Алгоритм решения следующий:

  • Проверяем, не является ли текущий узел пустым (null)

  • Добавляем в итоговый список текущий узел

  • Рекурсивно обходим левое поддерево

  • Рекурсивно обходим правое поддерево

На Java код выглядел бы так: 

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList();
    helper(root, result);
    return result;
}

private void helper(TreeNode root, List<Integer> result) {
    if (root != null) {
        result.add(root.val);
        helper(root.left, result);
        helper(root.right, result);
    }
}

Вот тут еще задачки для центрированного и обратного обходов:

Чтобы их решить, нужно просто поменять местами пару строк в алгоритме.

Если дерево слишком глубокое (для современных машинок более 1000 узлов будет тяжеловато), то лучше использовать итеративный подход. Для итерации обычно используется собственный стек вызовов. 

Но давайте перед кодом посмотрим на структуры данных, которые в целом можно использовать для итеративного обхода. Если открыть википедию, там будет рекомендация использовать стэк. Stack в Java является устаревшей структурой данных, вместо него рекомендуют использовать Deque. Преимущества Deque расписаны хорошо в этой статье - https://www.baeldung.com/java-deque-vs-stack

Для решения алгоритмических задач, по факту, никакие преимущества Deque нам не даст. Поэтому если хотите использовать по-старинке Stack - пожалуйста.

Но тут внимание вопрос: почему нельзя использовать обычный ArrayList для хранения?

На практике списки используются значительно чаще, чем очереди. Давайте подумаем, даст ли нам какое-то преимущество использование Deque конкретно в этой задаче, но сначала код (с ArrayList):

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    List<TreeNode> stack = new ArrayList<>();
    stack.add(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.remove(stack.size() - 1);
        result.add(node.val);

        // Добавляем правого ребенка в стек первым, чтобы левый обрабатывался первым
        if (node.right != null) {
            stack.add(node.right);
        }
        if (node.left != null) {
            stack.add(node.left);
        }
    }

    return result;
}

  1. Вставка элементов в конец списка - скорость O(1),  вставка элементов в конец очереди - O(1)

  2. Удаление элементов из конца списка - O(1), удаление элементов из конца очереди - O(1)

В обоих случаях операции, используемые в задаче, выполняются за константное время. Поэтому использование Deque не дает каких-либо преимуществ.

Чтобы не быть голословной, поделюсь результатами замеров (код можно сокращать и рефакторить, да-да, но оставила в таком виде для большей наглядности).

Тут код (раскрой, если интересно)
public static void main(String[] args) {
    for (int i = 0; i < 10; i++) {
        compare(25);
        System.out.println("_______________");
    }
}

private static void compare(int treSize) {
    TreeNode root = generateLargeTree(treSize);
    long start, end;

    // Тест с ArrayDeque
    start = System.currentTimeMillis();
    preorderTraversalWithArrayDeque(root);
    end = System.currentTimeMillis();
    System.out.println("ArrayDeque Time: " + (end - start) + " ms");

    // Тест с ArrayList
    start = System.currentTimeMillis();
    preorderTraversalWithArrayList(root);
    end = System.currentTimeMillis();
    System.out.println("ArrayList Time: " + (end - start) + " ms");

    // Тест с Stack
    start = System.currentTimeMillis();
    preorderTraversalWithStack(root);
    end = System.currentTimeMillis();
    System.out.println("Stack Time: " + (end - start) + " ms");
}

private static List<Integer> preorderTraversalWithArrayList(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    List<TreeNode> stack = new ArrayList<>();
    stack.add(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.remove(stack.size() - 1);
        result.add(node.getVal());

        if (node.getRight() != null) {
            stack.add(node.getRight());
        }
        if (node.getLeft() != null) {
            stack.add(node.getLeft());
        }
    }

    return result;
}

private static List<Integer> preorderTraversalWithArrayDeque(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.getVal());

        if (node.getRight() != null) {
            stack.push(node.getRight());
        }
        if (node.getLeft() != null) {
            stack.push(node.getLeft());
        }
    }

    return result;
}


private static List<Integer> preorderTraversalWithStack(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.getVal());

        if (node.getRight() != null) {
            stack.push(node.getRight());
        }
        if (node.getLeft() != null) {
            stack.push(node.getLeft());
        }
    }

    return result;
}




private static TreeNode generateLargeTree(int depth) {
    if (depth == 0) {
        return null;
    }
    TreeNode root = new TreeNode(depth);
    root.setLeft(generateLargeTree(depth - 1));
    root.setRight(generateLargeTree(depth - 1));
    return root;
}

Прогнала тест с использованием разных структур данных (ArrayList, ArrayDeque, Stack) 10 раз с деревом глубиной 25. 

Лучшую скорость показали:

  • ArrayDeque - 2 раза

  • ArrayList - 6 раз

  • Stack - 2 раза

Результаты замеров тут

ArrayDeque Time: 2845 ms

ArrayList Time: 2231 ms

Stack Time: 4579 ms

_______________

ArrayDeque Time: 4478 ms

ArrayList Time: 1302 ms

Stack Time: 4541 ms

_______________

ArrayDeque Time: 7852 ms

ArrayList Time: 1305 ms

Stack Time: 4655 ms

_______________

ArrayDeque Time: 1537 ms

ArrayList Time: 4346 ms

Stack Time: 3870 ms

_______________

ArrayDeque Time: 4199 ms

ArrayList Time: 3966 ms

Stack Time: 1166 ms

_______________

ArrayDeque Time: 1048 ms

ArrayList Time: 1311 ms

Stack Time: 5988 ms

_______________

ArrayDeque Time: 4349 ms

ArrayList Time: 3924 ms

Stack Time: 1082 ms

_______________

ArrayDeque Time: 1135 ms

ArrayList Time: 1577 ms

Stack Time: 3744 ms

_______________

ArrayDeque Time: 7193 ms

ArrayList Time: 1207 ms

Stack Time: 4070 ms

_______________

ArrayDeque Time: 1188 ms

ArrayList Time: 1124 ms

Stack Time: 4230 ms

_______________

То есть какой-то явной динамики нет, а поэтому можно сделать вывод, что использование любой из структур данный уместно для решения этой алгоритмической задачи.  

Во второй части статьи я рассмотрю второй способ обхода деревьев - BFS (в ширину).

Tags:
Hubs:
Total votes 11: ↑7 and ↓4+4
Comments26
3
Karma
-9
Rating
Алина Козыренко @akozyrenko

Java Developer

Send message

Articles

Your account

Sections

Information

Services

Support
© 2006–2024, Habr