Ram*_*ary 9 c++ algorithm stl red-black-tree data-structures
我在cplusplus.com上读到,std::map通过将迭代器作为参数传递来删除a中元素的操作是常量时间.
如果我没有错(如果我是,请纠正我)迭代器基本上是指向地图中元素的指针,++运算符只返回当前元素的有序后继,我猜这是如何在遍历时实现排序结果std::map.
现在如果地图是一棵红黑树,不应该删除一个元素(使用它的地址)是对数时间操作,我不知道他们是如何在恒定时间内完成的(除非存在高度内存浪费的替代方法) .
对于初学者,我会对你从cplusplus.com获得的任何信息保持警惕; 该网站已知有一些错误.
访问cppreference.com,我们得出复杂性是按时间摊销的.这意味着n个erase操作的任何序列都应该花费时间O(n),即使单个擦除操作花费的时间大于O(1).
事实证明,插入或删除红/黑树所需的时间最终计算如下:每次插入或删除需要时间O(log n)来查找节点的位置,但之后只进行摊销O( 1)插入或移除元素的工作.这意味着从红/黑树插入或删除节点所完成的工作由确定该节点所在位置所需的工作主导,而不是之后重新平衡树所需的工作.因此,如果您已经有一个指向红色/黑色树的指针并想要删除该元素,则只需要进行分摊O(1)工作以删除该元素.每个单独的删除可能需要一些时间(最多为O(log n)),但是在n个操作流中,完成的总工作量最多为O(n).
请注意,该标准不要求std::map使用红色/黑色树.它可以使用另一种类型的数据结构(例如,展开树,替罪羊树或确定性跳转列表),这也保证了这种时间复杂性.有趣的是,并非所有平衡二叉搜索树结构都支持分摊的O(1)删除.在AVL树,例如,没有这样的保证.
希望这可以帮助!
| 归档时间： |
|
| 查看次数： |
303 次 |
| 最近记录： |