プログラミング/13

出典: CourseWiki

この回は2回分くらいの量があります

目次

クラスの継承

オブジェクト指向プログラミングでは,あるクラスをベースとして,それに機能を追加した別のクラスを作成するということがよく行われます.これがクラスの継承(inheritance)です.

ベースとなるクラスをスーパークラス(super class)(あるいは基底(ベース)クラス,親クラス),そこから派生したクラスをサブクラス (subclass)(あるいは派生クラス) と呼びます.

例えば,様々な敵キャラクタが登場するゲームを考えると,敵キャラクタには共通する部分(移動する,Hit Pointがある,etc.)と,異なる部分(攻撃方法,表示方法, etc.)があります.この場合,共通する部分をベースクラスとして,個々のキャラクタはサブクラスとして記述すれば全体の記述量は少なくなります.

class A をスーパークラスとして,class B を定義する場合,extends を使って次のように書きます.

// クラスAを引き継いでクラスBを作る
public class B extends A {
  クラス定義
}

継承したクラスBでは,クラスAの全てのメソッドや変数を引き継ぎます. つまり,クラスBで(定義しなくても)クラスAで定義されたメソッドや変数を最初から備えていることになります.このため,クラスBの定義では,クラスAの定義に対する差分だけを記述することになります.

サブクラスからさらにサブクラスを定義することもできます.

さて,Javaでは,クラス定義において明示的にスーパークラスを記述しなかった場合 (つまり,extends スーパークラス名 を書かなかった場合),そのスーパークラスは自動的に Object (java.lang.Object) というクラスになることになっています. このため,全てのクラスはスーパークラスを辿っていくと,Object クラスに辿りつくことになります.別の言い方をすると,全てのクラスは Object クラスのサブクラスということでもあります.

画像:Inheritance.png

Javaでは,クラスBがクラスAのサブクラスのとき,A型の変数にはBのインスタンスへの参照を代入できることになっています. 全ての参照型変数を Object 型の変数に代入できるのはこれが理由です (全てのクラスはObjectクラスのサブクラスなので).

Objectクラス

ObjectクラスのAPIドキュメントを見ると,いくつかメソッドが定義されていることが分かります (equals, hashCode, toStringなど). 全てのクラスはObjectのサブクラスなので,これらのメソッドは全てのクラスで定義されていることになります.

Javaの最も基本となるクラスなので,APIドキュメントは一度目を通しておきましょう.

サンプル

クラス継承の例として,バスとトラックのクラス(class Bus, class Truck)を定義してみます.

バスもトラックもクルマ(Car)なので,基本的な機能はほぼ共通しています.そこで,まず Car クラスを作って,クルマとしての共通の機能を定義します.次に,Car クラスを継承して Busクラスを作り,バスに特有の機能を定義します.同様に,Car クラスを継承して Truck クラスを定義します.こうすると,車の基本機能に何か追加や変更があったときも,Car クラスを変更するだけ済みます.

以下にサンプルプログラムを示します.

/*
 * クラスの継承のサンプル 
 */
// クルマクラス
class Car {
    // protected を付けたフィールドはサブクラスからも参照できる
    // (private だと参照できない)
    protected String name;        // クルマの名前
    public Car(String name) {    // コンストラクタ
        this.name = name;
    }
    // 走らせる
    public void drive() {
        System.out.println(name + " is running");
    }
    // 停める
    public void stop() {
        System.out.println(name + " is stopping");
    }
    public String toString() {
        return "Car(" + name + ")";
    }
}
 
// BusクラスはCarクラスのサブクラス
class Bus extends Car {
    private int passenger;
    public Bus(String name) {
        // サブクラスのコンストラクタでは,以下のようにスーパークラスの
        // コンストラクタを呼び出す必要がある
        super(name);
    }
    // 乗客を載せる
    public void loadPassenger(int passenger) {
        this.passenger = passenger;
    }
    // CarクラスのtoString()メソッドをオーバーライド(再定義)
    public String toString() {
        // 下の行のnameはCarクラスのインスタンス変数を参照している
        return "Bus(" + name + ", carrying " + passenger + " passengers)";
    }
}
 
