Алгоритм / Структура данных для ранжирования элементов в дереве

Question

Вот что у меня есть: дерево с произвольным количеством уровней.Мне нужен способ ранжировать все узлы на каждом уровне для каждого уровня.Если это не ясно, скажем, мой первый уровень - Мир.Мой второй уровень - континенты.Мой третий уровень - страны.Мой четвертый уровень - города.У каждой страны есть список городов, расположенных по порядку населения.Каждый континент имеет список стран, ранжированных по населению.У каждого континента ТАКЖЕ есть список городов, ранжированных по населению.И т. Д.

Алгоритм, который я представляю, представляет собой довольно простую рекурсию, но я не уверен, что будет лучшей структурой данных для отслеживания этих списков.Каждый уровень не знает, сколько у него подуровней, поэтому я не могу объявить произвольное количество списков.

Есть мысли?

Вот пример кода:

public void calcStats()
    {
        initWorldRanks();//clears ranks for the world
        for(Entity continent:theWorld.getChildren())
        {
            initContinentRanks();//clears ranks for the continent
            for(Entity country:continent.getChildren())
            {
                initCountryRanks();//clears ranks for the country
                for(Entity city:country.getChildren())
                {
                                    //Assume that add preserves sorted order.  Sorting is easy.  The tricky part is that each entity needs to be added to its ancestors.  I don't want to have fixed data structures
                    worldCityRanks.add(city);
                    continentCityRanks.add(city);
                    countryCityRanks.add(city);
                }
                worldCountryRanks.add(country);
                            continentCountryRanks.add(country);
            }
            worldContinentRanks.add(continent);
        }

Все правильно ранжировано, но это ограничивает меня определенной структурой 4 уровня.

Answer 1

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

Вы не говорите, являются ли эти узлы изменчивыми или нет.Если они неизменяемы, то это легко: вы строите итоговое значение узла, когда все его дочерние элементы добавляются во время построения.

Если они изменяемые, вы можете сделать так, чтобы каждый узел сообщал своему родителю об изменении его числа.Родитель может обновить свой счетчик и сообщить своему родителю и так далее по дереву.Это приводит к обновлению количества O (глубина дерева) или примерно O (logn) (в зависимости от того, насколько хорошо сбалансировано ваше дерево).

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

Обновление

На основе вашего обновления вопросаОдной из ваших проблем является то, что у вас есть отдельные методы для добавления вещей на разных уровнях.то есть: worldCityRanks.add, continentCityRanks.add, countryCityRanks.add и т. д. Вы должны заменить их все одним методом, который принимает глубину в качестве параметра.Например:

// Probably in your Entity class
public void addDescendant(int distance, Entity descendant) {
  // this replaces worldCityRanks.add, continentCityRanks.add,
  // countryCityRanks.add, etc.
}

Тогда вместо четырех полей для ваших дочерних коллекций у вас будет коллекция (вероятно, ArrayList) для их хранения.Вы бы расширили это по мере необходимости.

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

public void calcStats() {
  theWorld.initAllRanks();
  List<Entity> ancestors = new ArrayList<Entity>();
  theWorld.accumulateAllRanks(ancestors);
}

class Entity ... {
  ...

  void initAllRanks() {
    initRanks();
    for(Entity child: getChildren()) {
      child.initAllRanks();
    }
  }

  void accumulateAllRanks(List<Entity> ancestors) {
    int distance = ancestors.size();
    for(Entity ancestor: ancestors) {
      distance--;
      ancestor.addDescendant(distance, this);
    }
    ancestors.add(this); // push this
    for(Entity child: getChildren()) {
      child.accumulateAllRanks(ancestors);
    }
    ancestors.remove(ancestors.size() - 1); // pop this
  }

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