第 13 回順序木

本日の内容

13-1. 順序木
13-2. 連想配列

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

13-1. 順序木

順序木の定義

順序木は、値の大小に基づいて値を格納する木であり、低いコストで値を小さい順に取り出すことが可能になります。順序木とは、各頂点に値を持つ二分木のうち、次の性質を持つものです。

左の枝に接続している全ての頂点の要素は、この頂点の要素より小さい。
右の枝に接続している全ての頂点の要素は、この頂点の要素より大きい。

このような性質を持っている木に対して新たな値を格納することを考えます。値を格納できる場所を探す際、各頂点の持つ値と比較していくことで、頂点の右の枝の方面か左の枝の方面か選ぶことができます。すると、木の深さ分だけ値を比較することで挿入可能な場所を捜し出せることになります。木の深さは、都合が良い場合で全頂点数 N に対して log N 程度になりますので、挿入の手間もその程度で収まります。また、最小、最大の値もそれぞれ木の一番左と右の要素になりますから、やはり木の深さ程度の手間で見つけられます。

演習13-1

値 1, 2, 3, 4 を持つ順序木を全て書きだしなさい。

ヒント

全ての二分木の形に対して、それぞれに格納の方法が一通りだけ可能です。

C 言語での順序木

頂点の追加時に管理変数を書き換える手法

順序木も線形リスト同様に、根を指す管理変数を引数に関数を記述します。そのため、線形リスト同様に管理変数がNULLである場合とそうでない場合を考える必要があります。線形リストの場合は末端が一つなので、nilと呼ぶダミー頂点を用意して、それを番兵や既挿入頂点として扱うことで、管理変数の書き換えを避けることができました。しかし、二分木の場合、既挿入頂点を用意すると、その頂点にデータを入れる度に、新たな既挿入頂点が2個必要となるため、最終的に必要となる既挿入頂点が、(データの入っている頂点数)×2、つまり完全二分木では、木の深さを k とすると、 2^k-1×2 = 2^k と、全頂点と同じ数だけ必要となります。このようなアルゴリズムの工夫は、プログラムは単純になっても、計算効率は逆に悪くなるため、避けることとします。

そのため、頂点の追加においては、管理変数であろうと関数内において書き換えることとします。これを実現するには管理変数のポインターを関数に渡す必要があります。管理変数自体がポインター変数なので、頂点を追加する関数の管理変数の引数はダブルポインタになります。また、主プログラムにおいては、管理変数はポインタとして宣言し、頂点を追加するときは、管理変数の番地を引数として与えて関数呼び出しをすることとします。つまり、順序木を作るのに、構造体とポインタを使い、構造体の中にキーと、値と、左右の子へのポインタを格納します。そして、値を付け加える関数 add(TREE **t, キー, 値)は、次のように再帰的に処理します。

注目している木の頂点 (*tの指す構造体) に格納されているキー (*t)->key との大小により左 (*t)->left か右 (*t)->right かを選択し、どちらかの頂点に対して改めて add((*t)->left, キー, 値) か add((*t)->right, キー, 値) かを再帰的に実行する。
もし、(*t) が NULL だったらそこに頂点を付け加える。

なお、頂点を付け加える処理で NULL だったポインタの値を書き換えたいので、ポインタの格納されている番地を引数に渡してポインタの内容を書き換えてます。


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tr {
  int key;
  char *id;
  struct tr *left,*right;
} TREE;
void add(TREE **t, int p, char *i){
  if(*t==NULL){
    if((*t = malloc(sizeof(TREE)))==NULL){
      fprintf(stderr,"メモリーエラー\n");
      exit(1);
    }
    (*t)->key=p;
    if(((*t)->id = _strdup(i)) ==NULL){
      fprintf(stderr,"メモリーエラー\n");
      exit(1);
    }
    (*t)->left=NULL;
    (*t)->right=NULL;
    return;
  }
  if((*t)->key>p){
    add(&((*t)->left),p,i);
  }else{
    add(&((*t)->right),p,i);
  }
}
void show(TREE *t){
  if(t==NULL){
    return;
  }
  show(t->left);
  printf("%s: %d\n",t->id,t->key);
  show(t->right);
}
void deltree(TREE *t){
  if(t==NULL){
    return;
  }
  deltree(t->left);
  deltree(t->right);
  free(t->id);
  free(t);
}
int main(void){
  TREE *t=NULL;
  add(&t,100,"07kc963");
  add(&t,62,"07kc903");
  add(&t,85,"07kc923");
  add(&t,73,"07kc911");
  add(&t,85,"07kc987");
  show(t);
  deltree(t);
  return 0;
}


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tr {
  int key;
  char *id;
  struct tr *left,*right;
} TREE;
void add(TREE **t, int p, char *i){
  if(*t==NULL){
    if((*t = malloc(sizeof(TREE)))==NULL){
      fprintf(stderr,"メモリーエラー\n");
      exit(1);
    }
    (*t)->key=p;
    if(((*t)->id = strdup(i)) ==NULL){
      fprintf(stderr,"メモリーエラー\n");
      exit(1);
    }
    (*t)->left=NULL;
    (*t)->right=NULL;
    return;
  }
  if((*t)->key>p){
    add(&((*t)->left),p,i);
  }else{
    add(&((*t)->right),p,i);
  }
}
void show(TREE *t){
  if(t==NULL){
    return;
  }
  show(t->left);
  printf("%s: %d\n",t->id,t->key);
  show(t->right);
}
void deltree(TREE *t){
  if(t==NULL){
    return;
  }
  deltree(t->left);
  deltree(t->right);
  free(t->id);
  free(t);
}
int main(void){
  TREE *t=NULL;
  add(&t,100,"07kc963");
  add(&t,62,"07kc903");
  add(&t,85,"07kc923");
  add(&t,73,"07kc911");
  add(&t,85,"07kc987");
  show(t);
  deltree(t);
  return 0;
}

