Neterukun's Library
This documentation is automatically generated by online-judge-tools/verification-helper
順序付き集合 (AA Tree)
(DataStructure/SortedSet/SortedSetAATree.py)
- View this file on GitHub
- Last update: 2021-05-12 01:32:34+09:00
概要
AA Tree による順序付き集合。B-Tree による実装の方が高速なのでそちらを使いましょう。
使い方
SortedSetAATree()
空の順序付き集合を作成する。計算量 $O(1)$
-
__contains__(key: int) -> bool
要素keyが集合に属しているかどうかを返す。計算量 $O(\log N)$ -
__len__() -> int
集合の大きさを返す。計算量 $O(1)$ -
__iter__() -> Iterator[int]
要素の小さい順のイテレータオブジェクトを返す。イテレーション $1$ 回の計算量 $O(\log N)$。全 $N$ 要素のイテレーションの計算量 $O(N)$ -
add(key: int) -> bool
要素keyを集合に追加する。追加に成功した場合はTrueを、失敗した場合 (既にkeyが集合に属していた場合) はFalseを返す。計算量 $O(\log N)$ -
remove(key: int) -> bool
集合からkeyを削除する。削除に成功した場合はTrueを、失敗した場合 (keyが集合に属していなかった場合) はFalseを返す。計算量 $O(\log N)$ -
iterate(lower: int) -> Iterator[int]
lower以上の要素に対して、小さい順のイテレータオブジェクトを返す。イテレーション $1$ 回の計算量 $O(\log N)$。全 $k$ 要素のイテレーションの計算量 $O(k + \log N)$ -
next_val(lower: int) -> int
lower以上の最小の要素を返す。そのような要素が存在しない場合はNoneを返す。計算量 $O(\log N)$ -
prev_val(upper: int) -> int
upperよりも小さい最大の要素を返す。そのような要素が存在しない場合はNoneを返す。計算量 $O(\log N)$
Verified with
Code
class AANode:
Nil = None
def __init__(self, key):
self.key = key
self.lv = 1
self.l, self.r, self.p = self.Nil, self.Nil, self.Nil
def skew(self):
if self.l.lv == self.lv:
pv = self._rotr()
return pv
return self
def split(self):
if self.r.r.lv == self.lv:
pv = self._rotl()
pv.lv += 1
return pv
return self
def skew_split(self):
pv = self
if pv.l.lv == pv.lv:
pv = pv._rotr()
if pv.r.r.lv == pv.lv:
pv = pv._rotl()
pv.lv += 1
return pv
def _rotl(self):
pv = self.r
pv.p = self.p
if pv.p is not self.Nil:
if pv.p.l is self: pv.p.l = pv
else: pv.p.r = pv
self.r = pv.l
if self.r is not self.Nil: self.r.p = self
self.p = pv
pv.l = self
return pv
def _rotr(self):
pv = self.l
pv.p = self.p
if pv.p is not self.Nil:
if pv.p.r is self: pv.p.r = pv
else: pv.p.l = pv
self.l = pv.r
if self.l is not self.Nil: self.l.p = self
self.p = pv
pv.r = self
return pv
class SortedSetAATree:
Nil = AANode(-1)
AANode.Nil = Nil
Nil.lv = 0
Nil.l, Nil.r, Nil.p = Nil, Nil, Nil
def __init__(self):
self.root = self.Nil
self.size = 0
def __contains__(self, key):
return self._search(key)
def __len__(self):
return self.size
def __iter__(self):
def dfs(nd):
if nd.l is not self.Nil:
yield from dfs(nd.l)
yield nd.key
if nd.r is not self.Nil:
yield from dfs(nd.r)
if self.root is not self.Nil:
yield from dfs(self.root)
def _search(self, key):
nd = self.root
while nd is not self.Nil:
if nd.key < key: nd = nd.r
elif nd.key > key: nd = nd.l
else: return True
return False
def _balance_del(self, nd):
while nd is not self.Nil:
if nd.l.lv < nd.lv - 1 or nd.r.lv < nd.lv - 1:
nd.lv -= 1
if nd.r.lv > nd.lv:
nd.r.lv = nd.lv
nd = nd.skew()
nd.r = nd.r.skew()
nd.r.r = nd.r.r.skew()
nd = nd.split()
nd.r = nd.r.split()
self.root = nd
nd = nd.p
def add(self, key):
if self.root is self.Nil:
self.root = AANode(key)
self.size += 1
return True
nd = self.root
while nd is not self.Nil:
if nd.key < key:
if nd.r is self.Nil:
nd.r = AANode(key)
self.size += 1
nd.r.p = nd
if nd.lv + 1 == nd.p.lv:
return True
break
nd = nd.r
elif nd.key > key:
if nd.l is self.Nil:
nd.l = AANode(key)
self.size += 1
nd.l.p = nd
break
nd = nd.l
else: return False
while nd is not self.Nil:
nd = nd.skew_split()
self.root = nd
nd = nd.p
return True
def remove(self, key):
if self.root is self.Nil: return False
nd = self.root
while nd is not self.Nil:
if nd.key < key: nd = nd.r
elif nd.key > key: nd = nd.l
else: break
else: return False
self.size -= 1
if nd.l is not self.Nil and nd.r is not self.Nil:
min_nd = nd.r
while min_nd.l is not self.Nil:
min_nd = min_nd.l
nd.key = min_nd.key
nd = min_nd
chi_nd = nd.r if nd.r is not self.Nil else nd.l
if nd is self.root:
self.root = chi_nd
if self.root is not self.Nil: self.root.p = self.Nil
return True
elif nd.p.r is nd:
nd.p.r = chi_nd
if chi_nd is not self.Nil: chi_nd.p = nd.p
else:
nd.p.l = chi_nd
if chi_nd is not self.Nil: chi_nd.p = nd.p
self._balance_del(nd.p)
return True
def iterate(self, lower):
def dfs(nd):
if nd.l is not self.Nil and (nd.key > lower):
yield from dfs(nd.l)
if nd.key >= lower:
yield nd.key
if nd.r is not self.Nil:
yield from dfs(nd.r)
if self.root is not self.Nil:
yield from dfs(self.root)
def next_key(self, lower):
nd = self.root
ret = None
while nd is not self.Nil:
if nd.key >= lower:
ret = nd.key
nd = nd.l
else: nd = nd.r
return ret
def prev_key(self, upper):
nd = self.root
ret = None
while nd is not self.Nil:
if nd.key < upper:
ret = nd.key
nd = nd.r
else: nd = nd.l
return retTraceback (most recent call last):
File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
raise NotImplementedError
NotImplementedError