Skip to content

Balanced Trees

__gnu_pbds::tree

Attached: Official Documentation Link

1
2
3
4
5
6
#include <ext/pb_ds/assoc_container.hpp>  // Because tree is defined here, this header must be included
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
__gnu_pbds::tree<Key, Mapped, Cmp_Fn = std::less<Key>, Tag = rb_tree_tag,
                 Node_Update = null_tree_node_update,
                 Allocator = std::allocator<char>>

Template Parameters

  • Key: The type of elements stored. To store multiple identical Key elements, you need to use methods similar to std::pair and struct, and use the lower_bound and upper_bound member functions for searching.
  • Mapped: The mapping rule (Mapped-Policy) type. To indicate that the associative container is a set, similar to storing elements in std::set, fill in null_type here (for older g++ versions, use null_mapped_type). To indicate that the associative container is a set with values, similar to storing elements in std::map, fill in a Value type like std::map<Key, Value>.
  • Cmp_Fn: The key comparison functor, e.g., std::less<Key>.
  • Tag: Selects the underlying data structure type. The default is rb_tree_tag. __gnu_pbds provides three different balanced trees:
    • rb_tree_tag: Red-black tree. Generally use this one; the performance of the other two is usually not as good as the red-black tree.
    • splay_tree_tag: Splay tree.
    • ov_tree_tag: Ordered vector tree. It's just an ordered structure implemented by vector, similar to using a sorted vector to implement a balanced tree. Performance depends on whether the data tries to exploit its weaknesses.
  • Node_Update: The policy for updating nodes. The default is null_node_update. To use the order_of_key and find_by_order methods, you need to use tree_order_statistics_node_update.
  • Allocator: The memory allocator type.

Construction

1
2
3
4
__gnu_pbds::tree<std::pair<int, int>, __gnu_pbds::null_type,
                 std::less<std::pair<int, int>>, __gnu_pbds::rb_tree_tag,
                 __gnu_pbds::tree_order_statistics_node_update>
    trr;

Member Functions

  • insert(x): Inserts an element x into the tree. Returns std::pair<point_iterator, bool>, where the first element is an iterator pointing to the insertion position, and the second element indicates whether the insertion was successful.
  • erase(x): Deletes an element/iterator x from the tree. If x is an iterator, it returns an iterator pointing to the element after x (returns end() if x is end()). If x is a Key, it returns whether the deletion was successful (fails if the element does not exist).
  • order_of_key(x): Returns the number of elements strictly less than x (using Cmp_Fn as the comparison logic), i.e., the rank starting from \(0\).
  • find_by_order(x): Returns the iterator corresponding to the element with the rank x according to the Cmp_Fn comparison.
  • lower_bound(x): Returns an iterator pointing to the first element not less than x (using Cmp_Fn as the comparison logic).
  • upper_bound(x): Returns an iterator pointing to the first element strictly greater than x (using Cmp_Fn as the comparison logic).
  • join(x): Merges tree x into the current tree. Tree x is cleared (must ensure the comparison functions and element types of both trees are identical).
  • split(x,b): Using Cmp_Fn for comparison, elements less than or equal to x belong to the current tree, and the rest belong to tree b.
  • empty(): Returns whether the tree is empty.
  • size(): Returns the size.
Note

The join(x) function requires that the key value range of the tree being merged and the key value range of the tree being merged into are disjoint (i.e., all values in the merging tree must be either all greater than or all less than all values in the current tree). Otherwise, a join_error exception will be thrown.

To merge two trees with overlapping value ranges, you need to insert the elements of one tree one by one into the other tree.

Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// Common Header Simple over C++11
#include <iostream>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
__gnu_pbds::tree<pair<int, int>, __gnu_pbds::null_type, less<pair<int, int>>,
                 __gnu_pbds::rb_tree_tag,
                 __gnu_pbds::tree_order_statistics_node_update>
    trr;

int main() {
  int cnt = 0;
  trr.insert(make_pair(1, cnt++));
  trr.insert(make_pair(5, cnt++));
  trr.insert(make_pair(4, cnt++));
  trr.insert(make_pair(3, cnt++));
  trr.insert(make_pair(2, cnt++));
  // Tree elements: {(1,0), (2,4), (3,3), (4,2), (5,1)}

  auto it = trr.lower_bound(make_pair(2, 0));
  trr.erase(it);
  // Tree elements: {(1,0), (3,3), (4,2), (5,1)}

  // Output the 'first' of the element with rank 1 among ranks 0, 1, 2, 3
  auto it2 = trr.find_by_order(1);
  cout << (*it2).first << endl;  // Output: 3

  // Output its rank
  int pos = trr.order_of_key(*it2);
  cout << pos << endl;  // Output: 1

  // Split trr according to it2
  decltype(trr) newtr;
  trr.split(*it2, newtr);
  for (auto i = newtr.begin(); i != newtr.end(); ++i) {
    cout << (*i).first << ' ';  // Output: 4 5
  }
  cout << endl;

  // Merge newtr tree into trr tree. newtr tree is cleared.
  trr.join(newtr);
  for (auto i = trr.begin(); i != trr.end(); ++i) {
    cout << (*i).first << ' ';  // Output: 1 3 4 5
  }
  cout << endl;
  cout << newtr.size() << endl;  // Output: 0

  return 0;
}

References

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用