Самый глубокий путь в дереве

Question

У меня есть дерево с n элементами, которые хранят что-то вроде |id|parent_id|.Мне нужно найти максимальную глубину этого дерева.Мне нужно сделать это в Ruby, но мне может помочь и псевдокод.

Answer 1

Предполагая, что {id, parent_id} пары находятся в словаре / карте, вы можете найти максимальную глубину, используя памятка :

Основная функция (псевдокод):

Map tree; // <<=== This is your tree; id is the key; parent_id is the value
Map depth; // This map is used for memoization
int max = -1;
foreach pair in tree
    max = Max(memoized_depth(id, tree, depth), max)

Функция рекурсивной глубины:

int memoized_depth(id, tree, depth)
    if (depth.containsKey(id)) return depth[id];
    if (!tree.contains(id)) return 0; // no parent means it's a root
    int res = memoized_depth(tree[id] // parent, tree, depth) + 1;
    depth[id] = res;
    return res;

Answer 2

Вы можете использовать следующую функцию (в псевдокоде)

def level(id)
    find parent_id for id
    if parent_id then 
        level(parent_id) + 1 
    else 
        1    // no parent -> root
end def

и выполнять итерацию по всем элементам (т.е. идентификаторам) и искать максимум.Для повышения эффективности вы можете хранить уже рассчитанные глубины в своей древовидной структуре или отдельно в кеше и получать к ним доступ.