std :: map和二进制搜索树

提问于 2024-05-19T09:14:21+08:00

浏览次

7

我已经读过std map是使用二叉搜索树数据结构实现的 .

BST是一种顺序数据结构（类似于数组中的元素），它将元素存储在BST节点中并按顺序维护元素 . 对于例如如果element小于node，则将其存储在节点的左侧，如果它大于node，则将其存储在node的右侧 . 通过这种方法，我们实现了搜索，插入等各种操作的O（log n）复杂度 .

但是，std map是一个关联容器 . 我们有一个键和值插入 . 它是否真的使用BST实现，如果是，如何实现？在BST，我们没有任何关键或 Value . 它是一种标准容器 .

我有点困惑 . 请帮我澄清一下 . 它不影响我的工作，但我想更好地理解它们 . 谢谢你的帮助 .

2 回答

1
Map 中的节点通常看起来像这样：
```
struct node
{
    node* left;
    node* right;

    Key_type key;
    Value_type value;
};
```
如您所述，您对BST的工作原理有一般性的了解：

如果element小于node，则将其存储在节点的左侧，如果它大于node，则将其存储在节点的右侧 .

对于我的 node 结构，"element"是 key 成员 . 因此，比较密钥以确定树的组织 . 's keys compare less than that of a parent node are placed on the left, and nodes who'的密钥比较右边的节点 . value 不参与树的组织，它只是补充数据 . 它只是通过成为同一结构的一部分而与键相关联 .
回复于 2024-05-19T09:14:21+08:00
11

C标准中没有任何内容规定应该如何实现 std::map . 因此， std::map 的基础数据结构是实施者必须做出的决定 .

但是，大多数实现都将 std::map 实现为红黑树 .

回复于 2024-05-19T09:14:21+08:00

相关问题