// トラッククラス
class Truck extends Car {
    private String load;    // 積み荷の名前
    public Truck(String name) {
        super(name);
    }
    // 積み荷を積む
    public void load(String load) {
        this.load = load;
    }
    // CarクラスのtoString()メソッドをオーバーライド
    public String toString() {
        return "Truck(" + name + ", loading " + load + ")";
    }
}
 
public class InheritanceDemo {
    public static void main(String[] args) {
        Bus bus = new Bus("Fuso");
        Truck truck = new Truck("Isuzu");
        bus.loadPassenger(50);
        bus.drive();            // Carクラスのdrive()が呼ばれる
        truck.load("Kamo");
        Car car = bus;            // carはBusクラスのインスタンスを参照している
        // BusのtoString()が呼ばれる (CarのtoString()ではないことに注意!)
        System.out.println(car);
        car = truck;
        System.out.println(car);// TruckのtoString()が呼ばれる
        // car.load("Negi");    // エラー (Carにはloadメソッドがない)
        ((Truck)car).load("Negi");    // carをTruckにキャストすればOK
        System.out.println(car);// TruckのtoString()が呼ばれる
    }
}

実行結果:

Fuso is running
Bus(Fuso, carrying 50 passengers)
Truck(Isuzu, loading Kamo)
Truck(Isuzu, loading Negi)
  • Car型の変数carにはサブクラスであるBusやTruckクラスのインスタンスへの参照を代入できますが,carを通じて呼び出すインスタンスメソッドはBusやTruckクラスのものになります.つまり,インスタンスメソッドの呼び出しでは,呼び出されるメソッドは変数の型によって決まるのではなく,変数が指しているオブジェクトのクラスによって決まります. このことをオブジェクト指向プログラミング用語でポリモーフィズム(polymorphism) といいます.

publicでないクラス

上のサンプルプログラムにはpublicでないクラス(Car, Bus, Truck)があります.実はJavaでは1つのソースファイルにpublicなクラスは1つしか書けませんが,publicでないクラスは複数書くことができます.

publicでないクラスは,同一パッケージからアクセス可能です.

クラスを private とすることはできません.

protected

Carクラスでは,protected を使っています.protected はサブクラスからのアクセスは許す(しかし関係ないクラスからはアクセスできない)というアクセス修飾子です.

protected はメソッドにも付けることができます.

super

サブクラスのインスタンスには内部的にスーパークラスのインスタンスを含んでいるので,サブクラスのコンストラクタからはスーパークラスのコンストラクタを呼び出す必要があります.そのための構文が super(..) です.BusとTruckのコンストラクタで使っています.

  • super の引数にはスーパークラスのコンストラクタへの引数を書きます.
  • superの呼び出しは,サブクラスのコンストラクタの最初の文にないといけません.
  • superの呼び出しは,スーパークラスのコンストラクタに引数がないものがあれば省略可能です.省略した場合でも,スーパークラスのコンストラクタは自動的に呼び出されます.



木構造

木構造(tree)も基本的なデータ構造の一つで,よく使われます.

  • ファイルシステムのディレクトリ(フォルダ)は木構造そのもの.
  • Bツリー(木構造の一つ)は,外部記憶装置でのインデックスによく使われます(ファイルシステム,データベースなど)
  • 言語処理系(コンパイラやインタプリタなど)では,プログラムの構造を解析して木構造で保持します.

木構造では,n個のデータが存在するとき,検索,登録はO(log n)時間で実行できます. また,ハッシュテーブルと異なり,データ間に順序関係(大小関係)があることが特徴です.

