21
std :: map实现的清单，追踪开发人员并询问他们制定决策所使用的标准，因此仍然只能做出猜测。 - Steve Jessop取决于使用情况。AVL树通常有更多的旋转操作进行平衡。所以如果您的应用程序没有太多的插入和删除操作，但是对搜索权重很大，那么AVL树可能是一个不错的选择。
std::map使用红黑树，因为它在节点插入/删除和搜索速度之间得到了合理的折衷。
3
为什么不使用哈希表呢？
在树中，类型只需要有小于运算符（比较）就可以用作键。然而，哈希表要求每个键类型都定义了一个哈希函数。将类型要求最小化对于通用编程非常重要，这样您就可以将其与各种类型和算法一起使用。
设计一个好的哈希表需要深入了解它将被使用的上下文。它应该使用开放地址法还是链接链式法？在调整大小之前应该接受哪些负载水平？它应该使用避免冲突的昂贵哈希，还是使用粗糙快速的哈希？
由于STL无法预测哪个选择最适合您的应用程序，因此默认设置需要更加灵活。树“只需工作”并且可以很好地扩展。
（C++11添加了使用unordered_map的哈希表。您可以从documentation中看到，它需要设置策略以配置许多这些选项。）
其他树呢？
红黑树提供快速查找并且是自平衡的，不像BSTs。另一个用户指出了它相对于自平衡AVL树的优点。
Alexander Stepanov（STL的创建者）表示，如果他再次编写std :: map，他将使用B * Tree，因为它对现代内存缓存更友好。
自那时以来最大的变化之一就是缓存的增长。缓存未命中非常昂贵，所以现在更加重视引用局部性。基于节点的数据结构具有较低的引用局部性，因此不太有意义。如果我今天设计STL，我会有一个不同的容器集合。例如，对于实现关联容器，内存中的B *树比红黑树要好得多。- Alexander Stepanov 地图是否总是使用树？
另一个可能的地图实现是排序向量（插入排序）和二进制搜索。这对于不经常修改但经常查询的容器很有效。我经常在C中执行此操作，因为qsort和bsearch内置。
我甚至需要使用地图吗？
缓存考虑意味着即使对于我们在学校教授的那些情况（例如从列表中删除元素），使用std：vector也很少使用std：list或std：deque。应用相同的推理，使用for循环线性搜索列表通常比为少数查找构建地图更高效且更清晰。
当然，选择可读的容器通常比性能更重要。
AVL树的最大高度为1.44logn，而红黑树的最大高度为2logn。在AVL中插入一个元素可能会在树的某个点上进行重新平衡。重新平衡完成插入。插入新叶子后，必须更新该叶子祖先的内容直至根部，或者到达两个子树深度相等的点。需要更新k个节点的概率是1/3^k。重新平衡时间复杂度为O(1)。删除一个元素可能需要多次重新平衡（最多可以达到树深的一半）。
红黑树是表示为二叉搜索树的4阶B树。B树中的4节点导致等效BST中的两个级别。在最坏情况下，树的所有节点都是2节点，仅有一个3节点链到一个叶子。该叶子将与根距离为2logn。
从根到插入点，必须将4节点更改为2节点，以确保任何插入都不会使叶子结点饱和。从插入点返回时，必须分析所有这些节点，以确保它们正确表示4节点。也可以向下遍历树来完成此操作。全局成本将是相同的。没有免费午餐！从树中删除元素的操作也是同样的顺序。
所有这些树都要求节点携带高度、权重、颜色等信息。只有Splay树不需要额外的信息。但大多数人害怕Splay树，因为它们的结构是随机的！
最后，树还可以在节点中携带权重信息，从而实现权重平衡。可以应用各种方案。当子树包含另一个子树元素的3倍以上时，应进行重新平衡。重新平衡再次通过单个或双旋转完成。这意味着最坏情况下的时间复杂度为2.4logn。可以使用2倍而不是3倍，这是一个更好的比率，但可能意味着在此处和那里留下少于1％的未平衡子树。很棘手！
哪种树是最好的？毫无疑问是AVL树。它们是编码最简单的树，并且它们的最坏高度最接近于logn。对于1000000个元素的树，AVL树的高度至多为29，红黑树为40，而权衡树则因比率而异，可以是36或50。
还有许多其他变量：随机性、添加、删除、搜索等的比例。
6
这只是你实现的选择 - 它们可以作为任何平衡树来实现。各种选择都是可比较的，只有一些细微的差异。因此，任何一种都是同样好的。
更新于2017-06-14：webbertiger在我评论后编辑了它的回答。我应该指出，现在它的答案在我看来好多了。但是我仍保留我的答案作为额外信息...
由于我认为第一个答案有误（更正：不再有两个了），而第三个答案有错误的断言，我觉得我必须澄清一些事情...
最常见的两种树是AVL和Red Black（RB）。主要区别在于使用方法：
- AVL ：如果查询（读取）比修改（修改）更频繁，则更好。内存占用略小于RB（由于需要着色的位）。
- RB ：更适合一般情况，其中查询（读取）和修改（修改）之间存在平衡或更多的修改。存储红黑标志导致略微较大的内存占用。
主要区别在于着色。在RB树中，您比AVL树少进行重平衡操作，因为着色使您有时可以跳过或缩短相对较高成本的重平衡操作。由于着色，RB树的节点级别也更高，因为它可以在黑色节点之间接受红色节点（具有~2倍的级别可能性），使搜索（读取）效率稍低...但由于它是常数（2倍），因此保持在O(log n)。
如果考虑修改树的性能损失（显著）与查询树的性能损失（几乎不重要）之间的差异，对于一般情况而言自然会更喜欢RB而不是AVL。
原文链接
O(logn)的时间，而值始终会按顺序排序。从C++11开始（我想），有unordered_map和unordered_set，它们使用哈希函数实现，虽然它们没有排序，但大多数查询和操作可以在平均情况下以O(1)完成。 - SomethingSomethingstd::map中插入或删除元素时，指向其他元素的迭代器不会失效。这使得在一个动态分配的节点中存储多个元素变得非常困难，甚至是不可能的，同时还要满足通常的时间复杂度保证。（对std::map的查询和更新必须最坏情况下花费对数时间。）因此，在实践中，std::map的实现必须是某种自平衡二叉树。 - isekaijin