Что такое бинарное дерево? Бинарное дерево - это структура данных, суть которой - состояние иерархии узлов, где каждый узел имеет либо ноль, либо не больше двух дочерних узлов. Изначальный узел называется корнем.
Вот простая реализация на C#.
public class BinaryTreeNode<T>
{
private T _value;
private BinaryTreeNode<T>? _left;
private BinaryTreeNode<T>? _right;
public BinaryTreeNode(T value, BinaryTreeNode<T>? left = null, BinaryTreeNode<T>? right = null)
{
_value = value;
_left = left;
_right = right;
}
//Вот тут какая-то логика
}
В визуальном отображении такая структура как раз и напоминает перевёрнутое дерево.
Root
/ \
A B
/ \ \
C D E
В чём преимущество бинарных деревьев? В алгоритме обхода.
Предположим, у нас есть некоторые числа: 11, 5, 17, 3, 7, 13, 19, 2, 23.
Предположим, мы вставили их в массив.
У нас есть операции: вставка в середину, добавление, удаление, поиск.
Сложность операций:
- Вставка в середину - O(n), так как нам нужно пересобрать массив.
- Добавление - если размер массива 10, а мы вставляем 11 элемент, то нам придётся собрать массив заново. В итоге O(n). Если добавлением мы перезаписываем 10 элемент, то O(1).
- С удалением с конца тоже самое, что и с добавлением. С середины - тоже самое, что со вставкой.
- Поиск - O(n), если мы не получаем по индексу. Тогда будет O(1).
А теперь предположим тоже самое с бинарным деревом.
Алгоритм сортировки:
Начинаем в корне (верхнем узле).
Сравниваем новое число X с числом V в текущем узле.
Если X < V - идём влево.
Если X > V - идём вправо.
Если X = V - тут уже зависит от вашего желания, что с этим делать. Давайте предположим, что у нас только уникальные значения.
Теперь на числах.
Вставляем 11 - дерево пустое -> 11 становится корнем.
Вставляем 5. Cравниваем с 11.
5 < 11 -> идём влево, место пустое -> вставляем 5 как левый ребёнок 11.
Вставляем 17.
17 > 11 -> идём вправо -> вставляем как правый ребёнок 11.
Вставляем 7.
7 < 11 -> влево к 5;
Дальше 7 > 5 -> вправо от 5 - вставляем там.
Суть: меньше - налево, больше - направо. Это простое локальное правило гарантирует, что любая левая ветка хранит только меньшие значения, а правая - только бОльшие.
Получается вот такой рисунок.
11
/ \
5 17
/ \ / \
3 7 13 19
/ \
2 23
Примерно такая картина по операциям у нас получается.
h - это высота дерева.
Поиск:
O(h) -> в худшем случае O(n), если у нас дерево состоит только из одной ветки и мы идём только по ней.
Вставка:
O(h) -> в худшем случае O(n).
Удаление:
O(h) -> в худшем случае O(n).
Однако, если у нас хорошо распределённое дерево, как правило O(n) должно происходить редко, так как мы постоянно отсекаем какие-то его стороны. В этом случае также O(h) можно упростить до O(log n).
Таким образом, если дерево хорошо сбалансировано, у него более оптимизированное количество операций.
Однако, как правило такая оптимизация не всегда нужна, так как оперировать тем же List гораздо более удобно и понятно для разработчика. Думать о таких вещах нужно при огромном количестве объектов и при явной проблеме перформанса.
Безусловно, это не единственный вид деревьев. Их видов очень много под разные цели. Но сейчас мы разбираем именно бинарное, ибо его просто понять и оно периодически спрашивается на собеседовании. Более сложные варианты реализации спрашивают ещё реже
🚀 Пост Guru Unity: @Minerope