木構造では,ノードと呼ばれる節点にデータを記憶します.

  • 木構造の根となるノードが存在し,ルートノード(root node)(ルート,根とも)と呼ばれます.
  • ノードには0個以上の子ノードに対するリンクがあります.ノードBがノードAの子ノードの時,ノードAはノードBの親ノードであるといいます.
  • ルートノードの親ノードはありません.ルートノード以外のノードでは,親ノードは正確に1つだけ存在します.
    • このため,あるノードから子ノードを辿っていっても,最初のノードに戻ることはありません(ループはない).
  • 子ノードがないノードのことを,リーフノード(leaf node)(リーフ,葉とも)といいます.
  • リーフノードでないノードのことを,内部ノード(internal node)といいます.
  • 親ノードと子ノードとの距離を1とするとき,ルートノードからリーフノードまでの最大の距離を木の高さといいます.下の木の高さは3です.
  • 木構造では,あるノードXから辿れる全てのノードを含んだノード集合も木構造になっています.これを,(ノードXをルートノードとする)部分木と呼びます.

画像:Tree.png
木構造の例

木構造にはさまざまな種類がありますが,今回は基本的な2分探索木を取り上げます.

2分探索木

2分探索木(binary search tree)は以下の特徴を持つ木構造です.

  • 子ノードは最大2つで,と表現する.
  • ノードに値を格納する.
  • 全ての内部ノードで(左の部分木内の最大値≦親ノードの値≦右の部分木内の最小値)という関係が成立している.

以下に例を示します.上の条件が満たされていることを確認してください (例えば,70のノードの左の部分木の最大値は65,右の部分木の最小値は75で,65≦70≦75が成立).

画像:BinarySearchTree.png

上の2分探索木で,例えば65を検索する場合は以下のようになります.

  • まず,ルートノード(70)と65を比較します.65の方が小さいので,左の子ノード(50)に進みます.
  • 50と65を比較すると65の方が大きいので,右の子ノード(60)に進みます.
  • 60と65を比較すると65の方が大きいので,右の子ノード(65)に進みます.
  • 65を発見して終了します.

同様に,72を挿入する場合は以下のようになります.

  • まず,ルートノード(70)と72を比較します.72の方が大きいので,右の子ノード(80)に進みます.
  • 80と72を比較すると72の方が小さいので,左の子ノード(75)に進みます.
  • 75と72を比較すると72の方が小さいですが,左の子ノードが存在しないので,ここに(左の子ノードとして)72を挿入します.

木がうまくバランスしていれば(各ノードで左右の部分木の高さが同じ程度ならば), 1ステップで左右のどちらかの部分木に進むごとに部分木のノード数が約半分になります(これが2分探索木と呼ばれる理由).

検索,挿入の処理は登録データ数をnとしてO(logn)の時間で実行できます. (1ステップでノード数が半分になるということは,sステップで2s個のノード(データ)を処理できる.n = 2sとすれば,s = log2n).

例によって2分探索木をJavaで書いてみましょう.

ノードの表現

ノードは基本的には以下のように表現できます.

class Node {
   Object value;
   Node left;		// nullなら子ノードなし
   Node right;		// nullなら子ノードなし
}

ここで登録するデータ(value)同士は,大小関係を判定できる必要があります. 等しいかどうかの判定はequalsメソッドでできましたが(Objectクラスにequalsメソッドが定義されているので,全てのクラスにequalsメソッドが定義されている),大小関係の判定を行うメソッドはありません.

かといって,Object value; の部分を Integer value; のようにしてしまうと,整数しか扱えないNodeになってしまいます.なんとかして大小関係を比較できるクラスなら何でもよいを表現できればよいのですが,(結論から言うと)Javaではこのような目的のためにはインタフェースというしくみを使います.

インタフェース

Javaではインタフェース(interface)という機能があります.

Javaのインタフェースは,簡単にいうとあるクラスが特定のメソッド(群)を備えていることを宣言し,それらのクラスを統一的に扱うためのものです.

インタフェースは,interface キーワードを使ってクラスと同様に宣言します.

// Fooというインタフェースを定義する.Foo.java に保存する必要がある
interface Foo {
  public int foo(int f);
  public void bar();
}

インタフェースはクラス定義と似ていますが,メソッドの実体がありません.

あるクラスAが,インタフェース Foo で定義されている全てのメソッドを定義している場合,クラスAはインタフェースFooを実装しているといいます.このことをimplementsキーワードを使って次のように表します.

