SICP §2.3.3（集合の表現　その３　[二進木としての集合]）

今度は「木」構造のデータを考える。このデータ構造は、前セクションでやった「順序づけられたリスト」よりももっとご利益があるらしい。

構造のイメージとしてはこんな感じ。



┌────── tree ──────┐

│　　　　　　entry　　　　 　　│

│　　┌────┴────┐　　│

│left(tree)　　　　 right(tree)│

└───────────────┘

entryってのはしきい値をもっているラベル（SICPだと「見出し」って書いてあった）のようなものだと思いねぇ。で、leftはそのしきい値よりも小さい要素が格納され、rightにはしきい値よりも大きい要素が格納される感じ。

このモデルで考えると何が嬉しいか。。
仮にtreeのleftとrightの要素数が「釣り合っている」とすると、entryとの比較一発だけで候補を半分に減らすことができるということ。
つまり線形的なデータ構造よりも目的箇所に到達するのがはるかに早くなる。
どういう計算かいまいちわかんねーが、オーダーは Θ(log(n))になるそうだ。
（誰か教えてください。）

さて、このモデルをschemeで実装するとどうなるかというと・・・

;選択子（entry）
(define (entry tree)
  (car tree))
;選択子（左の木）
(define (left-branch tree)
  (cadr tree))
;選択子（右の木）
(define (right-branch tree)
  (caddr tree))

;構成子
(define (make-tree entry left right)
  (list entry left right))

こんな感じ。データの持ち方はどーでもいいちゃいい。（いままで散々「構成子」「選択子」の概念で問題解いて来たからまぁ分かるっしょ。）

次にこのデータモデルにおける element-of-set? はどんな実装になるかというと・・・

(define (element-of-set? x set)
  (cond ((null? set)
	 #f)
	((= x (entry set))
	 #t)
	((< x (entry set))
	 (element-of-set? x (left-branch set)))
	(else ;(< e x)
	 (element-of-set? x (right-branch set)))))

こんな感じになると。同じく adjoin-set はというと・・・このデータ構造だと重複を許しちゃうとどう定義すればいいか訳分からん感じになるので、重複なしで考えると、

(define (adjoin-set x set)
  (cond ((null? set)
	 ;比較対象となる集合(tree)が空リストだった場合は単独のtree（左右の枝無し）を返す
	 (make-tree x '() '()))
	((= x (entry set))
	 ;同一値があった場合は変更不要なのでそのまま set を返却
	 set)
	((< x (entry set))
	 ;比較元となる値 x が entry 値よりも小さい場合は左枝を再帰チェック。
	 (make-tree (entry set)
		    (adjoin-set x (left-branch set))
		    (right-branch set)))
	(else ;(< e x)
	 ;比較元となる値 x が entry 値よりも大きい場合は右枝を再帰チェック。
	 (make-tree (entry set)
		    (left-branch set)
		    (adjoin-set x (right-branch set))))))

こんな感じ。

これで結構な効率化が計れるとは思うが、実は前述のオーダー Θ(log(n)) ってやつ、そこにも記述したが tree が「釣り合っている」ことが前提になっている。
現実的にはそうでないケースがほとんど。
例えば何も登録されていない tree に 1, 2, 3, 4, 5, 6, 7 を順番に adjoin-set していくとどうなるか。。
そんな手続を書いてみるとこんな感じになる。

(define (adjoin-from-a-to-b init max)
  (let loop ((v init)
	     (lis '()))
    (if (< max v)
	lis
	(loop (+ 1 v) (adjoin-set v lis)))))

実行結果はコレ。



gosh> (adjoin-from-a-to-b 1 5)

(1 () (2 () (3 () (4 () (5 () ())))))

gosh>

こいつを図に直してみると・・・

こんな形のtreeになってしまう。全然釣り合ってねぇので、このままでは全然効率的なデータ構成とは言えなくなってしまう。。
この問題を解決する一つの方法として、何回か adjoin-set したら、tree が釣り合うように変換してやる演算を定義してやるってのもアリだが、「探索と挿入が共に Θ(log(n)) ステップで出来る新しいデータ構造を設計する」というのがこの後の話の流れになるっぽい？？

つーわけで問題 2.63 へ参ろう！