2016年度「プログラミング言語」配布資料 (3)

五十嵐 淳 (京都大学大学院情報学研究科 通信情報システム専攻)

2016年10月3日

[ 前の資料 | 講義ホームページ・トップ | 次の資料 ]

under construction2017年版に向け改訂中

配布資料(1) では，インターフェースと動的ディスパッチを使って，2分探索木をJavaで実装した．ここでは，実装方法のバリエーションとして，

  • leaf の表現として null 参照を使う方法
  • mutable な2分探索木
  • ビジターパターン(visitor pattern)を使い，木の操作を木のデータから分離する方法

を学ぶ．

葉を null ポインタで表現する (java/bstNull)

前回の実装方法では，葉を Leaf クラスで，節点を Branch クラスで表現した．ここでは，葉をオブジェクトではなく， null (null pointer) を使って表現する方法をみる．

Java における null は，何のオブジェクトも指さない特殊な参照(ポインタ)の定数を示す表記である．null はオブジェクト参照を格納できる変数であれば，その変数の型に関わらず格納することができる．しかし，何のオブジェクトも指していないので，null を格納した変数を使ってメソッドを呼び出すと，例外(exception)1が発生し，(ふつうは)プログラム全体の実行がその時点で終了してしまう．null は未定義や例外的な値を表すのによく使われる．例えば，(初期化子がなく宣言された)インスタンス変数の初期値は null に設定される．

この null を使って葉を表すわけだが，これをしてよい理由は以下の通りである．

  • まず，Leaf オブジェクトにはインスタンス変数がないこと．実質，複数の Leaf オブジェクトは同一視しても問題はないため，予め約束事として定数をひとつ選んでおけばクラスを書かずともその定数で leaf を表現することができる．しかし，一方で Branch オブジェクトなどと同じ変数に格納できてほしいので，整数などを使うことはできない(Java で int やオブジェクト参照を格納できる変数は作れない)．null はBranchが格納できる変数にも格納できるのでうってつけである．

  • leaf の他には定数で代替してよいようなものがない．参照のうち null のような特殊な定数はひとつしかないので，null で代替できるクラスは，データ構造を表すクラスの中でひとつだけである．

2分木構造の定義

このような方針を取ると，クラスがひとつしか必要がないのでインターフェースを設定する必要がなくなる．(もちろん，これはデータを構成する要素が2種類しかない，という2分木の特殊事情である．一般のデータ構造では3つ以上の種類のデータを混ぜて使うこともあり，その場合はインターフェースを定義する必要がある．)ということで，BinarySearchTree というクラスを定義するだけになる．そして，その内容は(データの設計に関する部分は)ほとんど Branch クラスと同様である．

1
2
3
4
5
6
7
8
9
10
11
12

public class BinarySearchTree {
    private BinarySearchTree left;
    private int v;
    private BinarySearchTree right;

    public BinarySearchTree(BinarySearchTree left, int v,
                            BinarySearchTree right) {
        this.left = left;
        this.v = v;
        this.right = right;
    }
}

2分木操作の定義

この方法はクラスがひとつに減ってうれしい反面，もはや動的ディスパッチで葉か節点かの場合分けをすることができない．木を使おうとする側が，自分で，変数に格納された木が葉なのか節点なのかを管理して適切な場合分けをする必要がある．以下は，新しい find メソッドの定義である．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

    // BinarySearchTree クラスに追加
    public boolean find(int n) {
        if (n == v) {
            return true;
        } else if (n < v) {
            /* same as return (left!=null)&&(left.find(n)) */
            if (left != null) {
                return left.find(n);
            } else {
                return false;
            }
        } else /* n > v */ {
            if (right != null) {
                return right.find(n);
            } else {
                return false;
            }
        }
    }

if が入れ子になって少し見通しが悪いが，再帰呼出しをする前に，left != null や right != null によって，部分木が leaf かどうかを確かめている．この場合分けは，以前は動的ディスパッチで行っていたものであり，else 節の処理は，これまで Leaf クラスに書かれていたものである．

Main クラスでは以前からほとんど変更なく，そのまま find を呼出しているが，これは変数に格納された木が(nullではなく)Branch であることがわかりきっているからである．一般には再帰呼出しに限らず，find を呼出す前に null かどうかのチェックをする必要がでてくる．

挿入・削除操作については，同じ要領で実装することができる．定義が少し長くなっているが，これは Leaf と Branch にあったコードがまとまっているためである．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

    // BinarySearchTree クラスに追加
    public BinarySearchTree insert(int n) {
        if (n == v) { return this; }
        else if (n < v) {
            if (left != null) {
                BinarySearchTree newLeft = left.insert(n);
                return new BinarySearchTree(newLeft, v, right);
            } else {
                BinarySearchTree newLeft = new BinarySearchTree(null, n, null);
                return new BinarySearchTree(newLeft, v, right);
            }
        } else /* n > v */ {
            if (right != null) {
                BinarySearchTree newRight = right.insert(n);
                return new BinarySearchTree(left, v, newRight);
            } else {
                BinarySearchTree newRight = new BinarySearchTree(null, n, null);
                return new BinarySearchTree(left, v, newRight);
            }
        }
    }