// Fooを実装しているクラスAの定義
class A implements Foo {
  public int foo(int f) {..}
  public void bar() {..}
  // interfaceに関係ないメソッドがあってもよい
  public void baz() {..}
}
// 別のクラスBでもFooを実装
class B implements Foo {
  public int foo(int f) {..}
  public void bar() {..}
  ..
}

Foo型の変数を作ると,Fooを実装しているクラスのインスタンスへの参照を代入することができます.また,Fooで定義しているメソッドも呼び出すことができます.

A a = new A();
B b = new B();
Foo foo1 = a;	  // AがFooを実装しているので,Foo型に代入できる
Foo foo2 = b;
foo1.foo(10);    // OK.クラスAのfooメソッドが呼び出される
foo1.baz();      // エラー! (Fooにbazメソッドは定義されていない)

Objectという型によって,全てのクラスのインスタンスを統一的に扱うことができましたが,Fooという型を使うことによってインタフェースFooを実装した特定のクラスのインスタンスだけを統一的に扱うことができます.

クラスの継承を使っても,特定のメソッドが定義されていることを保証することはできますが(以下のように),インタフェースを使った場合は継承関係にないクラスでも大丈夫です.

// Aの全てのサブクラスはfooとbarを備えている
class A {
  public int foo(int f) {..}
  public void bar() {..}
} 
class B extends A {
  ...
}
class C extends A {
  ...
}

Comparableインタフェース

話を元に戻すと,JavaではComparable (java.lang.Comparable)という標準のインタフェースがあり, 大小関係を比較できるクラスは,通常このインタフェースを実装しています.

Comparableインタフェースではただ一つのメソッド(compareTo(Object o))が定義 されています.

interface Comparable {
  int compareTo(Object o);
}

compareToメソッドは,インスタンスと引数のoで指定したオブジェクトを比較 して,大小関係を数値で返します.A.compareTo(B)の値が負ならばA<B,0なら ばA=B,正ならばA>Bということになっています.

ComparableのAPIドキュメントをみると,

public interface Comparable<T> {
 int compareTo(T o);
}

のように<T>という記法がありますが,これはJ2SDK5.0で導入されたジェネリックタイプと呼ばれるものです(ここでは解説しません(便利なのですが..)).

StringクラスやIntegerクラス,DoubleクラスなどはComparableインタフェースを実装しています(このことは,各クラスのAPIドキュメントの最初にある「全ての実装されたインタフェース」に記述されています).各クラスの compareTo メソッドの説明も読んでください.

String a = "aaa";
String b = "bbb";
System.out.println(a.compareTo(b));
// 辞書順で "aaa" < "bbb" なので負の値が表示される
Integer c = new Integer(100);
Integer d = new Integer(10);
System.out.println(c.compareTo(d));
// 100 > 10 なので正の値が表示される

ノードの表現(again)

ということで,(前置きが長くなりましたが),Nodeクラスは次のように書くことができます.

class Node {
   Comparable value;	// 互いに比較可能なオブジェクト
   Node left;		// nullなら子ノードなし
   Node right;		// nullなら子ノードなし
   ...
}

BinSearchTreeクラス

2分探索木を実装するBinSearchTreeクラスを以下に示します.

/*
 * ツリー
 */
public class BinSearchTree {
    // ノードクラス
    public static class Node {
        private Comparable value;
        private Node left;  // 左ノード
        private Node right; // 右ノード
        public Node(Comparable value) {
            this.value = value;
            // left, rightはnullになっている
        }
        public String toString() {
            return "Node(" + value + ")"; 
            //    + ", left = " + left + ", right = " + right + ")";
        }
    }
 
    // ルートノード
    private Node rootNode;
 
    // valueを挿入する
    public void insert(Comparable value) {
        // rootNodeをルートとしてvalueを挿入する
        rootNode = insert(value, rootNode);
    }
 
