Связный список, в котором каждый узел указывает на два узла и нет циклов.
Преимущество деревьев по сравнению со связанными списками заключается в том, что нам не всегда нужно искать все узлы (поскольку вы не можете пропустить узлы в связанном списке), но можно пройти по определенным путям в зависимости от искомого значения.
Конечно, деревья тоже могут быть небинарными, но бинарные деревья — обычное дело на собеседованиях по программированию.
Бинарное дерево поиска
Дерево, в котором левые дочерние узлы меньше корня, а правые дочерние узлы больше или равны корневому.
Временная сложность бинарного дерева поиска
- Вставка:
log n(сбалансированная),n(несбалансированная) - Удалить:
log n(сбалансированный),n(несбалансированный) - Поиск:
log n(сбалансированный),n(несбалансированный)
Разминка
Найти, существует ли данный номер в BST?
Как бы вы нашли число в BST, наиболее близкое к данному числу?
Большинство вопросов на основе дерева включают рекурсию. Поэтому, если вы столкнетесь с вопросом на основе дерева, подумайте о рекурсии!
Базовый
- Вычислите глубину дерева.
- Проверьте, является ли данное дерево допустимым BST
- Выведите уровень обхода дерева.
Дополнительно
- Создайте сбалансированное бинарное дерево поиска из отсортированного массива
- Выведите «зигзагообразный обход» дерева. Зигзагообразный обход — это поуровневый обход дерева, при котором каждый четный уровень обходится слева направо, а нечетный — справа налево.
- У вас есть n строк. Найдите самый длинный префикс, который встречается не менее чем в 3 строках. Например, если вам даны строки
“abcde”, “ijkl”, “abxyz”, “abcdefghi”, “iabcdef”,, самый длинный префикс, встречающийся как минимум в 3 строках, будет «ab». (Да, это вопрос о дереве. Постарайтесь быть конкретным.)
