今日は、2分木を用いた式の表現とB木について説明を行う。 前回、２項演算子の話で、逆ポーランド記法などの説明をしたので、 そのプログラム例から話を行う。

逆ポーランド記法のスタック処理

逆ポーランド記法による式は、スタックを用いると簡単にその値を求める処理が記述できる。

// スタックの記述
int stack[ 10 ] ;
int *sp = stack ;
void push( int x ) {
*sp++ = x ;
}
int pop() {
return *--sp ;
}
// 逆ポーランド記法の式を処理する関数
int eval( char* s ) {
for( ; *s != '
// スタックの記述
int stack[ 10 ] ;
int *sp = stack ;
void push( int x ) {
*sp++ = x ;
}
int pop() {
return *--sp ;
}
// 逆ポーランド記法の式を処理する関数
int eval( char* s ) {
for( ; *s != '\0' ; s++ ) {
if ( *s >= '0' && *s <= '9' ) {
push( *s - '0' ) ;
} else {
switch( *s ) {
case '+' : push( pop() + pop() ) ; break ;
case '*' : push( pop() * pop() ) ; break ;
}
}
}
return pop() ;
}
void main() {
printf( "%d\n" , eval( "12+3*" ) ) ;
}
' ; s++ ) {
if ( *s >= '0' && *s <= '9' ) {
push( *s - '0' ) ;
} else {
switch( *s ) {
case '+' : push( pop() + pop() ) ; break ;
case '*' : push( pop() * pop() ) ; break ;
}
}
}
return pop() ;
}
void main() {
printf( "%d\n" , eval( "12+3*" ) ) ;
}

2分木による式の表現

これが本来説明したい2分木による式の表現。 データ構造を簡単にしたいので、 左右の枝がNULLなら、opr部に整数値、非NULLなら、opr部に演算子の文字コードとする。 この方式であれば、要素名は異なるものの、２分木のデータ宣言とまるっきり同じ。

// まずはデータ構造の宣言と、そのデータを生成する補助関数。
struct Expr {
int opr ;
struct Expr* left ;
struct Expr* right ;
} ;
// 数値の場合
struct Expr* Integer( int x ) {
struct Expr* ans ;
ans = (struct Expr*)malloc( sizeof( struct Expr ) ) ;
if ( ans != NULL ) {
ans->opr = x ;
ans->left = NULL ;
ans->right = NULL ;
}
return ans ;
}
// 演算子の場合
struct Expr* Operator( int op ,
struct Expr* l ,
struct Expr* r ) {
struct Expr* ans ;
ans = (struct Expr*)malloc( sizeof( struct Expr ) ) ;
if ( ans != NULL ) {
ans->opr = op ;
ans->left = l ;
ans->right = r ;
}
return ans ;
}

データ構造を作る処理が記述できたところで、その式の表示と、その式の計算。

// 2分木による式を表示する関数。
// 演算子の優先順位を無視して、全てにカッコをつける
void print_expr( struct Expr* e ) {
if ( e->left == NULL && e->right == NULL ) {
printf( "%d" , e->opr ) ;
} else {
printf( "(" ) ;
print_expr( e->left ) ;
printf( "%c" , e->opr ) ;
print_expr( e->right ) ;
printf( ")" ) ;
}
}
// 式の値を計算する関数
int eval_expr( struct Expr* e ) {
if ( e->left == NULL && e->right == NULL ) {
return e->opr ;
} else {
switch( e->opr ) {
case '+' :
return eval_expr( e->left )
+ eval_expr( e->right ) ;
case '*' :
return eval_expr( e->left )
* eval_expr( e->right ) ;
}
}
}
// 実際に計算させてみる。
void main() {
struct Expr* e
= Operator( '*' ,
Integer( 1 ) ,
Operator( '+' ,
Integer( 2 ) ,
Integer( 3 ) ) ) ;
printf( "%d\n" , eval_expr( e ) ) ;
}

B木

2分木で式の表現を説明したが、枝の数は左右２本と限定する必要はあるのだろうか？ 2本をN本に拡張したものが、B木と呼ばれる。

// 位数2のBTree
struct BTree {
int size ; // B木のノード内のデータ数
int d[ 4 ] ; // 実際のデータ
struct BTree* p[ 5 ] ; // d[i] < ● < d[i+1] のデータは、
// p[i+1]の枝に保存
} ;

B木では、枝に関する条件に加え、位数Nの場合では、ノード内のデータ件数を必ず、 N <= (データ件数) <=2N を満たすようにする。

データの追加で、ノード内のデータ件数が2Nを越える場合には、 加えるデータを含め、データ順に並べた時の中央値を上位ノードに移動させ、 ノードを、左右に分割を行う。

|
　　[ 12 | 21 | 23 | 29 ]  ← 18を加えるなら、12,18,21,23,29 で、
　　　　　　　　　　　　　　　　　21を上位に上げる。
[ 8 |(21)| 39 | × ]
|    |
|    +---------------+
|                    |
[ 12 | 18 | × | × ]  [ 23 | 29 | × | × ]