«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. Алгоритм
Имея определение сбалансированного дерева, мы можем придумать алгоритм. Что нам нужно сделать, так это проверить желаемое свойство для каждого узла. Это может быть легко достигнуто с помощью рекурсивного обхода поиска в глубину.
Теперь наш рекурсивный метод будет вызываться для каждого узла. Кроме того, он будет отслеживать текущую глубину. Каждый вызов будет возвращать информацию о высоте и балансе.
Теперь давайте посмотрим на наш метод поиска в глубину:
Во-первых, нам нужно рассмотреть случай, когда наш узел равен нулю: мы вернем true (что означает, что дерево сбалансировано) и -1 как высота.
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);
}
Затем мы делаем два рекурсивных вызова для левого и правого поддеревьев, сохраняя актуальность глубины.
На данный момент у нас есть вычисления, выполненные для дочерних элементов текущего узла. Теперь у нас есть все необходимые данные для проверки баланса:
переменная isBalanced проверяет высоту дочерних элементов, а substreesAreBalanced также указывает, сбалансированы ли оба поддеревья
-
Наконец, мы можем вернуть информацию о балансе и высоте. Также было бы неплохо упростить первый рекурсивный вызов методом фасада:
5. Резюме
public boolean isBalanced(Tree tree) {
return isBalancedRecursive(tree, -1).isBalanced;
}
В этой статье мы обсудили, как определить, сбалансировано ли бинарное дерево. Мы объяснили подход поиска в глубину.
Как обычно, исходный код с тестами доступен на GitHub.
«