_strdup は文字配列を別の領域を確保してコピーするものです。メモリーが確保できなかった時は NULL を返します。

deltree は作成した木を消す関数です。プログラムが終了すると使用した領域はすべて OS が自動的に回収しますが、プログラミングのテクニックとして作成したものを消す方法は学んでおくべきですので、可能な限り malloc, _strdup などで確保したメモリーはその都度消すようにして下さい。

strdup は文字配列を別の領域を確保してコピーするものです。メモリーが確保できなかった時は NULL を返します。

deltree は作成した木を消す関数です。プログラムが終了すると使用した領域はすべて OS が自動的に回収しますが、プログラミングのテクニックとして作成したものを消す方法は学んでおくべきですので、可能な限り malloc, strdup などで確保したメモリーはその都度消すようにして下さい。

頂点を追加した後に管理変数を書き換える方法

前項のアルゴリズムでは、管理変数 t (TREE*型)に対して、項目を追加するのに、管理変数の書き変えを許すのに次のような呼び出しを行いました。

add(&t,key,value);

これはダブルポインタなので、糖衣構文が機能せずに、直感的に見通しの悪い記述になっていました。そこで、管理変数の書き変えを関数内で行わず、要素追加関数が常に新しい管理変数の値を返すようにすると、ダブルポインターを避けることができます。つまり関数呼び出しを次のようにします。

t=add(t,key,value);

この仕様を満たすプログラムを以下に示します。


TREE* add(TREE* t, int key, char* value){
  TREE* p;
  if(t==NULL){
    if((p = malloc(sizeof(TREE)))==NULL){
      fprintf(stderr,"メモリーエラー\n");
      exit(1);
    }
    p->key=key;
    if((p->id = _strdup(value))==NULL){
      fprintf(stderr,"メモリーエラー\n");
      exit(1);
    }
    p->left=NULL;
    p->right=NULL;
    return p;
  }
  if(t->key > key){
    t->left = add(t->left,key,value);
    return t;
  }else{
    t->right = add(t->right,key,value);
    return t;
  }
}


TREE* add(TREE* t, int key, char* value){
  TREE* p;
  if(t==NULL){
    if((p = malloc(sizeof(TREE)))==NULL){
      fprintf(stderr,"メモリーエラー\n");
      exit(1);
    }
    p->key=key;
    if((p->id = strdup(value))==NULL){
      fprintf(stderr,"メモリーエラー\n");
      exit(1);
    }
    p->left=NULL;
    p->right=NULL;
    return p;
  }
  if(t->key > key){
    t->left = add(t->left,key,value);
    return t;
  }else{
    t->right = add(t->right,key,value);
    return t;
  }
}

管理変数を構造体に含め、構造

管理変数を構造体に含め、関数呼び出しをその構造体の変数で呼び出すようにすると、ダブルポインタの運用無しでプログラムを書くことができます。但し、構造体を二つ使うことになるのと、初期化に工夫が必要になります。


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node {
  int key;
  char* value;
  struct node *left, *right;
} NODE;
typedef struct {
  NODE* root;
}TREE;