    // rootをルートノードとする部分木に対してvalueを挿入する
    // valueが挿入された部分木のルートノードを返す
    private Node insert(Comparable value, Node root) {
        // rootがnullならば,Nodeを作って返す
        if (root == null) {
            return new Node(value);
        }
        // root.valueはComparableなので,compareToを呼び出せる
        int cmp = root.value.compareTo(value);
        if (cmp < 0) {
            // rootのほうが小さければ,右の部分木に挿入する (再帰)
            root.right = insert(value, root.right); 
        } else {
            // そうでなければ左の部分木に挿入する
            root.left = insert(value, root.left);
        }
        return root;
    }
 
    // valueを検索する
    public Comparable search(Comparable value) {
        return search(value, rootNode);
    }
 
    // rootをルートノードとする部分木からvalueを検索する.
    // valueが挿入された部分木のルートノードを返す
    private Comparable search(Comparable value, Node root) {
        if (root == null) {
            return null;
        }
        int cmp = root.value.compareTo(value);
        if (cmp == 0) {
            return root.value;
        } else if (cmp < 0) {
            return search(value, root.right); 
        } else {
            return search(value, root.left);
        }
    }
 
    // valueを削除する
    public void remove(Comparable value) {
        rootNode = remove(value, rootNode);
    }
 
    // rootをルートノードとする部分木からvalueを削除する (バグあり)
    // valueを削除した部分木のルートノードを返す
    private Node remove(Comparable value, Node root) {
        if (root == null) {
            return null;
        }
        int cmp = root.value.compareTo(value);
        if (cmp == 0) {
            // rootが削除対象のノード
            if (root.left == null) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }
            // rootに左右の子が両方存在する場合
            // n = 左部分木の最大ノード
            Node n = searchLargestNode(root.left);
            n.left = root.left;
            n.right = root.right;
            return n;
        } else if (cmp < 0) {
            root.right = remove(value, root.right); 
        } else {
            root.left = remove(value, root.left);
        }
        return root;
    }
 
    /*
     * rootをルートノードとする部分木から最大値を持つノードnを検索する.
     * ただし,nの左ノードをnの元位置に置き換える.
     */
    private Node searchLargestNode(Node root) {
        // 右の子ノードが存在する限り右の子ノードを辿れば最大値が見つかる
        if (root.right == null) {
            return root;
        }
        // 右の部分木を探索する
        Node n = searchLargestNode(root.right);
        // nの左ノードをnの元位置に置き換える
        if (n == root.right) {
            // root.right = null; となっていましたが,間違いです.
            root.right = n.left;
        }
        return n;
    }
 
    // 文字列に変換
    public String toString() {
        StringBuilder buf = new StringBuilder();
        buf.append("[");
        toString(buf, rootNode);
        buf.append("]");
        return buf.toString();
    }
 
    private void toString(StringBuilder buf, Node root) {
        if (root == null) {
            return;
        }
        // 左側の部分木を処理(結果はbufに追記)
        toString(buf, root.left);
        // rootのデータを追記
        buf.append(root.value);
        buf.append(" ");
        // 右側の部分木を処理
        toString(buf, root.right);
    }
 
    // サンプル
    public static void main(String[] args) {
        BinSearchTree tree = new BinSearchTree();
        for (int i = 0; i < 10; i++) {
            tree.insert((int)(Math.random() * 100));
        }
        System.out.println(tree);
    }
}


EclipseではComparableなどの下に黄色い下線(警告)が表示されるかもしれませんが, これはジェネリックタイプを使っていないことに対する警告です. 気になる人はEclipseのPreferenceからJava→Compiler→Errors/Warningと辿り, Generic typesの警告を全て Ignore にしておくとよいでしょう.

入れ子クラス

NodeクラスはBinSearchTreeクラスの内部で定義しています. このようなクラスを入れ子クラス(nested class)といいます.

入れ子クラスは,あるクラスに関連の深いクラスを定義するためによく使われます.

staticな入れ子クラスは,通常のクラスとそれほど違いはありません. (staticでない入れ子クラスもありますが,ちょっとややこしいので省略します).

staticな入れ子クラスを定義するには以下のように書きます.

