Деревья — это структуры данных, у которых есть корень, родитель и дочерний элемент. Одна из наиболее распространенных структур данных, связанные списки, также являются типом дерева.
Чаще всего используются бинарные деревья.
- В бинарном дереве узлы могут иметь 0, 1 или 2 дочерних узла.
- Каждый дочерний узел может иметь только один родительский узел.
Название «дерево» выбрано потому, что оно выглядит как перевернутое дерево. Существует множество реализаций деревьев, но я буду писать в основном о бинарном дереве поиска, которое чаще всего встречается в вопросах на собеседовании.
Бинарное дерево поиска
Двоичное дерево поиска — это подмножество бинарного дерева, в котором правый узел всегда больше родительского узла, а левый узел всегда меньше родительского узла. Лучше всего это поясняется графикой.
- Корень это 8.
- Правая сторона дочернего узла (10) всегда больше родительского узла (8).
- Левая сторона ребенка (3). всегда меньше, чем родительский узел (8).
Сложность времени
access: O(log(n)) search: O(log(n)) insert: O(log(n)) delete: O(log(n))
Как следует из названия, это очень полезно для поиска предмета. Временная сложность доступа/поиска составляет O(log(n)).
Итак, как это O (log (n))?
# of nodes to search = n # of steps = s n = 2^s — 1. log(n) = s
Количество шагов, необходимых для поиска элемента, равно O(log(n)), что намного эффективнее, чем O(n).
Сбалансированный против несбалансированного
Деревья могут быть неэффективными, когда они не сбалансированы. Возьмите пример с изображения ниже.
Это дерево больше похоже на связанный список. Если мы не сбалансируем это, временная сложность для наихудшего сценария может быть
access: O(n) insert: O(n) delete: O(n)
АВЛ и красные/черные деревья
AVL и Red/Black Trees балансируют дерево, если дерево становится несбалансированным после вставки или удаления. Эти два типа деревьев чаще всего используются для балансировки деревьев.
Вот реализация бинарного дерева поиска в Javascript.