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

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

2016年10月16日

Java の主要概念の復習(超特急版)
2分探索木 in Java (java/bst/)

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

Java の主要概念の復習(超特急版)

オブジェクト

データとそのデータに対する操作の集まり．

インスタンス変数

オブジェクトに格納されるデータを表す．

メソッド

データに対する操作．操作が呼出されると，呼出し元から与えられる引数とインスタンス変数を使って計算を行う．場合によってはインスタンス変数の値を代入によって更新する．最終的に何らかの計算結果を呼出し元に返す(ことが多い)．

シグネチャ

メソッドの名前，引数の個数とそれぞれの型，返り値の型をまとめて，メソッドのシグネチャと呼ぶ．シグネチャさえわかれば，そのメソッドをどういう形式で呼出せばよいかわかる．

クラス

オブジェクトの定義を与えるプログラムのための構成単位．インスタンス変数の宣言，インスタンス変数の初期化処理を記述するコンストラクタ，メソッド定義が含まれる．

インターフェース

メソッドシグネチャをいくつか集めたものに名前をつけたもの．典型的には，
同一シグネチャのメソッドを持つ(異なる)クラスのオブジェクトをまとめて扱う際に便利である．具体的には

共通するメソッドのシグネチャを列挙したようなインターフェース I を定義する．
各クラスは，そのインターフェースを実装するという宣言 (implements I) をつけて定義する．(そのクラスにはインターフェースのシグネチャを持つメソッドを定義する義務が生じる．)
こうすることによって，I 型の変数には，Iを実装したクラスのオブジェクトをどれでも格納することができ，その変数を通じて I で宣言されているメソッドを呼ぶことができる．この際，実際に呼ばれるメソッド定義は，その時，変数に格納されているオブジェクトのクラスに依存する(動的ディスパッチ(dynamic dispatch))．

2分探索木 in Java (java/bst/)¹

まずは，2分木をどのように表現するかを考え，探索と挿入について考える．削除はあとで．

インターフェースを使った2分木の表現

Java (というかオブジェクト指向言語)の場合，データを構成する主要な手段はクラス/オブジェクトである．ここでは leaf と branch を別のクラス(名前を Leaf と Branch にしよう)で定義する．branch は左右の部分木と整数を持つので，それらを Branch クラスのインスタンス変数で表すことにする．2分木一般は Leaf または Branch クラスのオブジェクトであるので，インターフェース BinarySearchTree を用意し，変数がどちらでも格納できるようにする．

ファイル名: BinarySearchTree.java

public interface BinarySearchTree {
    // signatures for find, insert, delete to come
}

ファイル名: Leaf.java

public class Leaf implements BinarySearchTree {
    // no instance variables

    // Constructor
    public Leaf() {
        // nothing to initialize
    }
}

ファイル名: Branch.java

public class Branch implements BinarySearchTree {
    // instance variables to hold a number and subtrees
    private BinarySearchTree left;
    private int v;  // standing for a value
    private BinarySearchTree right;

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

Branch のコンストラクタのパラメータ変数の名前が(わざと)インスタンス変数の名前と衝突している．this.left とすることでインスタンス変数を示すことができる．右辺のように，本体内で単に left と書くとパラメータのことになる．

この定義を使って，2分木は例えば以下のように構成できる．²

        BinarySearchTree t1 = new Branch(new Leaf(), 10, new Leaf());
        BinarySearchTree t2 = new Branch(new Leaf(), 25, new Leaf());
        BinarySearchTree t3 = new Branch(t1, 15, t2);
        BinarySearchTree t4 = new Branch(new Leaf(), 60, new Leaf());
        BinarySearchTree t5 = new Branch(new Leaf(), 48, t4);
        BinarySearchTree t6 = new Branch(t3, 30, t5);

Branch オブジェクトが，t1 などの BinarySearchTree 型の局所変数に代入されていたり，BinarySearchTree 型の引数を期待するコンストラクタにLeaf オブジェクトが渡されていることに注目してほしい．これが，BinarySearchTree を設定したことの御利益(のひとつ)である．

この時点では何もメソッドを定義していないので，構成した2分木に対して何もできない．また，2分探索木の条件を満たさないようなものでも作れてしまうことに注意してほしい．

new を使ってオブジェクトを生成するとメモリが消費される．Leaf オブジェクトはインスタンス変数も持たず，複数の new Leaf() を使って生成された Leaf オブジェクト達を区別する理由はほとんどなく，ある意味メモリの無駄遣いである．これを問題として対処する方法はいくつか考えられる．できれば後述したい．

探索

木に対する操作はオブジェクトのメソッドとして実装する．典型的な木の操作の記述は，木が leaf である場合と branch である場合からなる．メソッドとして実装する場合，この場合分けを動的ディスパッチで行うのがオブジェクト指向らしいプログラミングである．この場合，Leaf クラスには木が leaf である場合の記述のみ，Branch クラスには木が branch である場合の記述のみをする．

探索のメソッド find は，探索する整数を引数とし，それが存在するかを表す真偽値を返すことにする．

まず，インターフェースに find のシグネチャを追加する．

public interface BinarySearchTree {
    boolean find(int n);
}

これで，Leaf と Branch にも find を(この引数，返り値で)定義する必要がでてくる．

次に木が leaf であった時の処理を，Leaf クラスのメソッドとして書く．(以下，
追加する部分だけ示す．)

