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

Чаще всего используются бинарные деревья.

  • В бинарном дереве узлы могут иметь 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.