Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Order Statistic Tree in C++

Tags:

I need an order statistic tree for standard GCC STL map containers.

I checked and there is something known as PBDS. Policy based data structures. That usage is also not clear to me.

Anyone can tell me how to use STL map containers for order statistic tree? Even if its only on GNU G++ its enough?

like image 988
user1486288 Avatar asked Jun 27 '12 16:06

user1486288


People also ask

What is an order statistic Tree explain and give an example?

In computer science, an order statistic tree is a variant of the binary search tree (or more generally, a B-tree) that supports two additional operations beyond insertion, lookup and deletion: Select(i) – find the i'th smallest element stored in the tree.

What is the order tree?

order tree (plural order trees) (topology) A set that is the union of subsets (called segments), each of which is totally ordered, such that the segments fit together a certain way.

What is order statistics DAA?

"Order statistics" is a fancy name for "K-th element of an N-element sequence sorted in ascending order". The rest of the slide simply illustrates the idea, explaining that 1-order statistics is the smallest element in a sequence, n-order statistics is the largest element, n/2 order statistics is the median, and so on.

Which features should be supported by every node of order static tree?

It should support four operations: Insert, Delete, Select and Rank.


1 Answers

Here is the example of GNU Policy-Based STL MAP implemented as order statistic tree (tested on Linux gcc 4.6.1):

#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef
tree<
  int,
  int,
  less<int>,
  rb_tree_tag,
  tree_order_statistics_node_update>
map_t;

int main()
{
  map_t s;
  s.insert(make_pair(12, 1012));
  s.insert(make_pair(505, 1505));
  s.insert(make_pair(30, 1030));
  cout << s.find_by_order(1)->second << '\n';
  return 0;
}

Here is a link to the overview of GNU Policy-Based Data Structures. Here is other tree_order_statistics example. I cannot find a good reference for Policy-Based Data Structures, but you can use these links as well as PBDS sources.

like image 61
Evgeny Kluev Avatar answered Dec 15 '22 03:12

Evgeny Kluev