ジェネリクスの補足と2分探索木

先週の復習(Javaでの LinkedList(Deque) のクラスの使い方)

Javaで Deque のような双方向リスト(2重リスト)を使うには、LinkedList<E> を用いる。クラス宣言などで <E> の内側に型Eを指定する機能はジェネリクスと呼ばれる。クラス名に Deque というのもあるけど、LinkedList などの内部の処理を記述するために使われているものなので、ユーザが直接 Deque クラスを使うことはない。

LinkedList でデータ構造を宣言する場合には、LinkedList<E> のように、どのテータ構造を要素にもつ LinkedList なのかを指定する。ただし int,double といったプリミティブ型を型の欄に書くことはできない。こういった場合には Integer,Double といったオブジェクトを記載すること。

また、リストの要素で繰り返しをする場合には、for( 型 item : LinkedList型 ) {…} のように書けば、繰り返しが記述できる。

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        LinkedList<Integer> lst = new LinkedList<Integer>() ;
        lst.addFirst( 11 ) ;  // lst の先頭に11を挿入
        lst.addFirst( 22 ) ;  // lst の先頭に22を挿入
        for( Integer item : lst ) {
            System.out.println( item ) ;
        }
        lst.addLast( 33 ) ;   // lst の末尾に33を追加
        // 全要素の繰り返し
        for( Integer item : lst ) {
            System.out.println( item ) ;
        }
        // 先頭を取り出す
        while( !lst.isEmpty() ) { // isEmpty() : lst の要素が空か判定する
            System.out.println( lst.removeFirst() ) ; // lstの先頭要素を取り出す
        }
    }
}

ジェネリクスを使ったLinkedListの例

LinkedList クラスは双方向リストだけど、単純リスト専用のクラスは無い。このため、これまでの授業のように自分でクラスを宣言して使う必要がある。

ArrayList クラス

これと同じように自由な配列サイズのデータクラスとして、ArrayListクラスも存在する。以下の例は、ArrayList<Integer> の使用例。

ArrayList はジェネリクスを使った、要素数を増やすことができる配列である。

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        ArrayList<Integer> lst = new ArrayList<Integer>() ;
        lst.add( 11 ) ;
        lst.add( 22 ) ;
        for( Integer item : lst ) {
            System.out.println( item ) ;
        }
        lst.add( 33 ) ;
        for( Integer item : lst ) {
            System.out.println( item ) ;
        }
        for( int x = 0 ; x < lst.size() ; x++ ) {
            System.out.println( lst.get( x ) ) ;
        }
    }
}

ジェネリクスを使ったArrayListの例

型推論

上記のプログラムで、LinkedList<Integer> lst = new LinkedList<Integer&gt() ; で宣言しているが、初期化の右辺と左辺で型を揃える必要があるが、複雑な型だとプログラムが煩雑になる。このため、最近の Java には型推論の機能があるため、下の様に型を省略して記述できる。

LinkedList<Integer> lst = new LinkedList<Integer>() ; // 型推論なし
LinkedList<Integer> lst = new LinkedList<>() ;        // 後半のIntegerは明らか
var lst = new LinkedList<Integer>() ; // lst の型は new LinkedList<Integer> で明らか

for( Integer item : lst ) { ... } // 型推論なし
for( var item : lst ) { ... }     // 型推論でIntegerを省略

LinkedListとArrayListの違い

LinkedList や ArrayList は同じ使い方ができるようにadd(int,E),get(int)クラスメソッド等が定義されている。しかし、LinkedList は双方向リスト、ArrayList は配列を使って実装されているので、同じ名前のメソッドでもそのメソッドの処理時間には、以下のような特徴がある。

処理時間のオーダ	LinkedList	ArrayList	メソッドの機能
addLast(E e) / add(E e)	O(1)	O(1)	リストの末尾に要素を追加
add(int index, E e)	指定した場所探しにO(N) その場所に挿入O(1)	指定した場所探しにO(1) その場所に挿入O(N)	リストの指定したインデックスに要素を追加
addFirst(E e) / add(0, E e)	先頭に挿入O(1)	先頭に挿入O(N)	リストの先頭に要素を追加
E get(int index)	O(N)	O(1)	リストのインデックス番目を参照

