C++中的排名树 [英] Rank Tree in C++
问题描述
我们需要具有搜索和排名功能的 ADT.即除了STL map的接口外，还需要一个函数'int get_rank(key)'.
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 map/set 并没有这样做.
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、Boost)的解决方案，具有最佳的时间复杂度:查找/添加/删除元素需要 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).
通过一个元素的等级，我们指的是该元素在map/set中所有元素的排序序列中的位置.
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}rank(0)=1，rank(4)=2，rank(6)=3，rank(7)=4，rank(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}.然后rank(1) = 1, rank(4) = 3, rank(9) = 5.
E.g., let set s = {1, 3, 4, 6, 9}. Then rank(1) = 1, rank(4) = 3, rank(9) = 5.
STL 函数 distance() 可用于计算出现在集合 s 中的元素 x 的秩.
The STL function distance() can be used for computing the rank of an element x appearing in the set s.
rank = distance(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屋！
