Зависимо типизированные деревья в C ++ во время компиляции

Я пытаюсь придумать некоторые структуры данных с зависимой типизацией для C ++ во время компиляции. Я несколько рассмотрел основной пример, тип списка с его длиной, закодированной в типе, иначе. list<T, length>, Здесь можно легко сохранить простые инварианты, например, вы можете быть уверены, что добавление двух списков будет иметь сумму длины его части как длины и т. Д. До сих пор тривиально. Сейчас я перехожу на зависимо типизированные деревья, иначе. binary_tree<T, height>, так что я могу изменить это для достижения сбалансированных по высоте деревьев. Идея состоит в том, чтобы отказаться от любой операции, которая нарушит балансировку по высоте во время компиляции. Все это также является хорошим упражнением в рекурсивном мышлении для меня.

Я собираюсь представить свою попытку и позже спрошу об ошибке.

// A binary tree of height N
template <typename T, std::size_t N>
struct binary_tree
{
constexpr binary_tree(const T &node, binary_tree<T, N-1> left,
binary_tree<T, N-1> right)
:root{node}, left{left}, right{right}, size{left.size + right.size + 1}
{}

const T root;
const binary_tree<T, N-1> left;
const binary_tree<T, N-1> right;
const std::size_t size; // num of elements in tree
constexpr static const std::size_t capacity = 2^N -1;
};

template <typename T>
struct binary_tree<T, 0>
{
const std::size_t size{0};
constexpr static const bool nil = true;
};

template <typename T>
using empty_tree = binary_tree<T,0>;template <typename T, std::size_t N>
constexpr auto insert(const T& elem, const binary_tree<T, N> &tree) {
if constexpr (N == 0)
return binary_tree<T, 1>{elem, empty_tree<T>{}, empty_tree<T>{}};
else if (elem <= tree.root && tree.size < binary_tree<T, N>::capacity)
return binary_tree<T, N>{tree.root,
insert(elem, tree.left),
tree.right};
else if (elem <= tree.root && tree.size == binary_tree<T, N>::capacity)
return binary_tree<T, N + 1>{tree.root,
insert(elem, tree.left),
tree.right};
else if (elem > tree.root && tree.size < binary_tree<T, N>::capacity)
return binary_tree<T, N>{tree.root,
tree.left,
insert(elem, tree.right)};
else if (elem > tree.root && tree.size == binary_tree<T, N>::capacity)
return binary_tree<T, N + 1>{tree.root,
tree.left,
insert(elem, tree.right)};
}

int main() {
constexpr binary_tree<int, 1> tr1{2, empty_tree<int>{}, empty_tree<int> {}};
constexpr auto tr2 = insert(1, tr1);
}

Дело в том, что мой insert Функция пытается создать вызовы и для других веток, так как только первый constexpr if, Почему-то мне нужно сделать все дела else if constexpr но это кажется невозможным, так как сравнение elem чтобы увидеть, какое поддерево вставить не constexpr, Почему elem < tree.root не является constexprВ конце концов, они являются двумя постоянными значениями.

Редактировать: я понял, что проблематично брать левое и правое поддеревья одинаковой высоты, что не обязательно верно для общих деревьев. Это смущает меня больше.