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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

private void helper(TreeNode root, List 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 preorderTraversal(TreeNode root) {
    List result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    List 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 preorderTraversalWithArrayList(TreeNode root) {
    List result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    List 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 preorderTraversalWithArrayDeque(TreeNode root) {
    List result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    Deque 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 preorderTraversalWithStack(TreeNode root) {
    List result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    Stack 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 раза

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

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

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

© Habrahabr.ru