概要
最もシンプルなポインタによる二分木の実装は、各ノードが左子と右子を保持することでしょう。
一方でこの実装では親方向へ遡ることが出来ません。すると例えば平衡二分探索木のイテレータを実装するときなどに問題になります。
親へのポインタを保持すれば解決しますが、本稿では空間計算量を抑える手法を紹介します。
XOR木
ポインタ領域を削減するデータ構造として、XOR連結リストが知られています。
XOR連結リストとは、双方向連結リストで左右へのポインタの xor のみを保持する物です。
どちらかのポインタが分かっていればもう一方が復元できるため、左右いずれの端からも走査が可能となります。
この手法をポインタ二分木に応用してみましょう。
左子、右子、親の 3 つのポインタを適切に xor して 2 つに圧縮します。
どれを xor しても良いのですが、対称性から「左子と親」「右子と親」を xor した値を保持してみます。
すると各ノードについて、左子、右子、親のいずれかのポインタが分かっていれば全てのフィールドを復元可能です。
よって根からの探索の他、葉から親を探索するなども可能となります。
二重連鎖木に類似した手法
全てのノードは左子に加えて、自身が左子であるならば兄弟を、右子であるなら親を保持します。 これは図を見るのが最も分かりやすいでしょう。
親を取得するとき自身が左子か右子かを判定する必要がありますが、自身が左子と仮定して三角形をぐるっと回り戻ってきたら左子、といった風に判定することが出来ます。 また、左子や右子を片方しか持たない場合不都合なことが起こりますが、適宜ポインタを貼ることで何とかなると思います。(多分)
葉が隣接するノードへのポインタを持つ
これは二分探索木を in-order で走査するための手法で、一般に木を自由に探索できるわけではないことに注意してください。
各ノードは、もしポインタが null ならばそれを in-order でその方向に隣接するノードに張ります。
すると各ノードについて in-order で次のノードを以下のように探索することが出来ます。
- 右子を持たないならば、右子の代わりに持っているポインタに進む
- 右子を持つならば、右子→左子→左子→左子... と突き当たるまで進む
in-order で手前のノードも同様に探索可能です。
子を持つのか、持っていなくて隣接ノードへのリンクを持っているのかはなんか良い感じに判定しましょう。
例えば weight balanced tree なら weight の大小で判定できます。
終わりに
その他関連する情報があったら教えてください。 2 つめの手法はどこかの論文で見かけた気がしたのですが、分からなくなってしまったのでそちらも心当たりのある方は教えて頂けると嬉しいです。
