C++ Map使用哪种数据结构

什么是Map

在学习Map使用的数据结构之前，让我们先了解一下Map。

Map是STL库的一部分，它在其中存储键值对，并且没有两个值具有相同的键，但不同的键可以存储类似的值。Map按排序顺序存储键。

以下是Map使用的一些函数及其时间复杂度：

• insert() - 时间复杂度 O(Log N)
• delete() - 时间复杂度 O(Log N)
• erase() - 时间复杂度 O(Log N)
• find() - 时间复杂度 O(Log N)

Map使用哪种数据结构？

现在来到了Map使用哪种数据结构的问题。Map的内部实现是 自平衡二叉树 。一般有两种实现自平衡二叉树的方法：

• 红黑树
• AVL树

这是两种方法，但是对于Map的内部实现，它使用 红黑树 。

为了平衡树在插入和删除之后，这两种算法都使用旋转的概念，其中树的节点旋转以执行重新平衡。虽然在这两种算法中，插入/删除操作都是 **O(log N) ，但在红黑树中，重新平衡旋转是一个 **O(1) 操作，而在AVL树中，这是一个 O(log N) 操作，从而使红黑树在重新平衡阶段的效率更高，并且可能是更常用的原因之一。

什么是红黑树？

红黑树是一种自平衡的二叉搜索树，每个节点都有一个额外的位，该位通常被解释为颜色（红色或黑色），用于确保在插入和删除期间树保持平衡。

要了解有关红黑树的更多信息，请参阅“ 红黑树 ”一文。

红黑树图示