2分探索法と2分探索木

配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば2分探索法が用いられる。これにより、配列の中からデータを探す処理は、O(log N)となる。(ただし事前にデータが昇順に並んでいる必要あり)

// 2分探索法
import java.util.*;

public class Main {
    public static int bin_search( int[] a , int key , int L , int R ) {
        // Lは探す範囲の左端
        // Rは探す範囲の右端+1(注意!!)
        while( R > L ) {
            int m = (L + R) / 2 ;
            if ( a[m] == key )
                return m ;
            else if ( a[m] > key )
                R = m ;
            else
                L = m + 1 ;
        }
        return -1 ;
    }
    public static void main(String[] args) throws Exception {
        int[] array = {
            11, 13, 27, 38, 42, 64, 72, 81
        } ;
        System.out.println( bin_search( array , 64 , 0 , array.length ) ) ;
        System.out.println( bin_search( array , 14 , 0 , array.length ) ) ;
    }
}

Javaによる2分探索法

// 2分探索法
int array[ 8 ] = { 11, 13 , 27, 38, 42, 64, 72 , 81 } ;

int bin_search( int a[] , int key , int L , int R ) {
   // Lは、範囲の左端
   // Rは、範囲の右端+1 (注意!!)
   while( R > L ) {
      int m = (L + R) / 2 ;
      if ( a[m] == key )
         return m ;
      else if ( a[m] > key )
         R = m ;
      else
         L = m + 1 ;
   }
   return -1 ; // 見つからなかった
}

void main() {
   printf( "%d¥n" , bin_search( array , 0 , 8 ) ) ;
}

一方、リスト構造ではデータ列の真ん中のデータを取り出すには、先頭からアクセスするしかないのでO(N)の処理時間がかかり、極めて効率が悪い。リスト構造のようにデータの追加が簡単な特徴をもったまま、もっとデータを高速に探すことはできないものか？

2分探索木

ここで、データを探すための効率の良い方法として、2分探索木(2分木)がある。以下の木のデータでは、分離する部分に1つのデータと、左の枝(下図赤)と右の枝(下図青)がある。

この枝の特徴は何だろうか？この枝では、中央のデータ例えば42の左の枝には、42未満の数字の枝葉が繋がっている。同じように、右の枝には、42より大きな数字の枝葉が繋がっている。この構造であれば、64を探したいなら、42より大きい→右の枝、72より小さい→左の枝、64が見つかった…と、いう風にデータを探すことができる。

特徴としては、1回の比較毎にデータ件数は、(N-1)/2件に減っていく。よって、この方法であれば、O(log N)での検索が可能となる。これを2分探索木とよぶ。

このデータ構造をプログラムで書いてみよう。

import java.util.*;

class BTreeNode {
    int       data ;
    BTreeNode left ;
    BTreeNode right ;
    
    BTreeNode( int x , BTreeNode l , BTreeNode r ) {
        this.data  = x ;
        this.left  = l ;
        this.right = r ;
    }
}

public class Main {
    public static void print_tree( BTreeNode p ) {
        if ( p != null ) {
            print_tree( p.left ) ;
            System.out.print( p.data + " " ) ;
            print_tree( p.right ) ;
        }
    }
    public static int tree_search( BTreeNode p , int key ) {
        while( p != null ) {
            System.out.println( "p.data=" + p.data + " : key=" + key ) ;
            if ( p.data == key )
                return key ;
            else if ( p.data > key )
                p = p.left ;
            else
                p = p.right ;
        }
        return -1 ;
    }
    public static void main(String[] args) throws Exception {
        BTreeNode top =
            new BTreeNode( 42 ,
                           new BTreeNode( 27 ,
                                          new BTreeNode( 13 , null , null ) ,
                                          new BTreeNode( 38 , null , null ) ) ,
                           new BTreeNode( 72 ,
                                          new BTreeNode( 64 , null , null ) ,
                                          new BTreeNode( 81 , null , null ) ) ) ;
        print_tree( top ) ;
        System.out.println() ;
        if ( tree_search( top , 64 ) >= 0 )
            System.out.println( "Find." ) ;
    }
}

