Trie

クラス · Trie

template <int alphabet_size = 96, int char_offset = ' '>
struct Trie;

概要

Trie

名前	説明	計算量
`(constructor)`	根だけを持つ空のtrieを構築する	$O(alphabet\_size)$

名前	説明	計算量
`size`	ノード数を返す	$O(1)$
`add`	ノード node_id の子 ch をたどる。無ければ新規作成する。	既存遷移は $O(1)$、新規ノード作成は $O(alphabet\_size)$
`insert`	wordを挿入し各prefixのノードIDを返す	word長を $m$ として $O(m\cdot alphabet\_size)$
`search_id`	wordを表すノードIDを返し、存在しなければ-1を返す	$O(m)$
`get_node`	node_idのノードを返す	$O(1)$

名前	説明	計算量
`node_type`	trieノード型	型エイリアスで実行時計算量はない

int add(int node_id, char ch);

ノード node_id の子 ch をたどる。無ければ新規作成する。