Читать книгу Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию - Гейл Макдауэлл - Страница 32

Деревья и графы – рассадник неоднозначностей и неправильных предположений. Убедитесь, что не упустили из виду какие-либо аспекты и сможете обосновать ваше решение в случае необходимости.

Бинарное дерево vs бинарное дерево поиска

Когда задан вопрос о бинарном дереве, многие кандидаты считают, что речь идет о бинарном дереве поиска. Уточните, что имел в виду интервьюер. Бинарное дерево поиска предполагает, что для всех узлов левые дети меньше или равны текущему узлу, а правые – больше текущего узла.

Сбалансировано vs несбалансировано

В большинстве случаев предполагается, что деревья сбалансированы, но не всегда. Попросите интервьюера уточнить задачу. Если дерево несбалансировано, вам придется создавать алгоритм, учитывая оптимизацию. Существует множество способов сбалансировать дерево так, чтобы глубина поддеревьев оставалась в пределах заданного диапазона. Но это не означает, что левое и правое поддеревья будут одинакового размера.

Полнота дерева

Полные деревья – это деревья, в которых все листья находятся внизу, а все остальные узлы, не являющиеся листьями, имеют по два потомка. Нужно отметить, что полные деревья – чрезвычайная редкость, так как дерево должно содержать 2ⁿ узлов, чтобы удовлетворять этому условию.

Большинство кандидатов неплохо разбираются в бинарных деревьях, но обход графа требует несколько иного подхода. Особенно сложным является поиск в ширину. Не забудьте, что поиск в ширину (BFS, Breadth First Search) и поиск в глубину (DFS, Depth First Search) предназначены для разных сценариев. DFS – это самый простой способ посетить все узлы в графе, или, по крайней мере, посетить каждый узел, пока не найдется искомый. Однако при работе с очень большими деревьями DFS не подходит. В этих случаях лучше воспользоваться BFS.

Поиск в глубину

При DFS мы посещаем узел r и затем проходимся по всем ближайшим к r узлам. При попадании в узел n (соседний с r) мы посещаем всех его соседей. Таким образом, перед перемещением к следующему потомку узла r полностью обследуется узел n.

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

Приведенный псевдокод реализует DFS:

1 void search(Node root) {

2 if (root!= null) return;

3 visit(root);

4 root.visited = true;

5 foreach (Node n in root.adjacent) {

6 if (n.visited == false)

7 search(n);

8 }

9 }

10 }

Поиск в ширину

Поиск в ширину (BFS) не так прост, у большинства кандидатов при первом знакомстве он вызывает затруднения. При BFS перед посещением любого из «внуков» r мы должны посетить всех соседей с узла r. Оптимальным решением в этом случае будет реализация с циклом и очередью:

1 void search(Node root) {

2 Queue queue = new Queue();

3 root.visited = true;

4 visit(root);

5 queue.enqueue(root); // Добавление в конец очереди

6

7 while (!queue.isEmpty()) {

8 Node r = queue.dequeue(); // Удаление из головы очереди

9 foreach (Node n in r.adjacent) {

10 if (n.visited == false) {

11 visit(n);

12 n.visited = true;

13 queue.enqueue(n);

14 }

15 }

16 }

17 }

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