削除に関しては，min メソッドは引き続き使うものの，isLeaf や isBranch メソッドが不要になっている．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

    public BinarySearchTree delete(int n) {
        if (n == v) {
            if (left==null) {
                if (right==null) {
                    return null;
                } else {
                    return right;
                }
            } else {
                if (right==null) {
                    return left;
                } else {
                    int m = right.min();
                    BinarySearchTree newRight = right.delete(m);
                    return new BinarySearchTree(left, m, newRight);
                }
            }
        } else if (n < v) {
            if (left != null) {
                BinarySearchTree newLeft = left.delete(n);
                return new BinarySearchTree(newLeft, v, right);
            } else {
                return this;
            }
        } else /* n > v */ {
            if (right != null) {
                BinarySearchTree newRight = right.delete(n);
                return new BinarySearchTree(left, v, newRight);
            } else {
                return this;
            }
        }
    }

mutable な2分探索木 (java/bstMutable)

次に考えるバリエーションは，mutable な2分探索木である．この場合，immutable な実装と異なり，木の操作は既にある節点オブジェクトのインスタンス変数を代入文で書き換えて新しい木構造を作る．別の言い方をすると，必要最小限のオブジェクトの生成しか行わないよう操作を実現する，ともいえる．既にふれたように，その代償として，一旦挿入や削除を行うと，操作前の2分探索木は破壊されて失われてしまうことになる．

まず，挿入操作についての新しい定義を見ていこう．

Leaf クラス

1
2
3
4

    public BinarySearchTree insert(int n) {
        // a new singleton tree holding n
        return new Branch(new Leaf(), n, new Leaf());
    }

Branch クラス

1
2
3
4
5
6
7
8
9
10

    public BinarySearchTree insert(int n) {
        if (n == v) {
            // do nothing
        } else if (n < v) {
            left = left.insert(n);
        } else /* n > v */ {
            right = right.insert(n);
        }
        return this;
    }

実は，Leafクラスについては変更の必要がない．LeafオブジェクトがBranchオブジェクトに変化するわけだが，この変化はオブジェクトのクラスの変化であって，インスタンス変数の変化では表現できないため，新しいBranchオブジェクトを生成して，それを返すことになる．

一方，Branchクラスについては，部分木への挿入を行った結果 left.insert(n) (や right.insert(n))をインスタンス変数 left (や right)に代入することで，木構造を組替えている．最終的には this を返しているのは，このメソッドは新しい木の根を返すことになっているためである．Branch クラスだけを見ると，this を返すのではなく，(返り値型を void にして)，代入だけして，何も返さない(最後を return; とする)メソッドとして実現してもよいように思えるが，Leaf の方では新しいオブジェクトを返すのが自然なので，それに合わせて this を返す実装になっている．2

削除についても，変更のやり方は同じようなものである．Branchクラスの主な変更のみ示す．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

    public BinarySearchTree delete(int n) {
        if (n == v) {
            if (left.isLeaf()) {
               return new Leaf();
            } else {
                if (right.isLeaf()) {
                    ...
                } else {
                    // copy the number next to n (the minimum number
                    // in right) and delete it from right.
                    int m = right.min();
                    v = m;
                    right = right.delete(m);
                    return this;
                }
            }
        } else if (n < v) {
          ...
        } else /* n > v */ {
          ...
        }
    }

9行目から14行目にかけてが，削除すべき節点に子がふたつあった場合の処理である．インスタンス変数 v と right を代入によって変更している．また，Leaf クラスと合わせて定義を見てみると，delete 操作はオブジェクト生成をほとんどしていない(削除すべき節点に子がない場合の処理で，insert とは逆に，節点から葉への変化のために Leafオブジェクトを生成しているだけである)ことがわかる．

ビジターパターンによる操作とデータの分離 (java/bstVisitor)

その他

これらのバリエーションを組み合わせる，というのも考えられる．

  • java/bstNullMutable: 葉を null ポインタで表現した mutable な2分探索木
  • java/bstVisitorMutable: ビジターパターンによる mutable な2分探索木

ビジターパターンは動的ディスパッチに依存しているので，葉を null ポインタで表現する方法と組み合わせることはできない．

[ 前の資料 | 講義ホームページ・トップ | 次の資料 ]

  1. 例外とは，通常の実行が続けられなくなった状態を示す．例外機構についてはそのうちやりたいと思っています．↩

  2. Branch と Leaf の insert が別の返り値型を持つとコンパイル時のエラーになってしまう．↩

Copyright 五十嵐 淳, 2016, 2017