Дерево будет использоваться как внутренняя структура данных std::set. Методы begin (и cbegin) std::set имеют постоянную сложность, поэтому std::set должен иметь указатель узла-члена закрытых данных на первый элемент набора; обновляется вызовами, которые изменяют набор.
Должен std::set , а также хранить указатель на root? Например, для insert одна операция O (log (n)) может найти root, а другая может впоследствии применить традиционный алгоритм. Будут накладные расходы, но все равно будет сложность; и каждый std::set объект будет на один указатель меньше по размеру.