Top Tree の構造の変種 - noshi91のメモ

注意: 雑です

概要

[1] で定義された top tree は、葉が underlying tree の辺に対応するなどの条件があります。 [2] は splay tree をベースにした top tree を説明しています。 [1] の定義にはわずかに合致しないものの、いくらかの良い性質を持つ構造を思いついたので、本記事で説明します。

本文

link cut tree に類似した構造になっていて、根付き木を管理します。各辺は solid と dashed の 2 状態のいずれかであり、各頂点について子とをつなぐ辺の内 solid なものは高々 $1$ 本とするのも link cut tree と同様です。

link cut tree と異なるところは

solid edge からなるパスを管理する二分探索木
- link cut tree: $P$ を頂点の列と見て、 $P$ の頂点が $\mathcal{C}$ の頂点と $1$ 対 $1$ 対応する。
- 提案手法: $P$ を頂点と辺の列と見て、 $P$ の頂点が $\mathcal{C}$ の葉に、 $P$ の辺が $\mathcal{C}$ の内部ノードに $1$ 対 $1$ 対応する。
頂点に連なる dashed edge の管理
- link cut tree: それぞれの dashed edge から $v$ (に対応する $\mathcal{C}$ の頂点) へポインタを張る。
- 提案手法: 二分探索木 $\mathcal{R}$ で dashed edge を管理する。各 dashed edge と $\mathcal{R}$ の頂点が $1$ 対 $1$ 対応する。 $\mathcal{R}$ の頂点は middle child として dashed edge の先の部分木を管理する木構造の根へポインタを張る。

具体例です。

f:id:noshi91:20220102003524j:plain

図 1: 管理したい根付き木(左)と対応する link cut tree の例(右)。頂点の数字は元の木の頂点と対応している。

f:id:noshi91:20220102003753j:plain

図 2: 管理したい根付き木(左)と対応する提案手法の木の例(右)。丸いノードは元の木の頂点と、四角いノードは元の木の辺と対応している。

管理したい根付き木を $T = (V, E)$ とすれば、データ構造の全ての頂点が $V \amalg E$ と完全に $1$ 対 $1$ 対応します。また、提案した構造でも link cut tree と同様に splay や expose を行えば時間計算量が $\text{amortized} ~ \mathrm{O}(\log(N))$ になることも証明したつもりになっています (少し自信がありません)。

参考文献

[1] Alstrup, S., Holm, J., Lichtenberg, K. D., & Thorup, M. (2005). Maintaining information in fully dynamic trees with top trees. Acm Transactions on Algorithms (talg), 1(2), 243-264.

[2] Tarjan, R. E., & Werneck, R. F. F. (2005, January). Self-adjusting top trees. In SODA (Vol. 5, pp. 813-822).