Question

Как проверить, является ли двоичное дерево поиска сбалансированным?

И должен ли каждый программист это знать и уметь?

В аэропорту США программиста из Африки заставили решать задачи

Пограничники не поверили, что Целестин Омин из Нигерии действительно приехал по рабочим делам, и пустили его в страну только после звонков в компанию.

Сотрудники американской таможни в аэропорту Нью-Йорка заподозрили нигерийского программиста Целестина Омина в том, что он скрыл настоящую профессию, и заставили его прямо на месте доказывать свою компетентность, сообщает TJournal.

Омин отправился в Нью-Йорк по работе. В США он приехал впервые, по приглашению местного сервиса First Access. Во время таможенного осмотра ему задали несколько вопросов, после чего пригласили пройти в отдельную комнату, где продержали около часа.

После этого в комнату зашел офицер, спросил, действительно ли он является программистом, а затем дал ему два задания: рассказать, как проверить, является ли двоичное дерево поиска сбалансированным, и что такое абстрактный класс и зачем он нужен.

Африканец был крайне удивлен такой просьбой, но через десять минут передал таможенникам ответы, которые их не устроили. Ситуацию разрешили звонки в Andela, компанию, где работает Омин, и First Access. На прощание офицер заявил, что нигериец его все равно не убедил.

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

http://mir24.tv/news/world/15774021

Answer 1

Думаю, что программист баз данных обязательно должен знать этот вопрос. Дело в том, что этот вопрос непосредственно связан с быстродействием базы данных. От балансировки дерева зависит количество итераций при поиске объекта. Для примера. Вы когда нибудь играли в игру "да-нет"?

Первый участник загадывает что-то (слово) а другие пытаются максимально быстро найти это слово. Так вот. Базы данных тоже работают с ключами (вопросами). Чем правильнее (сбалансированнее) поставлен алгоритм опроса (это живое или неживое, это твёрдое или мягкое...), тем быстрее может быть найден ответ. Иными словами каждый заданный вопрос (в сбалансированном варианте) должен подразумевать равную вероятность ответов 50/50%. А проблема балансировки дерева может иметь не один вариант. Там есть математические закономерности. Поэтому офицер счёл ответ неверным, ибо знал только один из нескольких возможных правильных ответов. Наверное программисты посмеются над ответом, но им тоже полезно размять мышцы на лице :-)