std :: map和二分查找树

Question

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

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

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

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

Answer 1

地图中的节点通常看起来像这样:

struct node
{
    node* left;
    node* right;

    Key_type key;
    Value_type value;
};

如您所述,您对BST的工作原理有一般性的了解:

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

在我的nodestruct 的情况下,"element"是key成员.因此,比较密钥以确定树的组织.键的比较小于父节点的节点位于左侧,节点的键比较大的节点位于右侧.在value没有树的组织参加,它仅仅是补充数据.它只是通过成为同一结构的一部分而与键相关联.