第 13 回 順序木

本日の内容

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

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

13-1. 順序木

順序木の定義

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

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

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

演習13-1

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

ヒント

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

C 言語での順序木

C 言語では順序木を作るのに、構造体とポインタを使います。構造体の中にキー と、値と、左右の子へのポインタを格納します。 そして、値を付け加える関数 add(TREE **t, キー, 値)は、次のように再帰的に 処理します。

1. 注目している木の頂点 (*tの指す構造体) に格納されているキー (*t)->key との大小により左 (*t)->left か右 (*t)->right かを選 択し、どちらかの頂点に対して改めて add((*t)->left, キー, 値) か add((*t)->right, キー, 値) かを再帰的に実行する。
2. もし、(*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){
    *t=(TREE *)malloc(sizeof(TREE));
    if(*t==NULL){
      fprintf(stderr,"メモリーエラー\n");
      exit(1);
    }
    (*t)->key=p;
    (*t)->id=strdup(i);
    if((*t)->id ==NULL){
      fprintf(stderr,"メモリーエラー\n");
      exit(1);
    }
    (*t)->left=NULL;
    (*t)->right=NULL;
  }else{
    if((*t)->key>p){
      add(&((*t)->left),p,i);
    }else{
      add(&((*t)->right),p,i);
    }
  }
}
void show(TREE *t){
  if(t!=NULL){
    show(t->left);
    printf("%s: %d\n",t->id,t->key);
    show(t->right);
  }
}
void deltree(TREE *t){
  if(t!=NULL){
    deltree(t->left);
    deltree(t->right);
    free(t->id);
    free(t);
  }
}
int main(void){
  TREE *t=NULL;
  add(&t,100,"02kc963");
  add(&t,62,"02kc903");
  add(&t,85,"02kc923");
  add(&t,73,"02kc911");
  add(&t,85,"02kc987");
  show(t);
  deltree(t);
  return 0;
}

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

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

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

void showstructure(TREE *t,char *depth){
  char *p,*q;
  if(t!=NULL){
    if((p=(char *)malloc((strlen(depth)+2)*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

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

演習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;
  }else{
    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=(TREE *)malloc(sizeof(TREE));
    (*t)->key=k;
    (*t)->num=i;
    (*t)->left=NULL;
    (*t)->right=NULL;
  }else{
    res=strcmp((*t)->key,k);
    if(res==0){
      (*t)->num=i;
    }else if(res>0){
      return set(&((*t)->left),k,i);
    }else{
      return set(&((*t)->right),k,i);
    }
  }
}
void show(TREE *t){
  if(t!=NULL){
    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;
}