Подготовка к интервью
15 вопросов с ответами по теме «Деревья поиска»
Что проверяют на интервью
Вопросы связывают форму дерева с эффективностью поиска и изменения данных. Подборка включает вырожденный случай, способы обхода, отличие бинарного поиска от дерева и примеры деревьев в словарях, HashMap и индексах.
Каталог
Алгоритм бинарного поиска и структура данных двоичного дерева поиска (BST) связаны с поиском, но различаются по сути и применению:
Читать ответВ Java HashMap с версии Java 8 для оптимизации производительности при большом количестве коллизий используется красно-чёрное дерево (Red-Black Tree).
Читать ответОбычное бинарное дерево может деградировать до линейной структуры (списка) при неблагоприятном порядке вставки, что ухудшает производительность до O(n).
Читать ответВ классической реализации красно-чёрного дерева листовые узлы (null-узлы) не хранятся как отдельные объекты, а представлены как null (или None в некоторых языках).
Читать ответДа, словарь (dictionary) можно реализовать как через хэш-таблицу, так и через сбалансированное дерево, например, красно-черное дерево.
Читать ответБинарное дерево — это структура данных, в которой каждый узел имеет не более двух потомков: левый и правый.
Читать ответВ бинарном дереве поиска (BST) поиск элемента происходит следующим образом:
Читать ответОбычное бинарное дерево — это структура данных, где каждый узел имеет не более двух потомков (левый и правый). Оно часто используется для поиска, сортировки и представления иерархий.
Читать ответКлючевые отличия между бинарным деревом и балансированным деревом:
Читать ответСложность указанных операций зависит от высоты дерева.
Читать ответХудший случай поиска в бинарном дереве поиска (BST) возникает, когда дерево является вырожденным, то есть представляет собой по сути связный список.
Читать ответБинарное дерево поиска (BST) — это структура данных, где каждый узел имеет не более двух потомков: левый содержит значения меньше текущего, правый — больше.
Читать ответ