Сбалансированность дерева

Опубликовано Sep 30, 2011 в Деревья и графы | 1 коммент.

, , ,

Сбалансированным деревом называется дерево, в котором длины путей от корня до любого листового узла отличается не более, чем на 1.
Напишите функцию с приведенной сигнатурой, которая бы проверила, что дерево сбалансировано. Если нужно, можно создать вспомогательные функции.

bool is_tree_balanced(tree_node* tree_root)
{
  //ваш код
};
1 Цель задания быстрая проверка базовых знаний основных структур данных, алгоритмов и средств их реализации
2 Время выполнения 20 минут
3 Формат выполнения код пишется на компьютере или бумаге по выбору, без доступа к документации

Критерии оценки FulcrumWeb:

Нужно продемонстрировать знание стандартных приемов работы деревьями.

Ожидаемые вопросы:

  1. Можно ли ограничиться бинарным деревом?
  2. Я собираюсь использовать динамические контейнеры STL. Есть ли ограничения на их применение?

Оценка результатов:

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

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


Один комментарий : “Сбалансированность дерева”

  1. Сергей says:

    Мне кажется в вашем тестовом задании(сбалансированность
    дерева) некорректное определение сбалансированного дерева.
    Цитата:
    Сбалансированным деревом называется дерево, в котором длины путей от корня до любого листового узла отличается не более, чем на 1.
    Исходя из которого, при входной последовательности:
    50, 30, 20, 10, 70, 90 — дерево сбалансировано.

    Так будет лучше
    Дерево является СБАЛАНСИРОВАННЫМ только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1.

Оставить комментарий

Ваш адрес email не будет опубликован.


*