データをO(log N)で検索するための2分探索木以外の2分木のデータ構造について解説を行う。

意思決定木

意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。

   ((意思決定木の例:小さい子供が発熱した時))
　　　　　　　38.5℃以上の発熱がある？
　　　　　　no／　　　　　　　　　＼yes
　　　元気がある？　　　　　　　　むねがひいひい？
　yes／　　　　＼no　　　　　　no／　　　　　＼yes
様子をみる　氷枕で病院　　解熱剤で病院　　速攻で病院

このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じである。左右に枝のあるものは質問であり、yesの枝もnoの枝もない末端は最終決断を表す。このようなデータ構造は意思決定木と呼ばれ、質問と決断の処理は以下のように記述ができる。

import java.util.* ;
import java.util.Scanner ;

class TreeNode {
    String qa ;
    TreeNode    yes ;
    TreeNode    no ;
    
    TreeNode( String s , TreeNode y , TreeNode n ) {
        this.qa  = s ;
        this.yes = y ;
        this.no  = n ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner( System.in ) ;
        TreeNode top =
            new TreeNode( "38.5℃以上の発熱がある?" ,
                          new TreeNode( "胸がひぃひぃ?" ,
                                        new TreeNode( "速攻で病院" ,   null , null ) ,
                                        new TreeNode( "解熱剤で病院" , null , null ) ) ,
                          new TreeNode( "元気がある?" ,
                                        new TreeNode( "様子をみる",    null , null ) ,
                                        new TreeNode( "氷枕で病院",    null , null ) ) ) ;
        TreeNode p = top ;
        while( p.yes != null || p.no != null ) {
            System.out.println( "Question:" + p.qa ) ;
            if ( sc.nextInt() == 1 ) {
                System.out.println( "yes" ) ;
                p = p.yes ;
            } else {
                System.out.println( "no" ) ;
                p = p.no ;
            }
        }
        System.out.println( "Answer:" + p.qa ) ;
    }
}

• 意思決定木(Paiza.io)

struct Tree {
   char *qa ;
   struct Tree* yes ;
   struct Tree* no ;
} ;
struct Tree* dtree( char *s ,
                    struct Tree* l , struct Tree* r )
{  struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->qa = s ;
      n->yes = l ;
      n->no = r ;
   }
   return n ;
}
void main() {
   struct Tree* p =
      dtree( "38.5℃以上の発熱がある?" ,
             dtree( "胸がひぃひぃ?" ,
                    dtree( "速攻で病院",  NULL,NULL ) ,
                    dtree( "解熱剤で病院",NULL,NULL ) ) ,
             dtree( "元気がある?" ,
                    dtree( "様子をみる",  NULL,NULL ) ,
                    dtree( "氷枕で病院",  NULL,NULL ) ) ) ;
   // 決定木をたどる
   struct Tree* d = p ;
   while( d->yes != NULL || d->no != NULL ) {
      printf( "%s¥n" , d->qa ) ;
      scanf( "%d" , &ans ) ;
      // 回答に応じてyes/noの枝に進む。
      if ( ans == 1 )      // yesを選択
         d = d->yes ;
      else if ( ans == 0 ) // noを選択
         d = d->no ;
   }
   // 最終決定を表示
   printf( "%s¥n" , d->qa ) ;
}

• decision-tree.cxx

2分木の応用として次週以降に式の表現の説明を行うけど、その前に計算式の一般論の説明を行う。

逆ポーランド記法

一般的に 1*2 + 3*4 と記載すると、数学的には演算子の優先順位を考慮して、(1*2)+(3*4) のように乗算を先に行う。このような優先順位を表現する時に、()を使わない方法として、逆ポーランド記法がある。

演算子の書き方には、前置記法、中置記法、後置記法があり、後置記法は、「2と3を掛ける、それに1を加える」と捉えると、日本語の処理と似ている。

