Apo*_*ica 2 c++ c++-standard-library binary-search-tree
关于访问std::set索引中的元素,这个网站上有几个问题,但我看到的答案是旧的,没有启发性.
有序集可以(并且通常)实现为二叉搜索树.在二叉搜索树中,通过存储以每个节点为根的树中的节点数,我们可以及时k按排序顺序访问第th个元素,O(log n)而不会增加其他操作的算法复杂度(如果这是我的错误,请纠正我.思维).
然而,如果我想要k从a排序的th元素set::set,我必须从begin()一直走到k,使用O(k)时间代替.一般来说,这可能等同于O(n)时间.
所以,我的问题是:
k个元素O(log n)而不会损害其他操作的时间复杂度？这是可能的,以增加与可使用对数时间索引来实现搜索的额外信息(平衡)搜索树.这种增强搜索树可以称为订单统计树.
增加树不会影响主要操作(插入,查找,擦除)的最坏情况渐近复杂性:它们的最坏情况仍然是对数.我不知道它是否会阻止有序关联容器的擦除和提示插入操作所需的摊销常数复杂性.
然而,渐近复杂度不是特征的唯一标准.增加树增加了对数运算的复杂系数,使得所有(或大多数)其他运算更慢.它还增加了数据结构的空间开销.因此,仅仅因为这样的数据结构是可能的,并不一定意味着使用它来实现标准库提供的通用关联容器是个好主意.
没有.在标准库中没有基于搜索树的容器具有对数索引查找.
我找到了基于Boost树组件库的提议n3700,它建议添加通用树结构.它包括类rank_tree,它似乎是一个增强的搜索树,提供您正在寻找的操作.
| 归档时间： |
|
| 查看次数： |
94 次 |
| 最近记录： |