Существуют ли эффективные способы создания сбалансированной древовидной структуры?

Question

У меня сбалансированная двоичная древовидная структура:

Узел 0 на глубине 0 является корнем. Левый дочерний элемент корня - 1, правый дочерний элемент - 2 и т. Д.

Пожалуйста, смотрите изображение:

Общая глубина дерева дана как N. Этот N является единственным параметром проблемы. Узлы на уровне N обозначены как конечные узлы.

Я храню это дерево, используя следующую структуру узлов.

struct node_s{
    int n, depth, parent;//n is node number
    int nodescendents;//number of descendents of the current node
    std::vector<int> descendents;//Descendents in ascending order
    int lchild, rchild;//Immediate left child and right child
    std::vector<int> lchildleaves;//leaf nodes that descend from the immediate 
                                                      //left child
    std::vector<int> rchildleaves;//leaf nodes that descend from the immediate 
                                                      //right child
};

Я намерен хранить само дерево как:

std::vector<node_s> tree;

Есть ли способ численно эффективно заполнить вектор tree, используя простую алгебру примерно как:

//Creating the nth node, beginning from 0th node, then 1st node and so on
nodes_s node;
//populate all data structures of the nth node
//precisely, here, there are loops, algebraic calculations, etc., that can help 
//populate all of the node_s data members.
tree.push_back(node);

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

Answer 1

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

Для узла k - его рангr [k] равно floor (log2 (k + 1)) и его позиция в ранге равна p [k] = k - 2 ^ r [k] + 1

Тогда k находитсяпарой (r [k], p [k])

И наоборот, k = 2 ^ r [k] + p [k] - 1

Его родительский элемент затем определяется как (r [k] -1, floor (p [k] / 2)) -> индекс узла = 2 ^ r + p - 1

k - левый потомок, если k% 2 == 1

Полагаю, все остальное довольно просто