C++中的STL标准库map为什么是用红黑树，而不是用其它的平衡二叉搜索树

C++中的STL标准库map为什么是用红黑树，而不是用其它的平衡二叉搜索树

Probably the two most common self balancing tree algorithms are Red-Black trees and AVL trees. To balance the tree after an insertion/update both algorithms use the notion of rotations where the nodes of the tree are rotated to perform the re-balancing.

While in both algorithms the insert/delete operations are O(log n), in the case of Red-Black tree re-balancing rotation is an O(1) operation while with AVL this is a O(log n) operation, making the Red-Black tree more efficient in this aspect of the re-balancing stage and one of the possible reasons that it is more commonly used.

Red-Black trees are used in most collection libraries, including the offerings from Java and Microsoft .NET Framework.

面试的时候，被问到了，一脸懵逼，只说了红黑树的节点可以保存更多的信息

一个红黑树的节点,有左右节点指针,和父节点指针,这就是三个指针的大小+value_type的大小;
unordered_map呢,开放地址法,就value_type,如果是开链法,那就是prev指针和next指针,俩指针+value_type

也就是说,当你的value_type越小,红黑树越浪费内存.
而hash table呢,主要是填充因子,比如0.5的填充因子,那么那些桶是要浪费一些内存的.