Как определить, сбалансировано ли двоичное дерево в Java

Автор оригинала: baeldung.

1. Обзор

Деревья являются одной из наиболее важных структур данных в области компьютерных наук. Обычно нас интересует сбалансированное дерево из-за его ценных свойств . Их структура позволяет выполнять такие операции, как запросы, вставки, удаления в логаритмическое время.

2. Определения

Во-первых, давайте введем несколько определений, чтобы убедиться, что мы находимся на той же странице:

• Двоичное дерево – своего рода дерево, где каждый узел имеет ноль, один или два ребенка
• Высота дерева – максимальное расстояние от корня до листа (так же, как глубина самого глубокого листа)
• Сбалансированное дерево – это своего рода дерево, на котором для каждого подтрибного максимальное расстояние от корня до любого листа не более чем на один больше, чем минимальное расстояние от корня до любого листа

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

3. Объекты домена

Итак, давайте начнем с класса для нашего дерева:

public class Tree {
    private int value;
    private Tree left;
    private Tree right;

    public Tree(int value, Tree left, Tree right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

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

Прежде чем мы введем наш основной метод давайте посмотрим, что он должен вернуться:

private class Result {
    private boolean isBalanced;
    private int height;

    private Result(boolean isBalanced, int height) {
        this.isBalanced = isBalanced;
        this.height = height;
    }
}

Таким образом, для каждого вызова, мы будем иметь информацию о высоте и балансе.

4. Алгоритм

Имея определение сбалансированного дерева, мы можем придумать алгоритм. Что нам нужно сделать, это проверить желаемое свойство для каждого узла . Это может быть достигнуто легко с рекурсивной глубины первого поиска обхода.

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

Теперь давайте посмотрим на наш метод глубины-первых:

private Result isBalancedRecursive(Tree tree, int depth) {
    if (tree == null) {
        return new Result(true, -1);
    }

    Result leftSubtreeResult = isBalancedRecursive(tree.left(), depth + 1);
    Result rightSubtreeResult = isBalancedRecursive(tree.right(), depth + 1);

    boolean isBalanced = Math.abs(leftSubtreeResult.height - rightSubtreeResult.height) <= 1;
    boolean subtreesAreBalanced = leftSubtreeResult.isBalanced && rightSubtreeResult.isBalanced;
    int height = Math.max(leftSubtreeResult.height, rightSubtreeResult.height) + 1;

    return new Result(isBalanced && subtreesAreBalanced, height);
}

Во-первых, мы должны рассмотреть дело, если наш узел нулевой : Мы вернемся истинное (что означает, что дерево сбалансировано) и -1 в высоту.

Затем, мы делаем два рекурсивных звонка для левого и правого подтри, сохраняя глубину в курсе .

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

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

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

public boolean isBalanced(Tree tree) {
    return isBalancedRecursive(tree, -1).isBalanced;
}

5. Резюме

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

Как обычно, исходный код с тестами доступен более на GitHub .