c – std :: map和二叉搜索树

概述我已经读过std map是使用二叉搜索树数据结构实现的. BST是一种顺序数据结构(类似于数组中的元素),它将元素存储在BST节点中并按顺序维护元素.对于例如如果element小于node,则将其存储在节点的左侧,如果它大于node,则将其存储在node的右侧.通过这种方法,我们实现了搜索,插入等各种 *** 作的O(log n)复杂度. 但是,std map是一个关联容器.我们有一个键和值插入.它是否真 我已经读过std map是使用二叉搜索树数据结构实现的.

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

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

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

解决方法 地图中的节点通常看起来像这样：

struct node{    node* left;    node* right;    Key_type key;    Value_type value;};

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

if element is less than node,store it in left of node and if it is larger than node,store it in right of node.

在我的节点结构的情况下,“元素”是关键成员.因此,比较密钥以确定树的组织.键的比较小于父节点的节点位于左侧,而键的比较大的节点位于右侧.该值不参与树的组织,它只是补充数据.它只是通过成为同一结构的一部分而与键相关联.

总结

以上是内存溢出为你收集整理的c – std :: map和二叉搜索树全部内容，希望文章能够帮你解决c – std :: map和二叉搜索树所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。