中置記法 1+2*3
前置記法 +,1,*,2,3
後置記法 1,2,3,*,+　　# 1と「2と3をかけた値」をたす。

後置記法は、一般的に逆ポーランド記法(Reverse Polish Notation)とも呼ばれ、式をコンピュータで実行する際の処理と似ている。

演算子の右結合・左結合

例えば、”1/2*3″という式が与えられたとする。この結果は、1/6だろうか？3/2だろうか？

一般的な数学では、優先順位が同じ演算子が並んだ場合、左側から計算を行う。つまり”1/2*3″は、”(1/2)*3″を意味する。こういった左側の優先順位が高い演算子は左結合の演算子という。

ただしC言語やJavaでは、”a = b = c = 0″ と書くと、”a = (b = (c = 0))” として扱われる。こういった代入演算子は、 右結合の演算子である。

理解度確認

以下の式を指定された書き方で表現せよ。

逆ポーランド記法 1,2,*,3,4,*,+ を中置記法で表現せよ。
中置記法 (1+2)*3-4*5 を逆ポーランド記法で表現せよ。

以前の情報処理技術者試験では、スタックの概念の理解の例題として、逆ポーランド記法への変換アルゴリズムのプログラム作成が出題されることが多かったが、最近は出題されることはなくなってきた。

2分探索木にデータを追加

前回の2分探索木では、基本的な説明ということで、木の生成では直接木構造を生成していた。しかし、本来であれば、扱うデータに応じて木を生成することが求められる。

Javaの場合

以下の Javaのプログラムの関数 entry( … ) では、再帰を使いながら、value を追加した木を返す関数で記述した。

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 ) {
            System.out.print( "(" ) ;
            print_tree( p.left ) ;
            System.out.print( p.data ) ;
            print_tree( p.right ) ;
            System.out.print( ")" ) ;
        }
    }
    public static BTreeNode entry( BTreeNode p , int value ) {
        if ( p == null ) {
            return new BTreeNode( value , null , null ) ;
        } else {
            if ( p.data == value )
                ; // 何もしない
            else if ( p.data > value )
                p.left = entry( p.left , value ) ;
            else
                p.right = entry( p.right , value ) ;
            return p ;
        }
    }
    public static void main(String[] args) throws Exception {
        BTreeNode top = null ;
        top = entry( top , 42 ) ;
        top = entry( top , 27 ) ;
        top = entry( top , 72 ) ;
        top = entry( top , 13 ) ;
        top = entry( top , 38 ) ;
        top = entry( top , 64 ) ;
        top = entry( top , 81 ) ;
        print_tree( top ) ; System.out.println() ;
    }
}
// 動作結果
// (((13)27(38))42((64)72(81)))

• 2分探索木へのデータの追加(Paiza.io)

しかしながらこのプログラムでは、以下のように小さい順序でデータを与えると、右に伸びる木が作られてしまう。

    // 不均一な木ができる場合
    public static void main(String[] args) throws Exception {
        BTreeNode top = null ;
        top = entry( top , 13 ) ;
        top = entry( top , 27 ) ;
        top = entry( top , 38 ) ;
        top = entry( top , 42 ) ;
        top = entry( top , 64 ) ;
        top = entry( top , 72 ) ;
        top = entry( top , 81 ) ;
        print_tree( top ) ; System.out.println() ;
    }
    // 動作結果
    // (13(27(38(42(64(72(81)))))))

このような不均一な木が生成されてしまうと、本来であればデータ探索の処理時間は O( log N ) であるが、最悪の状態では O( N ) となってしまう。

AVL木

こういった偏った木が生成されてしまった時には、以下のような処理を加えると、不均一な状態を改善できる。

depth() 関数は与えられた木の深さを求める関数であり、左枝と右枝が大きく違う場所で 木の右回転を行う rotate_right() を実行する。

