Во время собеседования меня спрашивали, какой был рекомендуемый тип дерева, если вы собираетесь реализовать поиск по ширине.Рекомендуемый тип дерева для поиска по ширине
Я не мог видеть конкретного преимущества для чего-либо вроде красно-черного/радиуса/попыток.
Какой лучший вид использовать?
Я бы сразу задал два вопроса.
В общем, причина для поиска по ширине заключается в том, что вы хотите получить ответ, близкий к корню. Ваше дерево должно быть сформировано таким образом, чтобы «близко к корню» соответствовало вашим критериям для поиска. И тогда вам нужно дерево, форма которого соответствует этим критериям. Это, как правило, очень отличается от того, чтобы оптимизировать форму, чтобы минимизировать расстояние от корня до любого листа (например, красно-черные деревья).
И забота о том, что еще вы делаете, заключается в том, что если это общая структура данных, вы блокируете все это. Поэтому тщательно продумайте, какие блокировки и утверждения у вас будут, и как вы справитесь с этим.
«Лучший», каким образом? Представление [left-child right-sibling] (https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree) довольно удобно для поиска по ширине общего дерева. Он спрашивал конкретно о бинарных деревьях или деревьях вообще? –
На самом деле он не был бы нарисован на нем ... основанный на команде/продукте, я бы заподозрил, что это то, что они уже реализовали, и он хотел посмотреть, не приземлюсь ли я на то же самое - что тяжело, часть всей дискуссии! Многообразное дерево кажется применимым к проблеме, которую он описал (сохраняя числа, стоящие вдоль одного измерения, затем другое, затем другое и т. Д.). – Oli
Однако, прочитав вашу ссылку, я не понимаю, почему она лучшая - вы имеете в виду просто для простоты внедрения, потому что вы просто следуете за одной стороной, чтобы получить первый уровень? – Oli