跳转至

平衡樹

__gnu_pbds :: tree

附：官方文檔地址

1
2
3
4
5
6
#include <ext/pb_ds/assoc_container.hpp>  // 因為tree定義在這裏 所以需要包含這個頭文件
#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> >

模板形參

  • Key: 儲存的元素類型，如果想要存儲多個相同的 Key 元素，則需要使用類似於 std::pair 和 struct 的方法，並配合使用 lower_bound 和 upper_bound 成員函數進行查找
  • Mapped: 映射規則（Mapped-Policy）類型，如果要指示關聯容器是 集合，類似於存儲元素在 std::set 中，此處填入 null_type，低版本 g++ 此處為 null_mapped_type；如果要指示關聯容器是 帶值的集合，類似於存儲元素在 std::map 中，此處填入類似於 std::map<Key, Value> 的 Value 類型
  • Cmp_Fn: 關鍵字比較函子，例如 std::less<Key>
  • Tag: 選擇使用何種底層數據結構類型，默認是 rb_tree_tag。__gnu_pbds 提供不同的三種平衡樹，分別是：
    • rb_tree_tag：紅黑樹，一般使用這個，後兩者的性能一般不如紅黑樹
    • splay_tree_tag：splay 樹
    • ov_tree_tag：有序向量樹，只是一個由 vector 實現的有序結構，類似於排序的 vector 來實現平衡樹，性能取決於數據想不想卡你
  • Node_Update：用於更新節點的策略，默認使用 null_node_update，若要使用 order_of_key 和 find_by_order 方法，需要使用 tree_order_statistics_node_update
  • Allocator：空間分配器類型

構造方式

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;

成員函數

  • insert(x)：向樹中插入一個元素 x，返回 std::pair<point_iterator, bool>。
  • erase(x)：從樹中刪除一個元素/迭代器 x，返回一個 bool 表明是否刪除成功。
  • order_of_key(x)：返回 x 以 Cmp_Fn 比較的排名。
  • find_by_order(x)：返回 Cmp_Fn 比較的排名所對應元素的迭代器。
  • lower_bound(x)：以 Cmp_Fn 比較做 lower_bound，返回迭代器。
  • upper_bound(x)：以 Cmp_Fn 比較做 upper_bound，返回迭代器。
  • join(x)：將 x 樹併入當前樹，前提是兩棵樹的類型一樣，x 樹被刪除。
  • split(x,b)：以 Cmp_Fn 比較，小於等於 x 的屬於當前樹，其餘的屬於 b 樹。
  • empty()：返回是否為空。
  • size()：返回大小。

示例

 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
// Common Header Simple over C++11
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
#define pb push_back
#define mp make_pair
#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(mp(1, cnt++));
  trr.insert(mp(5, cnt++));
  trr.insert(mp(4, cnt++));
  trr.insert(mp(3, cnt++));
  trr.insert(mp(2, cnt++));
  // 樹上元素 {{1,0},{2,4},{3,3},{4,2},{5,1}}
  auto it = trr.lower_bound(mp(2, 0));
  trr.erase(it);
  // 樹上元素 {{1,0},{3,3},{4,2},{5,1}}
  auto it2 = trr.find_by_order(1);
  cout << (*it2).first << endl;
  // 輸出排名 0 1 2 3 中的排名 1 的元素的 first:1
  int pos = trr.order_of_key(*it2);
  cout << pos << endl;
  // 輸出排名
  decltype(trr) newtr;
  trr.split(*it2, newtr);
  for (auto i = newtr.begin(); i != newtr.end(); ++i) {
    cout << (*i).first << ' ';
  }
  cout << endl;
  // {4,2},{5,1} 被放入新樹
  trr.join(newtr);
  for (auto i = trr.begin(); i != trr.end(); ++i) {
    cout << (*i).first << ' ';
  }
  cout << endl;
  cout << newtr.size() << endl;
  // 將 newtr 樹併入 trr 樹，newtr 樹被刪除。
  return 0;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用