Настраивать

Допустим, у нас есть трехмерный куб, описывающий пространство. Мы разделяем этот куб на 8 различных меньших кубов, описывающих восьмую часть пространства, и продолжаем делать это некоторое количество раз.

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

то есть первый уровень - это полное пространство, следующий - 8 подпространств, следующие 64 подпространства... до 8^n подпространств.

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

Проблема

Мне дан массив самого низкого уровня разрешения (наименьшие подпространства, т.е. листья). Этот массив содержит дискретизированные (x,y,z) координаты занятых листьев. Другими словами, в этом массиве существуют только занятые листы, пустые листы явно не заданы, поэтому, если лист не найден в этом массиве, мы можем считать его пустым.

Информация не дается в каком-либо определенном порядке, но каждый лист сам идентифицирует свое положение в трехмерном пространстве через его координату (x, y, z).

Используя эту информацию, мы хотим построить описанное дерево. Другими словами, мы хотим создать октодерево, в котором пустые листья не имеют дочерних элементов.

Как я могу эффективно построить упомянутое дерево?