Эффективное устройство хранения данных массива для двоичного дерева
Мы должны записать узлы двоичного дерева в файл. Какова большая часть пространства эффективный способ записать двоичное дерево. Мы можем сохранить его в формате массива с родителем в положении i и его дети в 2i, 2i+1. Но это потратит впустую партию пространства в случае редких двоичных деревьев.
3 ответа
Один из методов, который мне нравится, - это сохранить предварительный обход обхода, но также включить туда «нулевые» узлы. Сохранение «нулевых» узлов устраняет необходимость хранить также порядок дерева.
Некоторые преимущества этого метода
- В большинстве практических случаев вы можете лучше хранить, чем метод до / после + inorder.
- Сериализация занимает всего один проход
- Десериализация может быть выполнена за один проход.
- Обход по порядку может быть получен за один проход без построения дерева, что может быть полезно, если этого требует ситуация.
Например, скажем, у вас есть двоичное дерево из 64-битных целых чисел, вы можете хранить дополнительный бит после каждого узла, указывая, является ли следующий нулевым узлом или нет (первый узел всегда является корнем). Нулевые узлы можно представить одним битом.
Таким образом, если имеется n узлов, использование пространства составит 8n байтов + n-1 бит индикатора + n + 1 бит для нулевых узлов = 66 * n бит.
В порядке до / после + вы получите 16n байтов = 128 * n бит.
Таким образом, вы экономите 62 * n бит по сравнению с этим методом pre / post + inorder.
Рассмотрим дерево
100
/ \
/ \
/ \
10 200
/ \ / \
. . 150 300
/ \ / \
. . . .
, на котором стоит '.' являются нулевыми узлами.
Вы будете сериализовать его как 100 10. . 200 150. . 300. .
Теперь каждое (включая поддеревья) «предварительный обход с нулевым значением» имеет свойство, согласно которому количество нулевых узлов = количество узлов + 1.
Это позволяет вам создать дерево с учетом сериализованной версии за один проход, как первый узел - корень дерева.Следующие за ним узлы - это левое поддерево, за которым следует правое, которое можно рассматривать следующим образом:
100 (10 . .) (200 (150 . .) (300 . .))
Чтобы создать обход в порядке, вы используете стек и нажимаете, когда видите узел, и выталкиваете (в список), когда видите нуль. Результирующий список представляет собой обход по порядку (подробное объяснение этого можно найти здесь: C ++ / C / Java: Анаграммы - от исходной строки к целевой; ).
Вы можете сохранить в порядке и предварительного / последующего обхода двоичного дерева в файл и восстановить дерево из этих обходов.
2i, 2i + 1 (Двоичная куча) действительно лучший способ, если у вас есть (почти) полное дерево.
В противном случае вы не избежите сохранения ParentId (родительского индекса) для каждого узла.