Treap
Abstract
非再帰版のTreapを実装した.
Explanation
TODO そのうち書く.
Implementation
Treap クラスでは, 頂点をリストにより表記している: 最初は頂点をクラス化して実装したけど, 遅かった......
リストの0, 1番の要素がそれぞれ左の子, 右の子.
2番目の要素が格納されている値.
3番目の要素が優先度.
4番目の要素が子孫の数.
5番目の要素が子孫の値の総和.
Treapの現在の根の頂点 (リスト) が Treap.root に格納されている.
Insert/Eraseベースで非再帰で実装をした. このため, 木の回転操作 (Treap._rotate) が必要になる. Merge/Splitベースの実装をしたほうが, 木の回転が必要なかったりと, 実装はもう少し楽にできるようだ.
Treapの構築
Input
比較可能なオブジェクトからなるイテラブル iterable (空でもよい)
Output
イテラブルの要素を格納したTreap Treap(iterable)
Time complexity
イテラブルの長さを$ Nとすると,
イテラブルが空のとき$ O(1)time,
そうでないとき, insert操作を繰り返すことで, expected$ O(N \log N)time.
Insert操作
Input
Treapに新たに格納する要素 key
Output
なし.
Time complexity
現在のTreapの要素数を$ Nとすると, expected$ O(\log N)time.
Delete操作
Input
Treapから消去する要素 key
Output
なし.
key がTreap内にある場合, key の要素は消去される.
そうでないときは, 何もしない.
Time complexity
現在のTreapの要素数を$ Nとすると, expected$ O(\log N)time.
Merge操作
Input
Treap other
other の要素は, すべてMergeするTreapの要素の最大値以上でなければならない.
そうでないと, Merge結果がTreapにならない.
Split操作の逆操作.
Output
併合してできるTreap Treap.merge(other)
Time complexity
現在のTreapの要素数を$ N_1, other の要素数を$ N_2とし, $ N = \max(N_1, N_2), ~ M = \min(N_1, N_2)とすると, expected$ O ( M \log (N / M))time.
Merge操作
Input
Splitする位置$ k
Output
$ k番目に小さい要素より大きい要素からなるTreap Treap.split(k)
もとのTreapには, $ k番目に小さい要素以下の要素のみ含まれるようになる.
Time complexity
現在のTreapの要素数を$ Nとすると, expected$ O ( \log N)time.
Top操作
Input
なし.
Output
Treap内の最小要素 val
Time complexity
$ O(1)time.
Search操作
Input
要素 x
Output
要素 x がTreapに含まれているかのBool値 x in Treap
Time complexity
二分探索になる. 現在のTreapの要素数を$ Nとすると, expected$ O(\log N)time. 要素数の確認
Input
なし.
Output
Treap内の要素数 len(Treap)
Time complexity
$ O(1)time.
$ k番目の要素の取得
Input
位置 k
Output
Treap内で k 番目に小さい要素 Treap[k].
Time complexity
二分探索になる. 現在のTreapの要素数を$ Nとすると, expected$ O(\log N)time. Sort操作
Input
なし.
Output
Treap内の要素をソートしたリスト lst
Time complexity
深さ優先探索をしながら中行順序で要素を拾えばよい. 現在のTreapの要素数を$ Nとすると,$ O(N)time. Bisect操作
Input
要素 x
Output
要素 x 以下の要素がTreap内にいくつ含まれているか i.
Pythonのbisect.bisect と同じ.
Time complexity
二分探索になる. 現在のTreapの要素数を$ Nとすると, expected$ O(\log N)time. Treapの木構造の可視化
Input
なし.
Output
Treapの現在の状態を表した文字列
print(Treap) のようにすれば幅優先探索順で表示される (子が無いところは None を表示). Time complexity
抽象化した実装もできるらしいが, やってない.
code:python
from random import random
from collections import deque
from copy import deepcopy
class Treap:
def __init__(self, iterable=None):
self.root = None
if iterable: self._construct(iterable)
def _construct(self, iterable):
for it in iterable: self.insert(it)
def __len__(self): return self._count(self.root)
@staticmethod
def _count(v): return v4 if v is not None else 0 def _rotate(self, v, direction): # rotate the vertex v to the given direction
# update vertex's information
n_desc, sum_desc = c4: = v4: v4: = n_desc - 1 - self._count(t), sum_desc - (c2 if c2 else 0) - (t5 if t else 0) return c # new parent
def __contains__(self, key): # check whether the given key is in the treap
if self.root is None: return False
v = self.root
while v:
if k == key: return True
v = vkey > k # key > v2 -> v = v1 (right child) return False
def __getitem__(self, i): # get the i-th smallest element in the treap
count = self._count
if i < 0: i = count(self.root) + i
if i >= count(self.root) or i < 0: raise IndexError
v = self.root
while True:
if i == n_left: return v2 elif i > n_left: i -= n_left + 1; v = v1 def __repr__(self): # visualize the treap
if not self.root: return 'Treap([])'
elements = []
while q:
v = q.popleft()
if v is None: elements.append(v); continue
elements.append((v2, v3)) q.append(v0); q.append(v1) return 'Treap({})'.format(str(elements))
@classmethod
def _treap(cls, treapnode):
tp = cls(); tp.root = deepcopy(treapnode)
return tp
def sort(self):
if not self.root: return []
elements = []
while stack:
v, st = stack.pop()
if st == 0:
if right: stack.append((right, 0))
stack.append((v, 1))
if left: stack.append((left, 0))
if st == 1: elements.append(k)
return elements
def bisect(self, key): # bisect_right
if self.root is None: return 0
v = self.root; idx = 0
count = self._count
while v:
left, right, k, _, _, _ = v
if key >= k: idx += count(left) + 1; v = right
else: v = left
return idx
def insert(self, key, priority=None):
if priority is None: priority = random()
rotate = self._rotate
v = self.root; p = None; direction = None
stack = []
while v:
stack.append((v, direction))
while stack:
p, direction = stack.pop()
p4 += 1; p5 += key # update vertex's information v = rotate(p, 1 - direction)
else: self.root = v
for p, _ in stack: p4 += 1; p5 += key # update vertex's information return self.root
def delete(self, key):
v = self.root; p = None; direction = None
stack = []
while v:
if key == v2: break # vertex to be deleted has been found stack.append((v, direction))
else: return self.root # the given key is not in the treap
rotate = self._rotate
while v0 or v1: # while v is not a leaf left, right, _, _, _, _ = v
direction = (left3 > right3) if left and right else (right is None) p = rotate(v, direction)
v = None # delete
while stack:
p, direction = stack.pop()
p4 -= 1; p5 -= (key if key else 0) # update vertex's information v = p
self.root = v
return self.root
def merge(self, other):
r, o = self.root, other.root
temp_v = [r, o, None, float('inf'), 1 + r4 + o4, float('inf')] virtual = self._treap(temp_v)
self.root = virtual.delete(None)
return self.root
def split(self, i):
INF = float('inf')
count = self._count
if i < 0: i = count(self.root) + i
if i >= count(self.root) or i < 0: raise IndexError
rotate = self._rotate
v = self.root; p = None; direction = None
stack = []
while v:
direction = (i > n_left)
stack.append((v, direction))
if direction: i -= n_left + 1
while stack:
p, direction = stack.pop()
p4 += 1; p5 += 0 # update vertex's information v = rotate(p, 1 - direction)
self.root = l
return self._treap(r)
Verification
References