Реализация std :: set с использованием различных структур данных

Question

Вдохновленный этим вопросом: Почему std :: set просто не называется std :: binary_tree? Я придумал один из них.Является ли красно-черное дерево единственно возможной структурой данных, удовлетворяющей требованиям std::set, или есть другие?Например, другое самобалансирующееся дерево - AVL дерево - кажется хорошей альтернативой с очень похожими свойствами.Теоретически возможно заменить базовую структуру данных std::set или есть группа требований, которая делает красно-черное дерево единственным жизнеспособным выбором?

Answer 1

Деревья AVL имеют худшую производительность (не путать с асимптотической сложностью), чем деревья RB в большинстве реальных ситуаций.Вы можете использовать std::set на деревьях AVL и полностью соответствовать стандарту, но это не принесет вам успеха ни одному клиенту.