Tree64

クラス · 64要素以下のTree64終端層

template <int N>
struct Tree64;

概要

64分木

計算量

各操作 $O(\log_{64}N)$

構築・破棄

名前	説明	計算量
`(constructor)`	空集合を構築する	(1) $O(\log_{64}N)$ (2) $O(1)$

メンバ関数

名前	説明	計算量
`insert`	keyを挿入し、新規挿入ならtrueを返す	(1) $O(\log_{64}N)$ (2) $O(1)$
`erase`	keyを削除し、存在したならtrueを返す	(1) $O(\log_{64}N)$ (2) $O(1)$
`contains`	keyを含むか返す	(1) $O(\log_{64}N)$ (2) $O(1)$
`min`	最小要素を返す	(1) $O(\log_{64}N)$ (2) $O(1)$
`max`	最大要素を返す	(1) $O(\log_{64}N)$ (2) $O(1)$
`pred`	key未満で最大の要素を返し、無ければ-1を返す	(1) $O(\log_{64}N)$ (2) $O(1)$
`succ`	key以上で最小の要素を返し、無ければ-1を返す	(1) $O(\log_{64}N)$ (2) $O(1)$
`get_map`	(1) 直下の子が空でないことを表すbit maskを返す (2) 要素集合をbit maskで返す	$O(1)$

メンバの詳細

(constructor)

// (1)
Tree64();

// (2)
Tree64();

(1) 空集合を構築する

計算量: $O(\log_{64}N)$

(2) 空集合を構築する

計算量: $O(1)$

insert

// (1)
bool insert(const int key);

// (2)
bool insert(const int key);

(1) keyを挿入し、新規挿入ならtrueを返す

計算量: $O(\log_{64}N)$

(2) keyを挿入し、新規挿入ならtrueを返す

計算量: $O(1)$

erase

// (1)
bool erase(const int key);

// (2)
bool erase(const int key);

(1) keyを削除し、存在したならtrueを返す

計算量: $O(\log_{64}N)$

(2) keyを削除し、存在したならtrueを返す

計算量: $O(1)$

contains

// (1)
bool contains(const int key) const;

// (2)
bool contains(const int key) const;

(1) keyを含むか返す

計算量: $O(\log_{64}N)$

(2) keyを含むか返す

計算量: $O(1)$

min

// (1)
int min() const;

// (2)
int min() const;

(1) 最小要素を返す

計算量: $O(\log_{64}N)$

(2) 最小要素を返す

計算量: $O(1)$

max

// (1)
int max() const;

// (2)
int max() const;

(1) 最大要素を返す

計算量: $O(\log_{64}N)$

(2) 最大要素を返す

計算量: $O(1)$

pred

// (1)
int pred(const int key) const;

// (2)
int pred(const int key) const;

(1) key未満で最大の要素を返し、無ければ-1を返す

計算量: $O(\log_{64}N)$

(2) key未満で最大の要素を返し、無ければ-1を返す

計算量: $O(1)$

succ

// (1)
int succ(const int key) const;

// (2)
int succ(const int key) const;

(1) key以上で最小の要素を返し、無ければ-1を返す

計算量: $O(\log_{64}N)$

(2) key以上で最小の要素を返し、無ければ-1を返す

計算量: $O(1)$

get_map

// (1)
std::uint64_t get_map() const;

// (2)
std::uint64_t get_map() const;

(1) 直下の子が空でないことを表すbit maskを返す

計算量: $O(1)$

(2) 要素集合をbit maskで返す

計算量: $O(1)$