順序木の右枝分解
https://gyazo.com/593c51247733e3ea85187bbd4d3dd6b0
ref. 『部分語計数問題の接尾辞配列を用いた高速アルゴリズム』PDF
明示的に接尾辞木を構築することなく接尾辞木の深さ優先、帰りがけ順での全探索を実現する
この「木を明示的に構築することなく」が重要
既に木が構築されてるなら素直に探索すれば良いだけなので。
論文では後置順巡回と呼んでる
二頂点の親子関係と、隣り合う葉との最近共通先祖が与えられるなら後置順巡回ができる
接尾辞配列の場合「開始点と長さの対」で木の頂点が表現できる
葉は文字列末までの長さを持つ
wがvの先祖であるならば、wの長さがvよりも小さい
逆は必ずしも真ではないけど、最近共通祖先との間での比較しかしないのでOK
最近共通先祖は長さをLCP arrayであらかじめ計算しておいたものに変えれば得られる
論文では「高さ」と表現されている
いわゆる木の高さなどとは関係ない
code:python
def test_travase_tree():
"""
>> test_travase_tree()
6, 1
* 1
6
6, 3
6, 3, 2
* 2
6, 3
* 3
6
6, 5
6, 5, 4
* 4
6, 5
* 5
6
* 6
[]
"""
ROOT = 0
TOP = 6
parent = TOP, 3, 3, 5, 5, 0, TOP
leafs = 1, 2, 4
stack = TOP
nearest_common_ancestors = None, 3, 5, None, 6, None
def is_ancestor_of(anc, x):
while True:
x = parentx
if x == anc:
return True
if x == 6:
return False
for leaf in leafs:
stack.append(leaf)
print(stack)
v = stack-1
w = nearest_common_ancestorsleaf
while is_ancestor_of(w, v):
print("*", v)
stack.pop()
print(stack)
if not stack:
return
v = stack-1
if v != w and is_ancestor_of(v, w):
stack.append(w)
print(stack)