C++ 中的排名树

Question

我们需要具有搜索和排名功能的 ADT。 也就是说，除了STL Map的接口之外，还需要一个函数'int get_rank(key)'。

这种功能的标准实现需要支持和更新自平衡搜索树（例如，在黑红树中，在STL映射/集合中使用）的每个节点中的额外整数字段。 但似乎STL映射/集不这样做。

我们正在寻找一种基于标准容器（STL、Boost）且具有最佳时间复杂度的解决方案： 查找/添加/删除元素需要 O(log n)（就像在 STL 映射/集合中一样）， 通过键计算排名也需要 O(log n)。

元素的排名是指该元素在映射/集合的所有元素的排序序列中的位置。

例子。 设置 = {0, 4, 6, 7, 8} 等级(0)=1，等级(4)=2，等级(6)=3，等级(7)=4，等级(8)=5。

我们认为，在上述时间复杂度约束下，不能通过两个映射（一个按键排序，另一个按排名排序）的组合来解决该问题。

谢谢。

Answer 1

给定密钥K的等级是小于或等于K的密钥的数量。

例如，让集合s = {1,3,4,6,9}。
那么rank(1) = 1，rank(4) = 3，rank(9) = 5。STL

函数distance()可用于计算集合s中出现的元素x的排名。

排名 = 距离(s.begin(), s.find(x));

问题是它的时间复杂度是O(n)。

请注意，提出的按键和按排名索引的两个映射（或集）不是正确的解决方案。
问题在于，一个元素的变化会影响许多其他元素的排名。
例如，将元素 0 添加到上面的集合 s 中会更改所有现有元素的排名：
s' = {0, 1, 3, 4, 6, 9}。
排名（1）= 2，排名（4）= 4，排名（9）= 6。

谢谢。

Answer 2

我实现了一个“排名红黑树”，它与红黑树类似，只是每个节点通过有序遍历存储与其前面的节点的距离，而不是存储键。

这正是你想要的，除了第一个节点的“等级”是 0 而不是 1（如果需要，你可以加/减 1）。

我的解决方案是公共域，基于常规红黑树的公共域教程。所有操作（包括插入、删除、查找和确定排名）都具有相对于数据结构中元素数量的对数时间。

您可以在这里找到它：
http://code.google.com/p/options/downloads/list

您应该从上面的链接获取最新版本，当前（截至撰写本文时）为 rrb_v4_release.cpp。

Answer 3

您可以使用其他地图，例如容器。
保留一个大小的字段可以使二叉搜索树易于随机访问。
这是我的实现...
std 样式，随机访问迭代器 ...
大小平衡树...
https://github.com/mm304321141/zzz_lib/blob/master/sbtree。哈
和 B+树 ...
https://github.com/mm304321141/zzz_lib/blob/master/bpptree。哈

Answer 4

我认为排名实际上是指距根的距离，因为如果它可以与值连续存储，则不必达到这样的长度。

我认为你可以“外部”执行此操作，因为在这种情况下，可以根据使用比较谓词的次数推断出排名...

namespace detail
{
  template <class Comparator>
  class CounterComparator: Comparator
  {
  public:
    CounterComparator(size_t& counter):
        Comparator(), mCounter(&counter) {}
    CounterComparator(Comparator comp, size_t& counter):
        Comparator(comp), mCounter(&counter) {}

    template <class T, class U>
    bool operator()(T& lhs, U& rhs) const
    { 
      ++(*mCounter);
      return this->Comparator::operator()(lhs,rhs);
    }
  private:
    size_t* mCounter;
  };
} // namespace detail

template <
  class Key, 
  class Value, 
  class Cmp = std::less<Key>, 
  class Allocator = std::allocator< std::pair<const Key,Value> >
>
class SuperMap
{
  typedef detail::CounterComparator<Cmp> Comparator;
public:
  SuperMap(): mCounter(0), mData(Comparator(mCounter)) {}

  Value& operator[](const Key& key) { return mData[key]; }

  size_t rank(const Key& key) const
  { 
    mCounter = 0; mData.find(key); return mCounter;
  }

private:
  typedef std::map<Key,Value, Comparator, Allocator> data_type;

  mutable size_t mCounter;
  data_type mData;
}; // class SuperMap

int main(int argc, char* argv[])
{
  SuperMap<int,int> superMap;
  superMap[1] = 42;
  std::cout << superMap.rank(1) << std::endl;
}

// outputs
// 2

它计算测试的数量，但由于 std::map 一旦获得正确的密钥就停止测试...应该没问题:)尽管可能有一些偏移量可以推断出（1或2）来获得排名。

如果您对排名给出了更好的定义，我可能会多做一些工作，但我不想在错误的方向上花费太多时间。