2分探索木

struct Tree {
   struct Tree* left ;
   int          data ;
   struct Tree* right ;
} ;

// 2分木を作る補助関数
struct Tree* tcons( struct Tree* L ,
                    int          d ,
                    struct Tree* R ) {
   struct Tree* n = (struct Tree*)malloc(
                       sizeof( struct Tree ) ) ;
   if ( n != NULL ) { /* (A) */
      n->left = L ;
      n->data = d ;
      n->right = R ;
   }
   return n ;
}

// 2分探索木よりデータを探す
int tree_search( struct List* p , int key ) {
   while( p != NULL ) {
      if ( p->data == key )
         return key ;
      else if ( p->data > key )
         p = p->left ;
      else
         p = p->right ;
   }
   return -1 ; // 見つからなかった
}
struct Tree* top = NULL ;

void main() {
   // 木構造をtcons()を使って直接生成 (B)
   top = tcons( tcons( tcons( NULL , 13 , NULL ) ,
                       27 ,
                       tcons( NULL , 38 , NULL ) ) ,
                42 ,
                tcons( tcons( NULL , 64 , NULL ) ,
                       72 ,
                       tcons( NULL , 81 , NULL ) ) ) ;
   printf( "%d¥n" , tree_search( top , 64 ) ) ;
}

この方式の注目すべき点は、struct Tree {…} で宣言しているデータ構造は、2つのポインタと1つのデータを持つという点では、双方向リストとまるっきり同じである。データ構造の特徴の使い方が違うだけである。

理解度確認

main() の (B) の部分 “top = tcons(…)” において、末端部に NULL を入れる理由を答えよ。

2分木に対する処理

2分探索木に対する簡単な処理を記述してみよう。

// (略)
public class Main {
    public static void print_tree( BTreeNode p ) {
        if ( p != null ) {
            print_tree( p.left ) ;
            System.out.print( p.data + " " ) ;
            print_tree( p.right ) ;
        }
    }
    public static int count( BTreeNode p ) { // データ件数を数える
        // 考えてみよう
    }
    public static int sum( BTreeNode p ) {   // 合計を求める
        // 考えてみよう
    }
    public static int max( BTreeNode p ) {   // 最大値を探す
         // 考えてみよう
    }
    public static void main(String[] args) throws Exception {
        BTreeNode top = /*(略)*/ ;
        print_tree( top ) ;
        System.out.println() ;
        System.out.println( count( top ) ) ; // データ件数を数える
        System.out.println( sum( top ) ) ;   // 合計を求める
        System.out.println( max( top ) ) ;   // 最大値を探す
    }
}

下記のC言語のプログラムをヒントとしておく。

// データを探す
int search( struct Tree* p , int key ) {
   // 見つかったらその値、見つからないと-1
   while( p != NULL ) {
      if ( p->data == key )
         return key ;
      else if ( p->data > key )
         p = p->left ;
      else
         p = p->right ;
   }
   return -1 ;
}
// データを全表示
void print( struct Tree* p ) {
   if ( p != NULL ) {
      print( p->left ) ;
      printf( "%d¥n" , p->data ) ;
      print( p->right ) ;
   }
}
// データ件数を求める
int count( struct Tree* p ) {
   if ( p == NULL )
      return 0 ;
   else
      return 1
             + count( p->left )
             + count( p->right ) ;
}
// データの合計を求める
int sum( struct Tree* p ) {
   if ( p == NULL )
      return 0 ;
   else
      return p->data
             + count( p->left )
             + count( p->right ) ;
}
// データの最大値
int max( struct Tree* p ) {
   while( p->right != NULL )
      p = p->right ;
   return p->data ;
}

これらの関数では、木構造の全てに対する処理を実行する場合には、再帰呼び出しが必要となる。

日	月	火	水	木	金	土
				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