public class A {
  public static class B {
    // Bのフィールドやメソッドの定義
  }
  // Aのフィールドやメソッドの定義
}

この場合,Aのクラス定義に加えて A.B という名前のクラスを定義したことになります. (class Aの中では A.B と書かずに B だけでよい).

入れ子クラスからみて,外側のクラスをエンクロージングクラス(enclosing class)といいます. (BinSearchTreeクラスがNodeクラスのエンクロージングクラス).

エンクロージングクラスからは,入れ子クラスのフィールドやメソッドは自由に(privateでも)アクセス可能です.

演習(入れ子クラス)

連結リストの実装で使ったCellクラスも,DLinkedListクラスの入れ子クラスにするほうがよいでしょう.ということで,そのように書き換えて下さい.(DLinkedList.Cell という名前のクラスになります)

演習(入れ子クラス)の回答例

再帰

searchメソッド(オーバーロードされているので2つありますが,2つめの方です)は,searchメソッド自身を呼び出しています.このようにメソッドが自分自身を呼び出すことを再帰(recursion)(または再帰呼び出し)といいます.

再帰は繰り返しを行うための方法の一つです.再帰に対して,for文やwhile文による繰り返しは反復(iteration)と呼ばれます.

メソッド内の局所変数の値が再帰呼び出しによって書き換わってしまうのではないかと思う人もいるかもしれませんが,そのようなことはありません.普通のメソッド呼び出しと同じです.

無条件に自分自身を呼び出したらプログラムの実行が止まらないので,ある条件が満たされたら自分自身を呼び出さずにreturnするようにします.再帰が止まらないと,そのうちメモリを使い果たして StackOverflowError になります.

一般に再帰を用いてあるサイズの問題を解決する場合,以下のようにします.

  • 再帰呼び出しによってよりサイズの小さい問題に分解する.また,
  • サイズが一定サイズ(たいてい0や1)になったら,再帰呼び出しせずに停止(return)する.

aからb(a<bとする)までの和を求めるメソッドは再帰を使うと次のように書けます.

1: public static int sum(int a, int b) {
2:   if (a == b) {
3:     return a;
4:   }
5:   return a + sum(a + 1, b);
6: }

sum(0, 3)を呼び出すと,5行目でsum(1, 3) を呼び出します.sum(1, 3)の実行が完了したら,その結果とa(=0)を加算した結果をreturnします.この様子を図示すると以下のようになります.

画像:Recursion.png
再帰呼び出しの様子

再帰呼び出しによって,問題がより小さい問題に分解されていることがわかります. (0〜3までの和を求める処理が,1〜3までの和を求める処理に,...). また,問題のサイズが0になったら(ここではa==b),再帰せずにreturnするようになっています.

再帰呼び出しは反復に比べると遅いですが,しばしば問題を簡単に記述(解決)できるため,覚えておくべきです.

演習(再帰)

再帰を使って,引数で与えた文字列を逆順にした文字列を返すメソッド static String reverse(String s) を書いてください. プログラミング/8#課題8-2(回文判定)の再帰版になります.

ヒント: 0文字目と1文字目以降に分割し,1文字目以降を再帰で逆順にする.

演習(再帰)の回答例

BinSearchTreeクラスの解説

話をBinSearchTreeクラスに戻します.

検索処理(searchメソッド)

searchメソッドはオーバーロードされていて public Comparable search(Comparable value) とprivate Comparable search(Comparable value, Node root) の2つがあります (解説がややこしくなって少し後悔).

前者は木全体からvalueを探しますが,後者は指定した部分木(頂点(root)を指定)の中から検索します. (前者は公開用なのでpublicに,後者はクラス内部でしか用いないのでprivateにしています)

返り値の型は,insert で登録したものを返すので Comparable です.

後者のsearchメソッドは,以下のようになっています.

  • rootがnullならばnullを返しています.(問題のサイズが0の場合に停止)
  • 部分木のルート(root)とvalueを比較し,等しければrootを返します.等しくない場合,rootの左か右の子ノードを頂点とする部分木から探せばよいので,再帰的にsearchメソッドを呼び出しています (小さいサイズの問題に分割)

