排名树在C ++ [英] Rank Tree in C++

问题描述

我们需要有搜索和排序功能ADT。
也就是说，除了为STL地图的界面，函数'诠释get_rank（密钥）是必需的。

We need ADT having search and rank features. That is, in addition to the interface of STL map, a function 'int get_rank(key)' is required.

标准执行这种功能的需要支持和自平衡搜索树（例如，在黑红色的树，以STL地图/一套采用）的每个节点更新一个额外的整数字段。
但似乎，STL地图/套不这样做。

Standard implementation of such function requires supporting and updating an extra integer field in every node of self-balanced searching tree (e.g., in black-red tree, used in STL map/set). But it seems, STL map/set do not do this.

我们正在基于具有最佳的时间复杂度标准箱（STL，升压）寻找一个解决方案：
  发现/添加/删除元素采取O（log n）的（如在STL地图/套），
  通过计算一个关键的排名也需要O（log n）的。

We're looking for a solution based on standard containers (STL, Boost) having the best possible Time Complexity: finding/adding/erasing an element take O(log n) (like in STL map/set), computing the rank by a key takes also O(log n).

通过元素的等级，我们指的是元件的地图/组中的所有元素的排序序列中的位置。

By the rank of an element, we mean the position of the element in the sorted sequence of all the elements of the map/set.

为例。
  设定= {0，4，6，7，8}
  等级（0）= 1，秩（4）= 2，秩（6）= 3，秩（7）= 4，秩（8）= 5。

Example. set = {0, 4, 6, 7, 8} rank(0)=1, rank(4)=2, rank(6)=3, rank(7)=4, rank(8)=5.

在我们看来，根据时间复杂度以上约束，该问题不能由秩两个地图一个分类由键和其它的排序的组合解决。

In our opinion, under Time Complexity constrains above, the problem cannot be solved by a combination of two maps one sorting by key and other sorting by rank.

感谢。

推荐答案

给定的密钥K的秩这是小于或等于k键的数量。

The rank of the given key K is the number of keys which are less or equal to K.

如，让组S = {1，3，4，6，9}。
然后，秩（1）= 1，秩（4）= 3，秩（9）= 5。

E.g., let set s = {1, 3, 4, 6, 9}. Then rank(1) = 1, rank(4) = 3, rank(9) = 5.

的STL函数距离（）可以被用于计算一个元素的等级点¯x出现在该组第

The STL function distance() can be used for computing the rank of an element x appearing in the set s.

秩=距离（s.begin（），s.find（X））;

rank = distance(s.begin(), s.find(x));

的问题是，它的时间复杂度是O（n）的

The problem is that its time complexity is O(n).

注意，建议重点和收录排名两个地图（或一组）是不正确的解决方案。
问题是，一个元素的改变会影响许多人的行列。
例如，添加元素0到集合S以上变化的所有现有元素的行列：
s'的= {0，1，3，4，6，9}。
等级（1）= 2，秩（4）= 4，秩（9）= 6。

Note that proposed two maps (or sets) indexed by key and by rank is not correct solution. The problem is that a change of one element affects ranks of many others. E.g., adding element 0 to the set s above change the ranks of all existing elements: s' = {0, 1, 3, 4, 6, 9}. rank(1) = 2, rank(4) = 4, rank(9) = 6.

感谢。

这篇关于排名树在C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！