木

http://www.kmonos.net/wlog/84.html#_1243080419 を読んで思ったのですが、外部イテレータで移動できる木のノードって普通{親,左,右,値}にしますけど、うまくやれば親フィールド削って{左,右,値}にできないでしょうか。左または右が無い時は、移動先となる親(の親……)を入れておくことができればいいわけで。

root=$

4追加。

root={$,$,4}

2追加。

root={A,$,4}
A={$,root,2}

3追加。

root={A,$,4}
A={$,B,2}
B={A,root,3}

B位置から右へ動くときは、右として記憶されているrootから左へ辿り始めて、自分のところに戻ってきてしまったらああこれは親方向に戻ったなと解釈してBの右はrootと解釈……親を別に記憶している場合は、親から左に接続されていたところまで親の親の……と辿るわけですので、計算量も増えない……と思う。
しまった、普通の子ノード方向への右移動は右に一歩移動した後左に行けるだけ行きますので、これだとBの右がAになるじゃないか……親方向ですよフラグがいりますね。
でもまあフラグなんてポインタの下位ビットに入れられるのでうまくいきそうな気もする。それに親方向ですよフラグがあれば、親方向の移動は一発で済むため逆に速くなるかもしれません。
暇なときに試す。
あとまあこんなのやってると回転で破綻するのでバランス木には使えませんが。いやまてよ親方向ですよフラグじゃなくて子が無いから代わりにリスト中の次の位置を指してますよフラグということにすれば破綻しないのか。