挿入処理(insertメソッド)

insertメソッドもsearchメソッドと同様です.

等しくない場合に,再帰呼び出しした結果をroot.leftやroot.rightに代入しているところが難しいかもしれません.これは,root.leftやroot.rightがnullの場合に,再帰で呼び出したinsertが返すNodeへの参照を代入するためにこうしています.

(root.left(or right)がnullでない場合,insertからはroot.left(or right)と同じ値が返されるので,特に代入する必要はありませんが,害もないのでこうしています)

削除処理(removeメソッド)

木からの削除は少し面倒です.削除したいノード r を見つけたら,以下のようにします.

rが子ノードを持たない場合
rを削除 (rの親ノードのleftかrightのいずれか(rを指している方)を,nullにする)
下の図でノード30を削除する場合,親ノードの50のleftをnullにします
rが1つだけ子ノードを持っている場合
rを子ノードに置き換える(rの親ノードのleftかrightのいずれか(rを指している方)を,rの子ノードに置き換える)
下の図でノード60を削除する場合,親ノード50のrightをノード65への参照にします
rが2つ子ノードを持っている場合
rの左の子の部分木の最大のノードをみつけ(nとします),rをnに置き換える.
ただし,nの左ノードを,nの元位置に置き換える (nには右ノードはないはず).
下の図でノード70を削除する場合,左の部分木の最大ノードはノード65なので,ノード70をノード65で置き換えます.
この図では65には左ノードがありませんが,もしある場合は,そのノードを65があった場所(下の図の60の右ノード)に入れます.

画像:BinarySearchTree.png
削除前(再掲)
画像:BinarySearchTreeRemove.png
ノード70の削除後

なお,上のプログラムのremoveメソッドには課題用にバグが潜ませてあるので注意してください.

toStringメソッド

toStringメソッドも再帰を使って,最小のデータから最大のデータまで順番に StringBuilderに追加しています.

toStringでやっているような,木構造を辿る処理を走査(traversal)といい, 再帰を使うことで簡単に書けます.

走査は,左右の部分木と親ノードを処理する順番によって3通りに分類されています.

前順(pre-order)
最初に親ノードを処理し,次に左部分木を辿り,最後に右部分木を辿る方法
間順(in-order)
最初に左部分木を辿り,次に親ノードを処理し,最後に右部分木を辿る方法
toStringはこれを使っています
後順(post-order)
最初に左部分木を辿り,次に右部分木を辿り,最後に親ノードを処理する方法

課題13(2分探索木)

最終課題なので少し多めです.

課題13-1(木の高さ)

再帰を使って2分探索木の木の高さを得る public int height() メソッドを書いてください.

  • 再帰の考え方: あるノードをルートとする部分木の高さは,そのノードの左右の部分木の高さの最大値 + 1
  • データが1つも挿入されていない場合(rootNode == nul)と,1つしか挿入されていない場合の木の高さは0として下さい.

課題13-2(挿入時間の測定)

2分探索木では,左右の部分木の高さがバランスしていればO(log n)時間で挿入・検索できますが(nは木に挿入されているデータ数),バランスしていない場合はそれより悪くなります.

ソートされたデータを順次挿入した場合が最悪で,木が左か右の一方向にしか伸びない状態になり, 実質的に片方向連結リストに縮退してしまいます.この場合,挿入・検索にO(n)時間かかります.

このような状態にならないように考慮された木構造を,平衡木(バランス木)といい,AVL木や赤黒木(Red Black Tree)が有名です.これらの木はアンバランスにならないように木の構造を変化させることで,最悪実行時間がO(log n)になるようにしています.

画像:DegradedBinaryTree.png
縮退した2分探索木

ランダムなデータをn個挿入した2分探索木と,ソートされたデータをn個挿入した(縮退した)2分探索木で,挿入時間がどのように変化するのかを確認しましょう.

nを変化させながら,両方の2分探索木に対して,1個のデータを挿入するために要する時間を測定して下さい(1個だと測定できない場合は適当に増やしてよい).

