Эффективное хранилище массивов для двоичного дерева

Ответ 1

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

Некоторые преимущества этого метода

• В большинстве практических случаев вы можете улучшить хранение, чем метод pre/post + inorder.
• Сериализация просто занимает один проход
• Десериализация может быть выполнена за один проход.
• Обход ордера может быть получен за один проход без создания дерева, что может быть полезно, если ситуация требует его.

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

Итак, если есть n узлов, использование пространства будет 8n байтов + n-1 индикаторных бит + n + 1 бит для нулевых узлов = 66 * n бит.

В pre/post + inorder вы закончите использование 16n байтов = 128 * n бит.

Таким образом, вы сохраняете пробел в 62 * n бит над этим методом pre/post + inorder.

Рассмотрим дерево

       100
      /   \
     /     \
    /       \
   10       200
  / \       /  \
 .   .     150  300
          / \    / \
         .   .   .  .

где '.' являются нулевыми узлами.

Вы сериализуете его как 100 10 . . 200 150 . . 300 . .

Теперь каждый (включая поддеревья) "обход предварительного порядка с нулем" имеет свойство, что количество нулевых узлов = число узлов + 1.

Это позволяет вам создать дерево, учитывая сериализованную версию за один проход, поскольку первый node является корнем дерева. Узлы, следующие за ним, - это левое поддерево, за которым следует правое, которое можно посмотреть так:

100 (10 . .) (200 (150 . .) (300 . .))

Чтобы создать обход по порядку, вы используете стек и нажимаете, когда вы видите node и поп (в список), когда вы видите нуль. Результирующим списком является обход inorder (подробное объяснение этого можно найти здесь: С++/C/Java: Anagrams - от исходной строки до цели;).

Ответ 2

Метод 2i, 2i + 1 (двоичная куча) действительно лучший способ, если у вас есть (почти) полное дерево.

В противном случае вам не удастся сохранить ParentId (родительский указатель) с каждым node.

Ответ 3

Подумайте о XML. Это своего рода сериализация дерева. Например:

<node id="1">
    <node id="2">                                   1
    </node>                                       /   \
    <node id="3">                                2     3
        <node id="4">                                 / \
        </node>                                      4   5
        <node id="5">
        </node>
    </node>
</node>

Тогда почему пробелы и теги? Мы можем их опустить, шаг за шагом:

<1>
   <2></>
   <3>
     <4></>
     <5></>
   </>
</>

Удалите пробелы: <1><2></2><3><4></><5></></></>.

Снимите угловые скобки: 12/34/5///

Теперь проблема в следующем: что, если node имеет пустое левое поддерево и непустое правое поддерево? Затем мы можем использовать другой специальный символ, '#' для представления пустого левого поддерева.

Например:

    1
  /   \
      2
     /  \
    3

Это дерево может быть сериализовано как: 1#23///.

Ответ 4

Вы можете сохранить обход in-order и pre/post-order двоичного дерева в файле и восстановить дерево из этих обходов.