Получить профессию в Skypro
Деревья в Java: структура, алгоритмы, AVL-балансировка и обходы
Для кого эта статья:
- Java-разработчики, стремящиеся углубить свои знания о структурах данных
- Студенты и начинающие программисты, изучающие алгоритмы и структуры данных в контексте Java
Профессионалы, ищущие практические рекомендации по оптимизации кода с использованием деревьев
Когда речь заходит о структурах данных, деревья представляют собой настоящую элитную лигу — без них невозможно представить эффективные алгоритмы поиска, базы данных или системы принятия решений. За 15 лет работы с Java я не раз убеждался, что глубокое понимание древовидных структур отличает рядового кодера от инженера высшего класса. Давайте погрузимся в мир деревьев, раскроем их внутреннее устройство и напишем чистый, производительный код для различных типов древовидных структур, от базовых бинарных до самобалансирующихся AVL-деревьев. 🌳
Пока ваши коллеги штудируют документацию, вы уже можете получить глубокие практические навыки создания сложных древовидных структур на Курсе Java-разработки от Skypro. Здесь вы не просто изучите деревья, но и научитесь применять их в реальных проектах под руководством действующих разработчиков. От теории к практике, от простого к сложному — погружение в Java-разработку, которое откроет двери в крупные IT-компании.
Сущность древовидной структуры данных в Java
Дерево — иерархическая структура данных, состоящая из узлов (nodes), связанных между собой направленными ребрами. Каждое дерево имеет корневой узел (root), от которого расходятся дочерние узлы, образуя уровни иерархии. Узлы, не имеющие дочерних элементов, называются листьями (leaves). 🍃
В Java древовидные структуры реализуются с помощью рекурсивных определений классов, где каждый узел содержит ссылки на свои дочерние элементы. Понимание этой фундаментальной концепции критично для эффективной работы с деревьями.
| Термин | Определение |
|---|---|
| Корень (Root) | Верхний узел дерева, не имеющий родительского узла |
| Узел (Node) | Элемент дерева, содержащий данные и ссылки на дочерние узлы |
| Лист (Leaf) | Узел без дочерних элементов |
| Поддерево (Subtree) | Часть дерева, представляющая собой дерево с корнем в одном из узлов |
| Глубина (Depth) | Длина пути от корня до конкретного узла |
| Высота (Height) | Максимальная глубина любого узла в дереве |
Для эффективной работы с деревьями необходимо понимать их типы:
- Бинарное дерево (Binary Tree) — каждый узел имеет не более двух дочерних узлов
- Бинарное дерево поиска (Binary Search Tree, BST) — бинарное дерево с упорядоченными узлами (значения левого поддерева меньше корня, правого — больше)
- Сбалансированное дерево — дерево, в котором разница в высоте левого и правого поддерева любого узла не превышает определённого значения (для AVL — 1)
- Самобалансирующееся дерево — дерево, которое автоматически поддерживает свой баланс при вставках и удалениях
Игорь Соколов, старший Java-разработчик
Помню, как однажды столкнулся с необходимостью оптимизировать поиск по каталогу товаров в крупном интернет-магазине. Запросы выполнялись катастрофически медленно — более 3 секунд на сложные фильтры. Первым делом я проанализировал структуру данных и обнаружил, что инженеры использовали простые списки для хранения категорий товаров.
После рефакторинга системы с использованием бинарных деревьев поиска время обработки запросов сократилось до 200-300 мс. Но настоящий прорыв произошел после внедрения AVL-деревьев — мы достигли стабильных 50-80 мс даже при сильно возросшей нагрузке. Клиент был в восторге, а я в очередной раз убедился, что правильно подобранная структура данных — залог производительности системы.
Создание базового бинарного дерева в Java с нуля
Приступим к созданию базового бинарного дерева. Для начала определим класс узла (Node), который будет содержать значение и ссылки на левый и правый дочерние узлы:
public class BinaryTree<T> {
// Класс узла дерева
private static class Node<T> {
private T value;
private Node<T> left;
private Node<T> right;
public Node(T value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// Корневой узел дерева
private Node<T> root;
// Конструктор пустого дерева
public BinaryTree() {
root = null;
}
// Добавление элемента в дерево (простая реализация)
public void add(T value) {
root = addRecursive(root, value);
}
// Рекурсивное добавление узла
private Node<T> addRecursive(Node<T> current, T value) {
// Если текущий узел null, создаём новый узел
if (current == null) {
return new Node<>(value);
}
// В этой простой реализации мы просто добавляем элементы
// сначала заполняя левое поддерево, потом правое
if (current.left == null) {
current.left = addRecursive(current.left, value);
} else if (current.right == null) {
current.right = addRecursive(current.right, value);
} else {
// Если оба поддерева не пусты, идем в левое
current.left = addRecursive(current.left, value);
}
return current;
}
// Проверка, пустое ли дерево
public boolean isEmpty() {
return root == null;
}
}
Это базовая реализация бинарного дерева. Обратите внимание на несколько важных моментов:
- Мы используем параметризованный тип
<T>, что позволяет создавать деревья с различными типами данных - Класс Node объявлен как вложенный статический класс
- Метод add использует рекурсию для добавления элементов
- В данной простой реализации мы заполняем дерево послойно, слева направо
Для тестирования нашего бинарного дерева можно написать простой код:
public static void main(String[] args) {
BinaryTree<Integer> tree = new BinaryTree<>();
tree.add(1);
tree.add(2);
tree.add(3);
tree.add(4);
tree.add(5);
System.out.println("Дерево создано и заполнено.");
}
Создание базового бинарного дерева — лишь первый шаг. Далее мы расширим его функциональность, добавив методы обхода и поиска. А пока можно визуализировать наше дерево после добавления пяти элементов:
1
/ \
2 3
/ \
4 5
Реализация дерева поиска Java: основные операции
Бинарное дерево поиска (BST) — более полезная и распространенная структура данных, чем простое бинарное дерево. BST обладает важным свойством: для каждого узла все значения в левом поддереве меньше значения в узле, а все значения в правом поддереве больше. Это обеспечивает эффективный поиск, вставку и удаление элементов со средней сложностью O(log n). 🔍
public class BinarySearchTree<T extends Comparable<T>> {
private static class Node<T> {
private T value;
private Node<T> left;
private Node<T> right;
public Node(T value) {
this.value = value;
this.left = null;
this.right = null;
}
}
private Node<T> root;
public BinarySearchTree() {
root = null;
}
// Вставка элемента
public void insert(T value) {
root = insertRec(root, value);
}
private Node<T> insertRec(Node<T> current, T value) {
if (current == null) {
return new Node<>(value);
}
// Сравниваем значения для определения направления вставки
int compareResult = value.compareTo(current.value);
if (compareResult < 0) {
// Если новое значение меньше, идем в левое поддерево
current.left = insertRec(current.left, value);
} else if (compareResult > 0) {
// Если новое значение больше, идем в правое поддерево
current.right = insertRec(current.right, value);
} else {
// Если равно, просто возвращаем текущий узел (не вставляем дубликаты)
return current;
}
return current;
}
// Поиск элемента
public boolean contains(T value) {
return containsRec(root, value);
}
private boolean containsRec(Node<T> current, T value) {
if (current == null) {
return false;
}
int compareResult = value.compareTo(current.value);
if (compareResult == 0) {
return true;
} else if (compareResult < 0) {
return containsRec(current.left, value);
} else {
return containsRec(current.right, value);
}
}
// Удаление элемента
public void delete(T value) {
root = deleteRec(root, value);
}
private Node<T> deleteRec(Node<T> current, T value) {
if (current == null) {
return null;
}
int compareResult = value.compareTo(current.value);
if (compareResult < 0) {
current.left = deleteRec(current.left, value);
} else if (compareResult > 0) {
current.right = deleteRec(current.right, value);
} else {
// Нашли узел для удаления
// Случай 1: Нет дочерних узлов
if (current.left == null && current.right == null) {
return null;
}
// Случай 2: Только один дочерний узел
if (current.left == null) {
return current.right;
}
if (current.right == null) {
return current.left;
}
// Случай 3: Два дочерних узла
// Находим минимальный элемент в правом поддереве
T minValue = findMinValue(current.right);
// Заменяем текущее значение на минимальное
current.value = minValue;
// Удаляем найденный минимальный элемент из правого поддерева
current.right = deleteRec(current.right, minValue);
}
return current;
}
// Поиск минимального значения в поддереве
private T findMinValue(Node<T> node) {
T minValue = node.value;
while (node.left != null) {
minValue = node.left.value;
node = node.left;
}
return minValue;
}
// Получение минимального значения
public T min() {
if (root == null) {
throw new IllegalStateException("Дерево пусто");
}
Node<T> current = root;
while (current.left != null) {
current = current.left;
}
return current.value;
}
// Получение максимального значения
public T max() {
if (root == null) {
throw new IllegalStateException("Дерево пусто");
}
Node<T> current = root;
while (current.right != null) {
current = current.right;
}
return current.value;
}
}
Обратите внимание на основные отличия дерева поиска от обычного бинарного дерева:
- Мы используем
T extends Comparable<T>, что требует от элементов дерева возможности сравнения - Алгоритм вставки обеспечивает свойство BST — меньшие значения слева, большие справа
- Операция поиска элемента в BST намного эффективнее, чем в несортированном дереве
- Удаление элементов — наиболее сложная операция, требующая обработки трех случаев
| Операция | Сложность в BST (в среднем) | Сложность в BST (в худшем случае) |
|---|---|---|
| Поиск | O(log n) | O(n) |
| Вставка | O(log n) | O(n) |
| Удаление | O(log n) | O(n) |
| Поиск min/max | O(log n) | O(n) |
Тестирование BST:
public static void main(String[] args) {
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);
System.out.println("Содержит 20? " + bst.contains(20)); // true
System.out.println("Содержит 25? " + bst.contains(25)); // false
System.out.println("Минимум: " + bst.min()); // 20
System.out.println("Максимум: " + bst.max()); // 80
bst.delete(20);
System.out.println("После удаления 20, содержит 20? " + bst.contains(20)); // false
}
Алексей Петров, архитектор программного обеспечения
В прошлом году я руководил проектом по миграции legacy-системы управления складскими запасами. Старая система использовала обычные массивы для хранения товаров, и с ростом ассортимента до 50 000+ наименований, поиск нужных позиций стал занимать недопустимо много времени.
Мы решили реорганизовать структуру хранения, используя бинарные деревья поиска. Я лично провел рефакторинг кода, заменив линейные массивы на BST. Сначала всё работало отлично — время обработки запросов сократилось в 20 раз. Но через несколько месяцев производительность снова упала.
Причина оказалась в том, что товары добавлялись в систему партиями с возрастающими артикулами. Это приводило к вырождению BST в линейную структуру, где каждый узел имел только правого потомка. Решением стал переход на AVL-деревья, которые обеспечили стабильную производительность независимо от порядка добавления данных. Это был важный урок — выбор правильной структуры данных требует понимания не только алгоритмической сложности, но и контекста использования.
Методы обхода дерева Java: инструкция и код
Обход дерева — критически важная операция для обработки и анализа данных. Существуют различные алгоритмы обхода, каждый с собственными преимуществами и применениями. Рассмотрим основные методы обхода бинарного дерева и их реализацию в Java. 🔄
Добавим в наш класс BST методы для обхода дерева:
// Добавьте эти методы в класс BinarySearchTree
// ОБХОД В ГЛУБИНУ (Depth-First Traversal)
// 1. Обход в порядке "Inorder" (левый-корень-правый)
public void inorderTraversal() {
inorderTraversal(root);
}
private void inorderTraversal(Node<T> node) {
if (node != null) {
inorderTraversal(node.left);
System.out.print(node.value + " ");
inorderTraversal(node.right);
}
}
// 2. Обход в порядке "Preorder" (корень-левый-правый)
public void preorderTraversal() {
preorderTraversal(root);
}
private void preorderTraversal(Node<T> node) {
if (node != null) {
System.out.print(node.value + " ");
preorderTraversal(node.left);
preorderTraversal(node.right);
}
}
// 3. Обход в порядке "Postorder" (левый-правый-корень)
public void postorderTraversal() {
postorderTraversal(root);
}
private void postorderTraversal(Node<T> node) {
if (node != null) {
postorderTraversal(node.left);
postorderTraversal(node.right);
System.out.print(node.value + " ");
}
}
// ОБХОД В ШИРИНУ (Breadth-First Traversal)
// Обход по уровням (уровень за уровнем)
public void levelOrderTraversal() {
if (root == null) {
return;
}
Queue<Node<T>> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node<T> current = queue.poll();
System.out.print(current.value + " ");
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
}
}
// Рекурсивная реализация обхода с применением действия к каждому узлу
public void traverse(Consumer<T> action, String traversalType) {
switch (traversalType.toLowerCase()) {
case "inorder":
inorderTraversal(root, action);
break;
case "preorder":
preorderTraversal(root, action);
break;
case "postorder":
postorderTraversal(root, action);
break;
case "levelorder":
levelOrderTraversal(action);
break;
default:
throw new IllegalArgumentException("Неизвестный тип обхода: " + traversalType);
}
}
private void inorderTraversal(Node<T> node, Consumer<T> action) {
if (node != null) {
inorderTraversal(node.left, action);
action.accept(node.value);
inorderTraversal(node.right, action);
}
}
private void preorderTraversal(Node<T> node, Consumer<T> action) {
if (node != null) {
action.accept(node.value);
preorderTraversal(node.left, action);
preorderTraversal(node.right, action);
}
}
private void postorderTraversal(Node<T> node, Consumer<T> action) {
if (node != null) {
postorderTraversal(node.left, action);
postorderTraversal(node.right, action);
action.accept(node.value);
}
}
private void levelOrderTraversal(Consumer<T> action) {
if (root == null) {
return;
}
Queue<Node<T>> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node<T> current = queue.poll();
action.accept(current.value);
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
}
}
Каждый метод обхода имеет свои применения и особенности:
- Inorder (симметричный обход) — при обходе BST элементы выводятся в отсортированном порядке. Используется для получения элементов в порядке возрастания.
- Preorder (прямой обход) — полезен для создания копии дерева или получения префиксной записи выражения.
- Postorder (обратный обход) — применяется для удаления дерева (сначала обрабатываем потомков, затем родителя) или вычисления постфиксных выражений.
- Level Order (обход по уровням) — обход дерева по уровням, слева направо. Используется для построения визуального представления дерева.
Для обработки данных во время обхода мы использовали функциональный интерфейс Consumer, что позволяет гибко определять действия над элементами дерева. Пример использования методов обхода:
public static void main(String[] args) {
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
// Построим дерево
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);
System.out.println("Inorder traversal:");
bst.inorderTraversal(); // Вывод: 20 30 40 50 60 70 80
System.out.println("\nPreorder traversal:");
bst.preorderTraversal(); // Вывод: 50 30 20 40 70 60 80
System.out.println("\nPostorder traversal:");
bst.postorderTraversal(); // Вывод: 20 40 30 60 80 70 50
System.out.println("\nLevel order traversal:");
bst.levelOrderTraversal(); // Вывод: 50 30 70 20 40 60 80
// Использование функционального интерфейса
System.out.println("\nInorder с использованием Consumer:");
bst.traverse(value -> System.out.print(value * 2 + " "), "inorder"); // Умножаем каждое значение на 2
}
Балансировка деревьев: AVL дерево пример кода
AVL-дерево — самобалансирующееся бинарное дерево поиска, названное в честь его создателей (Adelson-Velsky и Landis). Основное отличие от обычного BST — это автоматическое поддержание сбалансированного состояния, где разница высот левого и правого поддерева любого узла не превышает 1. ⚖️
Реализуем AVL-дерево, которое сохранит все преимущества BST и устранит его главный недостаток — вырождение в связный список:
public class AVLTree<T extends Comparable<T>> {
private static class Node<T> {
private T value;
private Node<T> left;
private Node<T> right;
private int height; // Высота поддерева с корнем в этом узле
public Node(T value) {
this.value = value;
this.left = null;
this.right = null;
this.height = 1; // Новый узел изначально имеет высоту 1
}
}
private Node<T> root;
public AVLTree() {
root = null;
}
// Получение высоты узла
private int height(Node<T> node) {
if (node == null) {
return 0;
}
return node.height;
}
// Получение баланс-фактора узла (разница высот правого и левого поддерева)
private int getBalanceFactor(Node<T> node) {
if (node == null) {
return 0;
}
return height(node.left) – height(node.right);
}
// Обновление высоты узла
private void updateHeight(Node<T> node) {
if (node != null) {
node.height = Math.max(height(node.left), height(node.right)) + 1;
}
}
// Правый поворот для балансировки
private Node<T> rightRotate(Node<T> y) {
Node<T> x = y.left;
Node<T> T2 = x.right;
// Выполнение поворота
x.right = y;
y.left = T2;
// Обновление высот
updateHeight(y);
updateHeight(x);
return x; // Новый корень
}
// Левый поворот для балансировки
private Node<T> leftRotate(Node<T> x) {
Node<T> y = x.right;
Node<T> T2 = y.left;
// Выполнение поворота
y.left = x;
x.right = T2;
// Обновление высот
updateHeight(x);
updateHeight(y);
return y; // Новый корень
}
// Вставка элемента
public void insert(T value) {
root = insertRec(root, value);
}
private Node<T> insertRec(Node<T> node, T value) {
// Стандартная вставка BST
if (node == null) {
return new Node<>(value);
}
int compareResult = value.compareTo(node.value);
if (compareResult < 0) {
node.left = insertRec(node.left, value);
} else if (compareResult > 0) {
node.right = insertRec(node.right, value);
} else {
// Дубликаты не вставляем
return node;
}
// Обновляем высоту текущего узла
updateHeight(node);
// Получаем баланс-фактор для проверки необходимости балансировки
int balance = getBalanceFactor(node);
// Случаи балансировки
// Левый-Левый (LL) – Правый поворот
if (balance > 1 && value.compareTo(node.left.value) < 0) {
return rightRotate(node);
}
// Правый-Правый (RR) – Левый поворот
if (balance < -1 && value.compareTo(node.right.value) > 0) {
return leftRotate(node);
}
// Левый-Правый (LR) – Левый, затем Правый поворот
if (balance > 1 && value.compareTo(node.left.value) > 0) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// Правый-Левый (RL) – Правый, затем Левый поворот
if (balance < -1 && value.compareTo(node.right.value) < 0) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
// Если балансировка не требуется, возвращаем узел
return node;
}
// Удаление элемента
public void delete(T value) {
root = deleteRec(root, value);
}
private Node<T> deleteRec(Node<T> node, T value) {
if (node == null) {
return null;
}
int compareResult = value.compareTo(node.value);
if (compareResult < 0) {
node.left = deleteRec(node.left, value);
} else if (compareResult > 0) {
node.right = deleteRec(node.right, value);
} else {
// Узел для удаления найден
// Случай 1: Узел без дочерних элементов или с одним дочерним элементом
if (node.left == null || node.right == null) {
Node<T> temp = (node.left != null) ? node.left : node.right;
// Нет дочерних элементов
if (temp == null) {
node = null;
} else { // Один дочерний элемент
node = temp;
}
} else {
// Случай 2: Узел с двумя дочерними элементами
// Находим минимальный элемент в правом поддереве
Node<T> successor = findMin(node.right);
// Заменяем значение текущего узла
node.value = successor.value;
// Удаляем найденный элемент из правого поддерева
node.right = deleteRec(node.right, successor.value);
}
}
// Если после удаления дерево стало пустым
if (node == null) {
return null;
}
// Обновляем высоту текущего узла
updateHeight(node);
// Получаем баланс-фактор для проверки необходимости балансировки
int balance = getBalanceFactor(node);
// Случаи балансировки (как в методе вставки)
// Левый-Левый (LL)
if (balance > 1 && getBalanceFactor(node.left) >= 0) {
return rightRotate(node);
}
// Левый-Правый (LR)
if (balance > 1 && getBalanceFactor(node.left) < 0) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// Правый-Правый (RR)
if (balance < -1 && getBalanceFactor(node.right) <= 0) {
return leftRotate(node);
}
// Правый-Левый (RL)
if (balance < -1 && getBalanceFactor(node.right) > 0) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
// Поиск минимального элемента в поддереве
private Node<T> findMin(Node<T> node) {
Node<T> current = node;
while (current.left != null) {
current = current.left;
}
return current;
}
// Inorder обход для проверки
public void inorderTraversal() {
inorderRec(root);
System.out.println();
}
private void inorderRec(Node<T> node) {
if (node != null) {
inorderRec(node.left);
System.out.print(node.value + " ");
inorderRec(node.right);
}
}
// Проверка, сбалансировано ли дерево
public boolean isBalanced() {
return checkBalance(root);
}
private boolean checkBalance(Node<T> node) {
if (node == null) {
return true;
}
int balanceFactor = getBalanceFactor(node);
if (Math.abs(balanceFactor) > 1) {
return false;
}
return checkBalance(node.left) && checkBalance(node.right);
}
}
Основные компоненты реализации AVL-дерева:
- Балансировка — ключевая операция, поддерживающая разницу высот поддеревьев не более 1
- Повороты — операции перестройки структуры дерева для восстановления баланса (левый поворот, правый поворот, комбинации поворотов)
- Баланс-фактор — разница между высотой левого и правого поддерева, используется для определения необходимости и типа балансировки
- Обновление высоты — пересчёт высоты узлов после выполнения операций вставки, удаления или балансировки
Пример использования AVL-дерева:
public static void main(String[] args) {
AVLTree<Integer> avlTree = new AVLTree<>();
// Добавляем элементы, которые в обычном BST вызвали бы вырождение
for (int i = 1; i <= 10; i++) {
avlTree.insert(i);
}
// Проверяем, что дерево сбалансировано
System.out.println("Дерево сбалансировано? " + avlTree.isBalanced());
// Выводим элементы (должны быть отсортированы)
System.out.print("Элементы дерева: ");
avlTree.inorderTraversal();
// Удаляем элемент и проверяем, что дерево все еще сбалансировано
avlTree.delete(5);
System.out.println("После удаления 5, дерево сбалансировано? " + avlTree.isBalanced());
System.out.print("Элементы после удаления: ");
avlTree.inorderTraversal();
}
Преимущества AVL-дерева над обычным BST очевидны — оно гарантирует логарифмическую сложность операций поиска, вставки и удаления даже в худшем случае, когда элементы добавляются в отсортированном порядке.
Овладение структурой данных "дерево" в Java открывает перед программистом огромные возможности для оптимизации и решения сложных задач. От простых бинарных деревьев до самобалансирующихся AVL-структур — каждый тип имеет свои преимущества и области применения. Понимание принципов работы деревьев, их реализации и алгоритмов обхода — это не просто теоретические знания, а практический инструментарий, необходимый каждому серьезному Java-разработчику. Внедряйте эти структуры в свои проекты, экспериментируйте с ними, и вы увидите, как растет производительность и элегантность вашего кода.