結果は適切なグラフにプロットして,考察を加えてください.

ランダムなデータが挿入されている場合,挿入処理に要する時間はO(log n)になるはずです. c\times \log_2{n} (cは適当な定数) と同時にプロットして,O(log n)に近いことを示してください.

gnuplotで関数のグラフを描くには以下のようにします.

plot [0:100] [0:200] x*log(x)/log(2), 2*x*log(x)/log(2)
  • [0:100] はX軸の値域,[0:200] はY軸の値域 (省略可能)
  • log関数は自然対数(底はe)なので,底を2にするには底の変換公式を使う(log(x)/log(2)).

データファイルと同時にプロットする場合は,以下のようにします.

plot [0:100] [0:200] x*log(x)/log(2), 'time.dat' with linespoints

課題13-3(ツリーソート)

  1. 二分探索木にデータを登録し,その後で木を走査すると,データをソート(昇順あるいは降順に並べ替え)することができます.この方法はツリーソート(tree sort)と呼ばれています.そこで,Treeクラスに登録されたデータを,昇順にソートされた形で取り出すメソッドpublic DLinkedList getSortedList()を書いてください.結果は連結リストで受け取ります.
    ヒント: toStringと同じように再帰を使って走査します.再帰用に補助用のprivateメソッドを定義します.
  2. この方法でn個のデータをソートするためには,(n個のデータを登録する時間+走査時間)が必要ですが,これはO(nlogn)になります.このことを,実際にn個のデータを登録・走査する時間を測定することで確認してください.
    • 横軸にn,縦軸に処理時間をプロットしたグラフと,c\times n\log_2{n}のグラフを重ねて描く(cは適当な定数).

n個のデータを登録する処理がO(nlogn)になる理由を簡単に述べます.

(走査処理は各ノードを1回ずつ訪問するのでO(n)です. 登録処理と走査処理の時間を合計してもO(nlogn)になる理由は宿題にしておきます.)

  • 空の2分探索木にn個のデータを挿入する時間は,O(\log_2{1}+\log_2{2}+\ldots+\log_2{n})になる.f(n)=\log_2{1}+\log_2{2}+\ldots+\log_2{n}とすると,

f(n) = \log_2(1\times 2\times\ldots\times n) = \log n!

  • ここで,階乗はStirlingの近似公式から,n! \approx \sqrt{2\pi n}\, \frac{n^n}{e^n}=\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n}\qquad(n\gg0) と近似できるので,
  • \log_2{n!} \approx \log_2\sqrt{2\pi}+(n+\frac{1}{2})\log n-n\log_2{e} になる.これをg(n)とする.
  • O(..)の定義から,h(n) = 2nlog2nとして,ある一定以上のnでh(n) − g(n) > 0ならばO(f(n)) = O(nlogn)といえる (O(..)の定義での定数cとして2を選んでいる).
  • h(n)-g(n)=(n-\frac{1}{2})\log_2{n}+(\log_2{e})n-\log_2\sqrt{2\pi}であるが,これはnが一定以上大きければ単調増加で0より大きいことは明らか(気になる人はgnuplotでグラフを描いてみよ).

課題13-4(反復によるinsertとsearch)

insertとsearchを再帰ではなく,反復によって書いてください. (ルートノードから辿っていくだけ)

メソッド名はそれぞれ insertIterative, searchIterative のようにすれば良いでしょう.

課題13-5(バグ探し)

(余裕のある人用)

上の BinTreeSearch クラスは remove 処理にバグがあります.

例えば以下のように20, 30, 10 をこの順に挿入し,20を削除するとデータ構造がおかしくなり, toStringの実行が止まらなくなるはずです(StackOverflowErrorになる).

このバグを修正して下さい(注意: バグはtoStringにあるのではない).

BinSearchTree tree = new BinSearchTree();
tree.insert(20);
tree.insert(30);
tree.insert(10);
tree.remove(20);
System.out.println(tree);

Copyright (C) 2002-2015 Kota Abe, Osaka City University

ナビゲーション