public class Main {
    public static int depth( BTreeNode p ) { // 木の深さを求める
        if ( p == null ) {
            return 0 ;
        } else {
            int l = depth( p.left ) ;
            int r = depth( p.right ) ;
            if ( l > r )
                return 1 + l ;
            else
                return 1 + r ;
        }
    }
    public static BTreeNode rotate_right( BTreeNode p ) {
        BTreeNode q = p.left ;      //      p
        BTreeNode r = q.right ;     //    ／ ＼
        q.right = p ;               //   q
        p.left  = r ;               // ／ ＼
        return q ;                  //      r
    }
    public static void main(String[] args) throws Exception {
        BTreeNode top = null ;
        top = entry( top , 86 ) ;
        top = entry( top , 53 ) ;
        top = entry( top , 92 ) ;
        top = entry( top , 11 ) ;
        top = entry( top , 65 ) ;
        top = entry( top , 22 ) ;
        // 不均一な状態を確認
        print_tree( top ) ;
        System.out.println() ;
        System.out.println( "p.left=" + depth( top.left ) ) ;
        System.out.println( "p.right=" + depth( top.right ) ) ;
        // top の右回転を実行
        top = rotate_right( top ) ;
        // 改善された状態を確認
        print_tree( top ) ;
        System.out.println() ;
        System.out.println( "p.left=" + depth( top.left ) ) ;
        System.out.println( "p.right=" + depth( top.right ) ) ;
    }
}

• AVL木と右回転(Paiza.io)

上記のプログラムでは、左枝が3段で右枝が1段であり不均一な状態となっている。

そこで、最上段の86の左枝を上に移動させるように枝の繋ぎ方を rotate_right() により変更している。実際には、繋ぎ変えを左回転させる処理も作る必要がある。

このように、木の枝の深さが不均一な場所で、このような処理を加えて均一化を図った木構造は AVL 木と呼ぶ。

AVL木は、考案した Velski と Landis の名前が由来(Adelson-Velskii and Landis’ tree)

2分ヒープ(binary heap)

2分探索木では、１つのノードにつき2つのポインタを持ち、データ1件あたりのメモリの使用量が多い。通常の「配列の先頭から昇順にデータを並べる2分探索法」では、途中にデータを挿入する場合、データを後ろにずらす必要があるため、O(N)の処理時間を要する。

これらの問題の解決法の１つとして、2分ヒープがある。左右に均一に成長している2分探索木で、上から番号を以下の様に振ると、i番目のデータの左の枝は 2×i+1 番目、右の枝は 2×i+2 番目であることが判る。

このような順序で配列にデータを保存する方法が2分ヒープである。この方式ならアルゴリズムの説明は省略するが、入れるべきノードの場所でのデータの入れ替えで実現できるため O( log( N ) )で挿入が可能となる。

import java.util.*;

public class Main {
    public static int find_heap( int[] array , int idx , int key ) {
        while( idx < array.length ) { if ( array[ idx ] == key ) return idx ; // 見つかった else if ( array[ idx ] > key )
                idx = idx*2 + 1 ;
            else
                idx = idx*2 + 2 ;
        }
        return -1 ; // 見つからなかった
    }
    public static void main(String[] args) throws Exception {
        int[] a = { 53 , 11 , 86 , 10 , 22 , 65 , 92 } ;
        System.out.println( find_heap( a , 0 , 22 ) ) ;
    }
}

• 2分ヒープ(Paiza.io)

レポート課題

以下のようなデータを扱う2分探索木のプログラムを作成せよ。以下の箇条書き番号の中から、(出席番号 % 3+1)のデータについてプログラムを作ること。

1. 名前(name)と電話番号(phone)
2. 名前(name)と誕生日(year,mon,day)
3. 名前(name)とメールアドレス(mail)

プログラムは以下の機能を持つこと。

• 1行1件でデータを入力し、2分木に追加できること。
• 全データを昇順(or降順)で表示できること。
• 検索条件を入力し、目的のデータを探せること。

レポートでは、(a)プログラムリスト,(b)その説明,(c)動作検証結果,(d)考察 を記載すること。