Как я минимально представляю состояние проверки дерева проверки?

Question

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

Например, скажем, что мое дерево выглядит примерно так:

A[0] -> B[1] -> C[1]
        |-----> D[1]
        |-----> E[1]

Здесь у нас есть состояние, где проверяются 4 узла, есть ли способ представить это состояние в сжатой форме? Наивным подходом было бы перечисление четырех узлов как проверяемых, но что, если узел B имеет 100 дочерних элементов вместо четырех?

Моя текущая идея заключается в том, чтобы сохранить предка каждого узла в компоненте данных и описать проверенное состояние в терминах набора предков, которые минимизируют данные, необходимые для представления состояния. В дереве ниже предок узла N представлен как n '. Таким образом, вышеприведенное дерево теперь будет выглядеть примерно так:

A[0, {a}] -> B[1, {a', b}] -> C[1, {a' b' c}]
             |--------------> D[1, {a' b' d}]
             |--------------> E[1, {a' b' e}]

Теперь вы можете проанализировать дерево и увидеть, что все дочерние элементы узла A проверены, и описать состояние просто, поскольку узлы с элементом данных a 'установлены в 1 или просто [a']. Если состояние узла D переключено на 0, вы можете описать состояние дерева как [a 'not d].

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

Спасибо

Answer 1

Используйте обход дерева предзаказа, начиная с корня. Если узел проверен, не проходите его дочерние элементы. Для каждого пройденного узла хранилища это проверенное состояние (логическое 0/1) в логическом битовом массиве (8 бит / байт). Наконец, сожмите результат с помощью zip / bzip или любого другого метода сжатия.

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

Answer 2

Как правило, не существует метода, который всегда сможет хранить проверенные элементы в меньшем, чем n битах пространства, где n - количество элементов в дереве.Это объясняется тем, что существует 2 ^ n различных возможных состояний проверки, поэтому вам нужно как минимум 2 ^ n различных кодировок, поэтому должна быть как минимум одна кодировка длиной 2 ^ n, поскольку существует только 2 ^ n - 1 кодировоккоторые короче этого.

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

Надеюсь, это поможет!