Здравствуйте, Кодт, Вы писали:
К>Каждый узел дерева — это значение, три указателя и флажок. Хороший аллокатор позволит экономно расходовать кучу, но ты его сперва ещё сделай, этот аллокатор...
Можно выделить всё сразу — вектор нод + intrusive::set. Вообще сделать дерево с двумя указателями на ноду. Parent по большому счёту не очень нужен, при вставке-балансировке можно хранить текущую ветку на стеке. А цвет при этом паковать в left или right. Тогда потребуется максимум n*3*sizeof(void*) дополнительной памяти. Всего на треть больше, чем для quicksort. А если уж совсем память не расходовать, тогда можно и пузырьком пройтись
К>Алюминиевая пуля?
Вроде того
в худшем случае будет не намного прожорливей, чем quicksort. Зато в лучшем даст фору.