二進木の置換表現

図のような二進木があるとする. ノードの番号は中順序で付けてある.

二進木だから左リンクと右リンクがある. つまり

   k      1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
LLINK[k]  0  0  1  0  0  4  0  0  8  0  7  6  0 13  0
RLINK[k]  2  0 12  5  0 11  9  0 10  0  0 14  0 15  0

この2組のリンクを1組に圧縮する方法がTAOCP V4F4にあった. permutation representation of binary treeという.

ノードがn個あれば, 左と右でリンクは2nあるわけだが, 意味有るリンクは1を子にするもの, 2を子にするもの, (3はルートだから, 子にするものはない,)4を子にすもの,... という n-1個しかない. あとは子なしのnilのリンクだ. n=15の上の表でも, 0 は16ある.

この0は無駄なので, それを使おうと考えるのが, この方法の味噌である.

ノード番号は中順序なので, LLINK[k]<k かつ LLINK[k]!=0ならLLINK[k]は重要な情報である.

LLINK=0の場所がうまくRLINKに転用出来るかが, 問題である. つまり図で,
1, 3, 4, 6, 7, 9, 12, 14 (1)
から出ている右リンクの情報を,
1, 2, 4, 5, 7, 8, 10, 13, 15 (2)
の左リンクの場所を使って表現出来るかということだ.

ありがたいことに, 右部分木には, 必ずもっとも左のノードがあり, もっとも左だから, 左リンクは空いていて, しかも中順序だと, ノード番号が1だけ多い. つまり上の(2)の列は, 先頭の1を除いて(2)の列より1ずつ多い.

例えはノード3の右部分木は12をルートとするものだが, そのもっとも左のノードは4. ノード4の右部分木のもっとも左のノードは5. ノード6の右部分木は11をルートとするものだが, そのもっとも左のノードは7である.

これを活用することにすると, 3の右リンク12を4に置かせて貰うが, 部分木のルート自身がもっとも左でなければ, いまの場合がそうだが, 4<12になり, 4の右リンク5を5に置かせて貰う場合, 右部分木のルートがもっとも左なので, 5≤5となる.

要するに, こういう情報だけを保存すると,

   k      1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
LINK[k]   0  2  1 12  5  4 11  9  8 10  7  6 14 13 15

で済むのである. 1のLINKが空いているのは, もったいないようにも思うが, 1はこの二進木全体のもっとも左のノードなので, 二進木がスーパーノード0の右部分木であるとすれば, 0の右リンク3を置かせてあげればよく, 従って1のLINKは3とするのが正解である.

   k      1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
LINK[k]   3  2  1 12  5  4 11  9  8 10  7  6 14 13 15

上の二進木を中順序で辿る通常のアルゴリズムは,

(define (traverse k)
 (if (not (eq? (llink k) '())) (traverse (llink k)))
 (display k) (display " ")
 (if (not (eq? (rlink k) '())) (traverse (rlink k))))

(define (llink k)
 (list-ref '(() () 1 () () 4 () () 8 () 7 6 () 13 ())
  (- k 1)))
(define (rlink k)
 (list-ref '(2 () 12 5 () 11 9 () 10 () () 14 () 15 ())
  (- k 1)))

(traverse 3) => 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

リンクを

(define (link k)
 (list-ref '(3 2 1 12 5 4 11 9 8 10 7 6 14 13 15) (- k 1)))

とした場合のllinkとrlinkは

(define (llink k) (let ((l (link k)))
  (if (< l k) l '())))
(define (rlink k) (let ((l (link (+ (modulo k 15) 1))))
  (if (> l k) l '())))

(traverse (link 1)) => 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

なるほど.