NODE* newnode(int i, char* k){
  NODE* n = malloc(sizeof(NODE));
  n->key = i;
  n->value = _strdup(k);
  n->left = NULL;
  n->right = NULL;
  return n;
}
void addTree(NODE *t, int i, char* k){
  int res;
  if (t->key > i){
    if (t->left == NULL){
      t->left = newnode(i,k);
    }
    else{
      addTree(t->left, i, k);
    }
  }
  else{
    if (t->right == NULL){
      t->right = newnode(i, k);
    }
    else{
      addTree(t->right, i, k);
    }
  }
}
void add(TREE* t, int i, char* k){
  if (t->root == NULL){
    t->root = newnode(i, k);
  }
  else{
    addTree(t->root, i, k);
  }
}
void showtree(NODE *t){
  if (t == NULL){
    return;
  }
  showtree(t->left);
  printf("%d: %s\n", t->key, t->value);
  showtree(t->right);
}
void show(TREE t){
  showtree(t.root);
}
void delTree(NODE* t);
void del(TREE t){
  if(t.root==NULL) return ;
  delTree(t.root);
}
void delTree(NODE* t){
  if(t==NULL){
    return;
  }
  delTree(t->left);
  delTree(t->right);
  free(t->value);
  free(t);
}

int main(void){
  TREE t={NULL};
  add(&t,100,"07kc963");
  add(&t,62,"07kc903");
  add(&t,85,"07kc923");
  add(&t,73,"07kc911");
  add(&t,85,"07kc987");
  show(t);
  del(t);
  return 0;
}


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node {
  int key;
  char* value;
  struct node *left, *right;
} NODE;
typedef struct {
  NODE* root;
}TREE;

NODE* newnode(int i, char* k){
  NODE* n = malloc(sizeof(NODE));
  n->key = i;
  n->value = strdup(k);
  n->left = NULL;
  n->right = NULL;
  return n;
}
void addTree(NODE *t, int i, char* k){
  int res;
  if (t->key > i){
    if (t->left == NULL){
      t->left = newnode(i,k);
    }
    else{
      addTree(t->left, i, k);
    }
  }
  else{
    if (t->right == NULL){
      t->right = newnode(i, k);
    }
    else{
      addTree(t->right, i, k);
    }
  }
}
void add(TREE* t, int i, char* k){
  if (t->root == NULL){
    t->root = newnode(i, k);
  }
  else{
    addTree(t->root, i, k);
  }
}
void showtree(NODE *t){
  if (t == NULL){
    return;
  }
  showtree(t->left);
  printf("%d: %s\n", t->key, t->value);
  showtree(t->right);
}
void show(TREE t){
  showtree(t.root);
}
void delTree(NODE* t);
void del(TREE t){
  if(t.root==NULL) return ;
  delTree(t.root);
}
void delTree(NODE* t){
  if(t==NULL){
    return;
  }
  delTree(t->left);
  delTree(t->right);
  free(t->value);
  free(t);
}

int main(void){
  TREE t={NULL};
  add(&t,100,"07kc963");
  add(&t,62,"07kc903");
  add(&t,85,"07kc923");
  add(&t,73,"07kc911");
  add(&t,85,"07kc987");
  show(t);
  del(t);
  return 0;
}

木の構造

なお、このままでは木の構造がわかりづらいので、木のどの頂点にあるかを表示する関数 showstructure()を作りました。呼び出す時は、木の根の頂点へのポインタを t として showstructure(t,""); として呼び出します。


void showstructure(TREE *t,char *depth){
  char *p,*q;
  int buffersize;
  if(t==NULL){
    return;
  }
  buffersize = strlen(depth)+2;
  if((p=malloc(buffersize*sizeof(char)))==NULL){
    fprintf(stderr,"メモリーエラー\n");
    exit(1);
  }
  printf("%s: %d\n",depth,t->key);
  strcpy_s(p,buffersize,depth);
  for(q=p;*q!='\0';q++);
  *(q+1)='\0';
  *q='l';
  showstructure(t->left,p);
  *q='r';
  showstructure(t->right,p);
  free(p);
}


void showstructure(TREE *t,char *depth){
  char *p,*q;
  int buffersize;
  if(t==NULL){
    return;
  }
  buffersize = strlen(depth)+2;
  if((p=malloc(buffersize*sizeof(char)))==NULL){
    fprintf(stderr,"メモリーエラー\n");
    exit(1);
  }
  printf("%s: %d\n",depth,t->key);
  strcpy(p,depth);
  for(q=p;*q!='\0';q++);
  *(q+1)='\0';
  *q='l';
  showstructure(t->left,p);
  *q='r';
  showstructure(t->right,p);
  free(p);
}

演習13-2

上のプログラムを点数の大きい順に出力するように改造しなさい。

演習13-3

上のプログラム例において、 showstructure() を呼び出しなさい。
表示された結果を元に、木の構造を求め図に書きなさい。