    // Leaf クラスに追加
    public boolean find(int n) {
       // n doesn't exist in this BST
       return false;
    }

leaf には何のデータも格納されていないので，n が見つからないことを示す false を返している．

次に，木が branch であった時の処理はもう少し面白い(といっても，基本的に擬似コード通りである)．

    // Branch クラスに追加
    public boolean find(int n) {
        if (n == v) { return true; }
        else if (n < v) { return left.find(n); }
        else /* n > v */ { return right.find(n); }
    }

コンストラクタと違い，パラメータとインスタンス変数の名前は衝突していないので，インスタンス変数も単に left, right, v と書ける．³ また，最後の else 節は上の条件が成り立たない場合にのみ実行されるが，その時成り立っている条件 n > v (すなわち n != v かつ n < v) をコメントとして書いてみた．

left.find(n); において，インスタンス変数 left (型は BinarySearchTree)には，Leaf オブジェクトか Branch オブジェクトのどちらかが入っているわけだが，動的ディスパッチによって，場合に応じた処理が呼出されることになる．

Java プログラムの動作の理解がおぼつかない人は，ここで一旦次の資料を読むべし．

挿入

immutable vs mutable データ構造

挿入(と削除)は木の形を変える操作である．このような，操作の前後で構造に変化が生じる場合には，大きくわけて以下のふたつの実装方針がありえる．

できるだけ既にあるオブジェクトを再利用して，変更が生じた部分だけ形を組替える．この時，組替えは既存のオブジェクトのインスタンス変数に代入を施して変数の内容を書き換えることによって行う．変更前の木はある意味で破壊されるので，変更前後の木は同時に存在できない．
変更前の木はそのままにして，変更後を表す 新しい 木を作る．変更前後の木が同時に存在するため，古い木を使って別の操作を行うこともできる．(コンストラクタでインスタンス変数の初期化を行う以外の)代入操作を使わないことになる．

前者を 変更可能な(mutable)データ構造，後者を 変更不可能な(immutable)データ構造 という．⁴ ここでは，後者の方法で実装することを考える．

immutable な場合の挿入

探索の時と同じように，各インターフェース・クラスに，insert メソッドを追加する．挿入の結果作られる新しい木が返り値になるようにするため，BinarySearchTree インターフェースに追加するシグネチャは以下のようになる．

    // BinarySearchTree に追加
    BinarySearchTree insert(int n);

n が挿入される新しい要素である．

Leaf クラスについては，要するに空の木に何かを挿入した結果の木がどんな形になるかを考え，そのような木を作って返せばよい．

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

Branch クラスについては，少し戸惑うかもしれない．挿入しようとしている整数が今問題となっている節点に発見された場合は木に変化はない．といっても，擬似コードのように何も返さないで処理を終えてよいわけではなく，挿入前の木を返さなければいけない．挿入前の木，というのは，メソッドが呼出された対象の木そのもので，それは this という特別な名前でアクセスすることができる．

一方，この節点には n が格納されていない場合には，v との大小関係によって左右どちからの部分木に挿入することになる．そのため再帰的に left.insert(n) か right.insert(n) を呼ぶことになる．ここで大事なのは，この呼出しからは， 挿入後のあるべき姿の部分木が返ってくる(はずだ) ということである．呼出し側としては，これを使って，今注目している Branch 以下の挿入結果を作る必要がある．結果として以下のようなメソッド定義になる．

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

部分木の挿入結果を newLeft や newRight という局所変数に一旦格納して，それを子とする新しい Branch オブジェクトを作っている．(この変数は，一度書き込んで，すぐに読み出すが，以後使わないので，プログラムの読み易さ以外に必要性は余りない．例えば，

        } else if (n < v) {
            return new Branch(left.insert(n), v, right);
        } ...

と書いても構わないだろう．

完全に新しい木が返されているわけではない

最初の説明では，挿入操作によって新しい木が作られるように書いたが，これは実は正確ではない．確かに，Leaf クラスの insert 処理では，新しい葉・節点が作られているが，Branch クラスの(例えば)

            BinarySearchTree newRight = right.insert(n);
            return new Branch(left, v, newRight);

の部分で返されているのは，既存の木の部分木 left が結果の木の一部となっているような木である．つまり変化を生じていない部分については木の再利用をしていることになることに注意してほしい．

本当に immutable な木*

Java ではインスタンス変数への代入(正確には初期化以外の再代入)を，その宣言に final という修飾子をつけることで禁止することができる．この場合，Branch クラスは

public class Branch implements BinarySearchTree {
    // instance variables to hold a number and subtrees
    private final BinarySearchTree left;
    private final int v;
    private final BinarySearchTree right;

