C++ STL中是否有用于在log(n)中执行第k个元素的插入,搜索和检索的数据结构？

Question

我需要一个c ++ STL中的数据结构来执行log(n)中第k个元素的插入,搜索和检索

(注意:k是变量而不是常数)

我有一个类似的课程

class myClass{
  int id;
  //other variables
};

我的比较器只是基于这个id,没有两个元素具有相同的id.

有没有办法使用STL或我手动编写log(n)函数以在任何时间点按排序顺序维护数组？

Answer 1

Afaik,没有这样的数据结构.当然,std::set接近这一点,但并不完全.这是一棵红黑树.如果此红黑树的每个节点都使用树权重(使用以此节点为根的子树中的节点数)进行注释,则可以进行retrieve(k)查询.由于没有这样的权重注释(因为它需要宝贵的内存并且因为必须更新权重而使插入/删除更复杂),所以不可能用任何搜索树有效地回答这样的查询.

如果要构建此类数据结构,请使用传统的搜索树实现(红黑,AVL,B树,...),并为每个节点添加权重字段,以计算其子树中的条目数.然后搜索k-th条目非常简单:

草图:

1. 检查子节点的权重,找到c权重最大(从左边累积)不大于的子节点k
2. 减去k剩下的所有儿童的重量c.
3. 下降到c递归调用此过程.

在二叉搜索树的情况下,算法非常简单,因为每个节点只有两个子节点.对于B树(可能更有效),您必须考虑节点包含的子节点数.

当然,您必须更新插入/删除时的权重:从插入/删除位置向上移动树,并将每个节点的权重递增/递减到根.此外,在进行旋转(或在B树情况下拆分/合并)时,必须交换节点的权重.

另一个想法是跳过列表,其中跳过用他们跳过的元素的数量注释.但是这个实现并不简单,因为你必须在插入或删除的元素之上更新每个跳过的跳过长度,因此调整二叉搜索树不那么麻烦恕我直言.

编辑:我找到了2-3-4树(B树)的C实现,请查看本页底部的链接:http://www.chiark.greenend.org.uk/~sgtatham/algorithms /cbtree.html