Implementation of std::set using different data structures

Question

Inspired by this question: Why isn't std::set just called std::binary_tree? I came up with one of my own. Is red-black tree the only possible data structure fullfilling requirements of std::set or are there any others? For instance, another self-balancing tree - AVL tree - seems to be good alternative with very similar properties. Is it theoretically possible to replace underlying data structure of std::set or is there a group of requirements that makes red-black tree the only viable choice?

Answer 1

Each data structure that can meet the AssociativeContainer requirements can be adopted to implement the std::set container. Binary search trees (BST) are generally the category of data structures that is more suitable, and in particular the red-black tree offers the best trade-offs.

The red-black tree ensures logarithmic-time insert, erase and search operations and constant-time rotate operations. On the other hand, the AVL tree may require logarithmic-time rotate operations. Furthermore, the number of rebalancing that must be performed is lower because the balancing requirements are less strict. This depends on the maximum height of the structure, which is 2 logN for the red-black tree and ~1.44 logN for the AVL tree.

	AVL tree	red-black tree
max height	~1.44 logN	2 logN
rotation	O(logN)	O(1)

Since 2009, it is possible to use another data structure, the WAVL tree. It is designed to combine some of the best properties of both the red-black tree and AVL tree.

The most interesting feature is its ability to change the balancing requirements depending on the number of performed insert and erase operations: if the tree is constructed from only insertions, the maximum height is restricted to ~1.44 logN, and therefore the structure allows more efficient search operations; if both insertions and deletions are performed on the tree, the maximum height is relaxed to 2 logN, and therefore the structure allows more efficient modify operations. In this way, the tree automatically adapts to the requirements that are likely more efficient for the use cases.

The rotate operations are always constant-time. Furthermore, they are slightly more efficient than that in the red-black tree.

	WAVL tree	red-black tree
max height	~1.44 logN / 2 logN	2 logN
rotation	O(1)	O(1)

Answer 2

AVL trees have worse performance (not to be confused with asymptotic complexity) than RB trees in most real world situations. You can base std::set on AVL trees and be fully standard-compliant, but it will not win you any customers.