Binary Trie
(DataStructure/misc/BinaryTrie.py)

• View this file on GitHub
• Last update: 2021-02-05 19:21:17+09:00

概要

Trie 構造で非負整数を管理するデータ構造。

使い方

BinaryTrie(MAX_BIT_LENGTH=32)
空の集合を構築する。集合に格納できる 2 進数での最大桁数を MAX_BIT_LENGTH (これを $\sigma$ とする) で指定する。計算量 $O(1)$

• search(val: int) -> bool
val が集合に属しているか返す。計算量 $O(\sigma)$

• insert(val: int) -> bool
  集合に val を追加する。追加に成功した場合は True を、失敗した場合 (既に val が集合に属していた場合) は False を返す。計算量 $O(\sigma)$

• delete() -> int
  集合から val を削除する。削除に成功した場合は True を、失敗した場合 (val が集合に属していなかった場合) は False を返す。計算量 $O(\sigma)$

• get_xor_min(xor_val: int) -> int
  集合内の要素と xor_val との bitwise-xor をとった場合に考えられる最小値を返す。計算量 $O(\sigma)$

Verified with

• TestCase/LibraryChecker/set_xor_min.test.py

Code

class BinaryTrieNode:
    def __init__(self):
        self.bit0 = None
        self.bit1 = None
        self.size = 0


class BinaryTrie:
    def __init__(self, MAX_BIT_LENGTH=32):
        self.MAX_BIT_LENGTH = MAX_BIT_LENGTH
        self.root = BinaryTrieNode()

    def _generate_bit(self, val):
        for i in reversed(range(self.MAX_BIT_LENGTH)):
            yield (val >> i) & 1

    def search(self, val: int) -> bool:
        ptr = self.root
        for bit in self._generate_bit(val):
            if bit:
                ptr = ptr.bit1
            else:
                ptr = ptr.bit0
            if ptr is None:
                return False
        return True

    def insert(self, val: int) -> bool:
        if self.search(val):
            return False
        ptr = self.root
        ptr.size += 1
        for bit in self._generate_bit(val):
            if bit:
                if ptr.bit1 is None:
                    ptr.bit1 = BinaryTrieNode()
                ptr = ptr.bit1
            else:
                if ptr.bit0 is None:
                    ptr.bit0 = BinaryTrieNode()
                ptr = ptr.bit0
            ptr.size += 1
        return True

    def delete(self, val: int) -> bool:
        if not self.search(val):
            return False
        ptr = self.root
        ptr.size -= 1
        for bit in self._generate_bit(val):
            if bit:
                if ptr.bit1.size == 1:
                    ptr.bit1 = None
                    return True
                ptr = ptr.bit1
            else:
                if ptr.bit0.size == 1:
                    ptr.bit0 = None
                    return True
                ptr = ptr.bit0
            ptr.size -= 1
        return True

    def get_xor_min(self, xor_val: int) -> int:
        ptr = self.root
        res = 0
        i = self.MAX_BIT_LENGTH
        for bit in self._generate_bit(xor_val):
            i -= 1
            if bit:
                if ptr.bit1 is not None:
                    ptr = ptr.bit1
                else:
                    ptr = ptr.bit0
                    res |= 1 << i
            else:
                if ptr.bit0 is not None:
                    ptr = ptr.bit0
                else:
                    ptr = ptr.bit1
                    res |= 1 << i
        return res

Traceback (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

Back to top page