自然数表記
木を自然数と一対一対応させる方法。具体的な対応のさせ方は色々考えられるが、現在は四角埋めに落ち着いている。
四角埋め
表
https://gyazo.com/1992fe561959400bab34d255d05d60c0
擬似コード
code:py
def pair(x, y):
m = max(x, y)
return m * (m + 1) + y - x + 1
def unpair(z):
m = floor(sqrt(z - 1))
h = m * (m + 1) + 1
if z < h:
return ( m, m - h + z )
if z == h:
return ( m, m )
if z > h:
return ( m - z + h, m )
メリット
自然数の大きさの順が木の高さの順になっている。
この性質を形態論に利用することができる。
デメリット