我读过 std map 是使用二叉搜索树数据结构实现的。
BST 是一种顺序数据结构（类似于数组中的元素），它将元素存储在 BST 节点中并按其顺序维护元素。例如如果元素小于节点，则将其存储在节点的左侧，如果元素大于节点，则将其存储在节点的右侧。通过这种方法，我们可以实现搜索、插入等各种操作的 O(log n) 复杂度。
然而，std map 是一个关联容器。我们有一个要插入的键和值对。它真的是使用 BST 实现的吗？如果是，是如何实现的？在 BST 中，我们没有任何键或值。它是一种标准集装箱。
我有点困惑。请帮我提供澄清。它不影响我的工作，但我想更好地理解它们。感谢您的帮助。
地图中的节点通常看起来像这样：
struct node
{
node* left;
node* right;
Key_type key;
Value_type value;
};
正如您所说，您对 BST 的工作原理有一个大致的了解：
如果元素小于节点，则将其存储在节点的左侧，如果元素大于节点，则将其存储在节点的右侧。
就我的情况而言node结构体，“元素”是key成员。因此，通过比较键来确定树的组织。键值比较小于父节点的节点放置在左侧，键值比较较大的节点放置在右侧。这value不参与树的组织，只是补充数据。它仅通过成为同一结构的一部分而与键相关联。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