演習13-4

特定の値と一致するキーを持つ頂点のポインタを返す関数 find を作りなさい。

13-2. 連想配列

木構造を利用して、文字列がキーとなる配列を作ります。 set(ポインタの番地, キー, 値) と get(ポインタ, キー) で値の格納、取り出しを行います。


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tr {
  char *key;
  int num;
  struct tr *left,*right;
} TREE;
int get(TREE *t, char *k){
  int res;
  if(t==NULL){
    return 0;
  }
  res=strcmp(t->key,k);
  if(res==0){
    return t->num;
  }else if(res>0){
    return get(t->left,k);
  }else{
    return get(t->right,k);
  }
}
void set(TREE **t, char *k, int i){
  int res;
  TREE *newnode;
  if(*t==NULL){
    *t=malloc(sizeof(TREE));
    (*t)->key=k;
    (*t)->num=i;
    (*t)->left=NULL;
    (*t)->right=NULL;
    return;
  }
  res=strcmp((*t)->key,k);
  if(res==0){
    (*t)->num=i;
  }else if(res>0){
    set(&((*t)->left),k,i);
  }else{
    set(&((*t)->right),k,i);
  }
}
void show(TREE *t){
  if(t==NULL){
    return;
  }
  show(t->left);
  printf("%s: %d\n",t->key,t->num);
  show(t->right);
}
int main(void){
  TREE *t=NULL;
  set(&t,"abc",50);
  set(&t,"def",20);
  printf("%d\n",get(t,"abc"));
  printf("%d\n",get(t,"def"));
  return 0;
}

演習13-5

文字列の頻度を表示するプログラムを書きなさい。文字列は配列に入っているとし、表示は「文字列:頻度」の形式で出しなさい。

入力例


  char *data[]={"abc","def","efg","abc","abc","efg",NULL};

出力例

abc: 3
def: 1
efg: 2

C++ での順序木

C++ では外見上、木構造を提供していませんが、 map と multimap は内部的に順序木を使ってます。格納できる値はキーと値の二種類です。map は重複するキーを許さず、 multimap は重複キーを許します。 map や multimap を使うには引数に、キーの型、値の型、キーの比較をするクラス less テンプレートを指定します。値を挿入する insert メソッドを使うには挿入するための特別な型のオブジェクトを作らなければなりません。そのため、map や multimap で作った型 x に対して、x::value_type という別のクラスを用意し、このインスタンスを使って挿入します。 iterator は begin(), end(), lower_bound(), upper_bound() などのメソッドで得られます。なお、 map ではさらに オブジェクト[キー] という構文で検索、更新が可能です。以下にサンプルプログラムを示します。


#include <iostream>
#include <string>
#include <map>
typedef std::multimap<int ,std::string , std::less<int> > MMAP;
typedef MMAP::value_type Mvalue;
std::ostream& operator<<(std::ostream& os, const Mvalue& p)const{
  os << p.second << ": " << p.first;
  return os;
}
int main(void){
  MMAP m;
  m.insert(Mvalue(100,"02kc963"));
  m.insert(Mvalue(62,"02kc903"));
  m.insert(Mvalue(85,"02kc923"));
  m.insert(Mvalue(73,"02kc911"));
  m.insert(Mvalue(85,"02kc987"));
  std::cout << "size = " << m.size() << std::endl;
  for(MMAP::iterator i=m.begin(),end=m.end(); i!=end; ++i){
    std::cout << *i << std::endl;
  }
  std::cout << "---------------------------------" << std::endl;
  for(MMAP::iterator i=m.lower_bound(70), end=m.upper_bound(90);
      i!=end; ++i){
    std::cout << *i << std::endl;
  }
}

補足

また、上のプログラムではcout << Mvalue の値; という構文で値を表示できるように以下のような関数を用意しました。 C++ 言語ではこのように演算子を再定義できます(乱用すると混乱のもとですが)。一般のオブジェクト指向の構文では、オブジェクトとオブジェクトの間に入る演算子は、左側のオブジェクトのメソッドになります。そのため、ここで定義するのも、 cout のオブジェクト型である ostream クラスの演算子 << の再定義になります。なお、この場合は Mvalue 型の表示にパブリックメンバしか使わなかったので、この定義だけで済みますが、もしプライベートメンバを使用しなければならない時は、そのクラスの宣言時にこの演算子の再定義に対してfried 指定をする必要があります。


std::ostream& operator<<(std::ostream& os, const Mvalue& p){
  os << p.second << ": " << p.first;
  return os;
}

坂本直志 <[email protected]>
東京電機大学工学部情報通信工学科

第 13 回 順序木