Алгоритм обхода всей древовидной структуры

Class Diagnostic {

//Get the size in bytes of an object
static long sizeOf(Object object);

//Get the references for an object (leafs)
static List<Object> getRefs(Object object);

//Implement this with those above
public Long objectSize(Object object);
}

Как бы вы реализовали objectSize для возврата размера объекта в байтах?

Метод objectSize возвращает размер в байтах всех объединенных дочерних узлов (каждого узла в дереве).

Пример:

               Object A (19 bytes)
                      /    \
                     /      \
                   B(20)    C(37)
                   /
                  /
                C(15)

Ответ: 19+20+37+15 = 91

У меня был этот вопрос во время интервью, и мне очень любопытно увидеть ответы других. Так как я мало знал об алгоритме обхода дерева.

Я придумал это... (знаю, плохо это или нет ;), просто пытаюсь научиться)

    public Long objectSize(Object object) {
    List<Object> objectList = new ArrayList<Object>();

    Long sum = sizeOf(object);
    objectList = getRefs(object);

    for(Object object : objectList){
           sum += objectSize(object);
    }

return sum;
}

Я заметил, что у меня может быть цикл и ошибка stackoverflow, потому что я не проверял, прошел ли я уже через "узел". Затем я решил, что у меня должна быть другая структура данных (например, хэш-карта для обработки ключей/значений) для обработки временного списка для сравнения.


java algorithm tree-traversal
person fneron    schedule 15.05.2013    source источник
comment
Ваш вопрос не ясен. Должен ли objectSize(Object object); возвращать размер самого себя и всех дочерних узлов вместе взятых?   -  person BLuFeNiX    schedule 15.05.2013
comment
У вас нет циклов в дереве.   -  person MAV    schedule 15.05.2013
comment
В деревьях нет циклов, но ваш код все равно может содержать циклы, если ссылки на структуру на самом деле не образуют DAG. Под этим я подразумеваю, что для каждой пары Object A и Object B вы можете иметь A в getObjects(B) и B в getObjects(A), если по какой-то причине ссылки симметричны. В противном случае, я думаю, вы имели в виду sum += objectSize(object); в этом цикле.   -  person G. Bach    schedule 15.05.2013
comment
Поправьте меня, если я ошибаюсь, но в вашем примере функция должна возвращать 19 + 20 + 37 + 15 = 91, я прав?   -  person Rerito    schedule 15.05.2013
comment
@ G.Bach Действительно, вы подходите для обоих.   -  person fneron    schedule 15.05.2013
comment
Я предполагаю, что вы объявили sum как переменную экземпляра или переменную класса. Если это так, вам нужно помнить, что всегда нужно сбрасывать sum на 0 перед вызовом метода objectSize. В остальном алгоритм работает нормально. Тот факт, что sum является переменной экземпляра/класса, кажется немного странным...   -  person Alderath    schedule 15.05.2013
comment
@ G.Bach На самом деле, если он поместит sum += objectSize(object); в цикл, то результат для примера будет: 19 + 20 + 15 + 54 + 108 + 37 + 253 (т.е. 506). В его цикле переменная sum является переменной экземпляра/класса, которая увеличивается при каждом посещении узла.   -  person Alderath    schedule 15.05.2013
comment
@Alderath В его цикле переменная sum — это переменная экземпляра/класса, которая увеличивается при каждом посещении узла. Это идея, да. Я не понимаю, как вы пришли к таким цифрам. Это не похоже на то, что сумма поддерева добавлялась бы на каждом шагу в иерархии.   -  person G. Bach    schedule 15.05.2013
comment
@ G.Bach Я говорил об исходном вопросе. ОП обновил вопрос и сделал sum локальной переменной. т.е. sum += sizeOf(object) (переменная экземпляра/класса) заменена на Long sum = sizeOf(object) (локальная переменная). Если бы он сохранил sum в качестве переменной класса, переменная sum удваивалась бы при каждом вызове sum += objectSize(object);.   -  person Alderath    schedule 15.05.2013
comment
@Alderath Понятно, я не видел первоначальную версию вопроса.   -  person G. Bach    schedule 15.05.2013
comment
@Alderath Плохо! Я просто быстро написал свой вопрос и допустил несколько ошибок при написании кода. знак равно   -  person fneron    schedule 15.05.2013
comment
@ G.Bach Как бы вы решили проблему, если бы это была DAG? Не могли бы вы использовать вместо списка хэш-карту и проверить, например, что ключ уже был замечен...   -  person fneron    schedule 16.05.2013
comment
@fneron Если ссылочная структура, которая у вас есть, фактически образует DAG, то, что вы написали, работает нормально. Если то, что вы написали, заканчивается, вы можете быть уверены, что ваша структура также является DAG, потому что в противном случае любой круг приведет вас к бесконечному рекурсивному циклу.   -  person G. Bach    schedule 16.05.2013

Ответы (3)


arrow_upward
2
arrow_downward

Если вы имеете дело с настоящей «древовидной» структурой, вам не нужно беспокоиться о циклах.

У вас есть основная идея, но вам нужно принять во внимание фактическое возвращаемое значение рекурсивного вызова. Если мы предположим, что общий размер объекта (objectSize()) равен сумме размеров его дочерних элементов плюс его собственный размер (sizeOf()), то вам просто нужно убедиться, что вы суммируете все размеры поддерева.

Вот один из способов сделать это:

public Long objectSize(Object object) {
    List<Object> objectList = getRefs(object);
    long sum = sizeOf(object);

    for(Object object : objectList) {
         sum += objectSize(object);
    }

    return Long.valueOf(sum);
}

Чего вам не хватало, так это того, что рекурсивный вызов objectSize возвращал значение, и это значение нужно было включить (в данном случае сложением) в ваше возвращаемое значение.

person Platinum Azure    schedule 15.05.2013
comment
Собственно, я так и сделал. Я просто написал это слишком быстро. Сладкий! - person fneron; 15.05.2013

arrow_upward
0
arrow_downward

Я не проверял это, но этот простой алгоритм поиска BFS должен это сделать.

public Long objectSize(Object object) {
   long sum=sizeOf(object);

   Queue<Object> q= new LinkedList<Object>();
   for (Object o : getRefs(object)) {
      q.add(o);
   }
   while (q.peek() != null) {
      Object child= q.poll();
      sum+= sizeOf(child);
      fore (Object o : getRefs(child)) {
         q.add(o);
      }
   }
   return sum;   
}
person darijan    schedule 15.05.2013

arrow_upward
0
arrow_downward

Вот что я бы сделал:

Я бы построил стек, содержащий узлы, которые еще предстоит изучить, и обработал бы их в цикле while. Поскольку мои навыки Java где-то утеряны, я не буду давать вам реализацию, но объясню процесс:

Входные данные: дерево T
Выходные данные: общий размер узловых объектов.

  1. Инициализируйте стек S, поместив в него T.root (корневой узел).
  2. Инициализируйте общий размер size равным 0 : size = 0
  3. While S is not empty :
    1. Let N be the head of S, we pop S : N = pop(S)
    2. Вставьте N.leftChild и N.rightChild в S, если они существуют
    3. Обновить размер: размер = размер + N.size
  4. Вернуть размер
person Rerito    schedule 15.05.2013