    ...
}

のようになる．コンストラクタの定義はそのままでよい．こうすることによって，メソッドの中で `v = 10;' などと代入するとコンパイル時のエラーになる．このように定義するとデータ構造が本当に immutable になる．

変数宣言の修飾子については，改めてまとめたい．

ここまでの要点と考察

木を構成する二種類のデータ(leaf と branch)が別々のクラスのオブジェクトとして表現されている．
二種類のデータどちらでも格納できる変数を用意するために，共通のインターフェースが定義されており，クラスはそれを implements するよう定義される．
木の操作で必要なデータの種類による場合わけは動的ディスパッチで実現されている．各クラスは，それが表すデータの場合の処理のみが書かれる．branch の持つ部分木はインスタンス変数として見えるので，木から部分木を取りだす，といった操作は特に明示する必要がない．
各クラスには，それが表すデータの場合の処理のみが書かれる結果，異なる操作同士の類似点は見やすいが，ひとつひとつの処理の全体像は定義がクラスにまたがってわかりにくい．ただし，(今回の2分木では考えづらいが，一般的には)もしデータの種類が増えるような場合には，新しいクラスを定義すればデータ構造が拡張できる点では便利である．
操作を代入を使わずに実現する場合，入力の木の部分，部分に対して再帰的にメソッドを呼出した結果を使って，どのように木を 作るか を記述するようなプログラムになる．
この2分探索木を使っている Main クラスでは new を使ってオブジェクトを生成しているが，間違えて2分探索木ではない構造を作ってしまう可能性があるため，本当は好ましくない．これを防止する手法については後でふれる．

削除

最後に削除についてみてみよう．挿入と同様に削除操作についても削除後の新しい木を返すように実装する．

    // BinarySearchTree に追加
    BinarySearchTree delete(int n);

Leaf クラスについては，このメソッドが呼出される，ということは，削除対象の n が木にそもそも存在しなかった，ということなので，削除前後で木が変化しない，ということになる．⁵

    // Leaf に追加
    public BinarySearchTree delete(int n) {
        // n is not in the BST, so return the same tree
        return this;    // could be  return new Leaf();  instead
    }

Branch については思いの他面倒臭い．2分木中の最大の数を求める操作(min)が必要なのが理由のひとつだが，他にも，擬似コードを見てみるとわかるように，部分木がどのような形をしているかによる場合分けをするのだが，その部分が案外曲者である．これまで，木の形(根が leaf か branch か)による場合分けは if を使わず，分岐した後の動作をメソッドとして書くことで行っていたが，この方法は取りづらい．そのため，木が Leaf や Branch であるかを問い合わせるメソッド isLeaf や isBranch を定義し，明示的に if で場合分けを行う．⁶ 以下に，必要なメソッドのシグネチャのみ示しておく．

    // BinarySearchTree に追加
    int min();
    boolean isLeaf();
    boolean isBranch();

今回は特定の言語に依存しないよう isLeaf や isBranch というメソッドを定義したが，Java の場合にはオブジェクトのクラスを判定するための instanceof 演算子がある．instanceof 演算子は 〈式〉 instanceof 〈クラス名〉 という形式で，〈式〉の値が指すオブジェクトのクラスが〈クラス名〉と等しいかどうかを判定する．例えば e.isLeaf() は e instanceof Leaf と書くこともできる．〈クラス名〉はインターフェースの名前でも構わない．その場合は，〈式〉の値が指すオブジェクトのクラスがインターフェースと implements 関係にあるかどうかを判定する．

これらのメソッドを使って detele は以下のように定義できる．

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

後半の n と v の値が異なる時の処理は insert と同様である．

この定義を見て，なぜ isLeaf などが必要になる(動的ディスパッチに頼ると非常に書きづらい)のか考えてみよう．

最後にminメソッドの定義について．Leafクラスでは，

    public int min() {
        // there is no minimum number in the BST
        return -255;
    }

と，全く意味のない -255 という値を返している．実は(delete の補助メソッドとして使われる限りでは)Leafに対して，最小値を求める処理が呼ばれることはないので，ここに何を書いておこうと問題はない．

(中級者向けコメント) むしろ，ここが実行されるのは，あってはならないことなので，return文の前に assert false; を書いておくべき．assert <Boolean式>; は，プログラマが <Boolean式> が true であることを何らかの理由で 表明(assert) しているものである．別の言い方をすると，これが false になったらプログラムの誤りであることを示している．実際には，true になったら単に通過するが，false になったら AssertionError と呼ばれる実行時エラーでプログラムの処理が異常終了する．assert false; は実行されたら必ず失敗するので，「そもそもここが実行されることはない」というプログラマの表明であると考えられる．