Что такое двоичное дерево

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

Чаще всего на собеседованиях говорят о двоичном дереве поиска, где операции поиска, вставки и удаления в среднем работают за O(log n) в сбалансированном дереве, а в вырожденном (сильно несбалансированном) случае могут деградировать до O(n).

Подробный ответ

Определение:

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

Что вам нужно знать:

• Деревья разработаны для оптимизирования списка и сортировки.
• Вырожденное дерево — это несбалансированное дерево (его высота заметно больше, чем у сбалансированного, то есть ближе к n, чем к log n). Если оно полностью одностороннее, то представляет собой, по сути, связный список.
• Деревья относительно просты в реализации по сравнению с другими структурами данных.
• Используются для создания двоичных деревьев поиска.
• Двоичное дерево с помощью сравнивания ключей решает, в каком направлении следовать к дочернему узлу.
• Ключ левого дочернего узла меньше, чем у родительского.
• Ключ правого дочернего узла больше, чем у родительского.
• Не может быть дублирующих узлов.
• В связи с вышесказанным такое дерево чаще используется как структура данных, чем двоичное дерево.

Эффективность («О» большое):

• Индексирование: двоичное дерево поиска — O(log n).
• Поиск: двоичное дерево поиска — O(log n).
• Вставка: двоичное дерево поиска — O(log n).