pb_ds Red–black tree

pb_ds Red–black tree

含 入 下 列 兩 函 式 庫:

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

宣 告 方 式:

__gnu_pbds::tree< Value_Type, null_type, Cmp_Fn, Tag, Node_Update > pq;

Value_Type 是 儲 存 類 型。

Cmp_Fn 是 比 較 方 法，默 認 是 std::less。

Tag 有

• rb_tree_tag
• splay_tree_tag
• ov_tree_tag

一 般 來 講 rb_tree_tag 是 最 好 的。

Node_Update 是 更 新 保 存 節 點 信 息，有

• null_node_update
• tree_order_statistics_node_update

一 般 會 使 用 tree_order_statistics_node_update，因 為可 以 多 使 用 find_by_order() 及 order_of_key 兩 種 函 式，不 然 就 跟 STL set 一 樣 了。

tree 的 方 法 也 跟 STL set 一 樣。

多 了 find_by_order()、order_of_key()，少 了emplace

• find_by_order( k ): 查 詢 第 k + 1 小 的 數，回 傳 值 為 迭 代 器。
  如 果 查 詢 不 成 功 則 回 傳 tree.end()
• order_of_key( k ): 查 詢 k 在 此 樹 是 第 幾 個 元 素。

code demo: