第 8 回木

本日の内容

8-1. 順序木
8-2. クイックソート
8-3. バランス木
8-4. ヒープ木

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

8-1. 順序木

順序木の定義

順序木を使うと、与えた要素を低いコストで順序順にとりだすことが可能になります。順序木とは、各頂点に値を持つ二分木のうち、次の性質を持つものです。

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

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

演習8-1

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

ヒント

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

C++ での順序木

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


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

なお、ここで用いる std::less というテンプレートは以下のように定義されています。演算子 < が定義されている型に対して、このテンプレートはクラス(struct)を定義します。そして、そのインスタンス x に対して、元の型の値 y,z を引数にとる x(y,z) で y<z の値を返すものです。下に評価用のテストプログラムを示します。

stl_function.h


template <class _Tp>
struct less : public binary_function<_Tp,_Tp,bool> 
{
  bool operator()(const _Tp& __x, const _Tp& __y) const { return __x < __y; }
};


#include <iostream>
#include <functional>
main(){
  std::less<int> lessObject;
  std::cout << lessObject(1,2) << std::endl;
            << lessObject(1,1) << std::endl;
            << lessObject(2,1) << std::endl;
}

補足

「std::cout << オブジェクト」という構文は既存のオブジェクト対しては有効ですが、プログラマが新たに作成したオブジェクトには対応してません。そのため、新たなオブジェクトに対してはプログラマが用意する必要があります。上のプログラムではstd::cout << *i; という構文を使用しています。この構文を与えるには operator<<(std::cout,*i)という関数を定義する必要があります。これを演算子のオーバロードといいます。 std::cout の型は std::ostream 型、 *i は Mvalue 型です。また、以下に説明するように、この関数の戻り値は std::cout 自体になるようにするため、引数は参照を使い、戻り値もその参照を使います。したがって、以下のような定義になります。


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

C++ 言語ではこのように演算子を再定義（オーバーロード)できます。但し、慣習と矛盾をしないようなオーバーロードにしないと混乱のもとですので避けてください。例えば、足し算記号 + で大小比較をさせるようなことはしてはいけません。なお、演算子の再定義は二つの意味があります。

左側のオブジェクトクラスのメンバ関数で、右側が引数
左側は第一引数、右側は第二引数という関数

つまり a+b は次のどちらかの意味になります。上の例は 2 番に当たります。

a.operator+(b)
operator+(a,b)

なお、C++ の構文では慣例として出力を意味する演算子 << に対して、左側に出力ストリームを書き、右側に出力対象を書きます。よって、 1 の構文を使うにはシステムが提供する std::ostream クラスにメンバ関数を追加する必要がありますが、システム提供部分の変更はできません。したがって、std::ostream 型が左側に来る演算子はメンバ関数ではなく、構文 2 の通常の関数として定義しなければならないことがわかります。

また、出力に関しては std::cout << 1 << 2 << std::endl; のように他の出力や改行も連続して行う慣習があります。これを実現するには最初の部分の std::cout << 1 の演算結果が std::cout である必要があります。

ostream 型		Mvalue 型		ostream 型
std::cout	<<	*i	の値が	std::cout

↓

戻り値の型	関数名	第一引数	第二引数
ostream&	operator<<	( ostream& os,	const Mvalue& p)

なお、この場合は Mvalue 型の表示なので、各値を直接アクセスして、そのまま出力できました。しかし、もし、クラスのオブジェクト中にあるメンバ変数の値を出力する場合、通常、メンバ変数はカプセル化しているため、このような定義だけでは、外部関数からアクセスできません。そのため、もしプライベートメンバを使用しなければならない時は、そのクラスの宣言時に friend 指定をし、アクセスを許す必要があります。


#include <iostream>
class Kazu
{
private:
  int x;
public:
  Kazu(int n){x=n;}
  friend std::ostream& operator<<(std::ostream& os, const Kazu& k);
};
std::ostream& operator<<(std::ostream& os, const Kazu& k){
  os << k.x; // k.x はprivate メンバだが、この関数は Kazu クラスに
                   // friend 指定されているのでアクセスできる
  return os;
}
int main(){
  Kazu aKazu(5);
  std::cout << aKazu
	    << std::endl; // return os をしているので再びメッセージを
                          // 送ることができる
  return 0;
}

Java での順序木

java.util.Collections クラスには様々な static メソッドが定義されています。その中で Collections.sort() メソッドは List をソートします。従って、要素を一回だけ整列するだけなら、先週の java.util.LinkedList を用い、 Collections.sort() メソッドを使うだけで要素を整列できます。但し一回につき要素数 N に対して $O (N log N)$ 程度の時間がかかります。

ところが、要素を増やしたり減らしたり変更したりと、ダイナミックに値の列が変化する時、毎回 sort() メソッドを呼び出すことになり効率的な処理になりません。そのため、順序木を用いる必要があります。 Java では java.util.TreeMap というクラスが順序木を内部で実現しています。そのため、データの挿入、削除、検索、昇順の取り出しなどが高速(データ数 N に対して $O (log N)$ 程度) でできます。データを入れるには put メソッドを使います。なお、順序木の順序を任意に与えるには、キーに使うオブジェクトが java.lang.Comparable インターフェイスを実装する必要があります。一方、java.util.Comparator インタフェースを実装しているクラスのオブジェクトをコンストラクタに渡すこともできます。

TreeMap には iterator() メソッドは実装されていません。各要素を全てアクセスするには Set オブジェクトを返す entrySet() メソッドを使います。得られた Set には iterator() メソッドが実装されています。但し、Set の要素は java.util.Map.Entry 型です。個々の値を取り出すにはこの Map.Entry 型のオブジェクトに対して getKey(), getValue() メソッドを使います。一方、keySet() メソッドは Key の Set オブジェクトが得られます。

作成した TreeMap に対して、 Key の大小関係で部分的に取り出す headMap(key), subMap(fromkey,tokey), tailMap(key) メソッドがあります。これは SortedTree オブジェクトを返します。

以下にサンプルコードを示します。

Java 5


import java.util.*;
class TestTree{
    public static void main(String[] arg){
	TreeMap<Integer,String> seisekiMap 
	    = new TreeMap<Integer,String>();
	seisekiMap.put(100, "02kc963");
	seisekiMap.put(62, "02kc903");
	seisekiMap.put(85, "02kc923");
	seisekiMap.put(73, "02kc911");
	seisekiMap.put(85, "02kc987");//重複キーはサポートされず上書き
	System.out.println("size ="+seisekiMap.size());

	for(Map.Entry<Integer,String> e : seisekiMap.entrySet()){
	    System.out.println(e.getValue()+": "+e.getKey());
	}
	System.out.println("---------------------------------");
	SortedMap<Integer,String> subTree 
	    = seisekiMap.subMap(70,90);
	for(Map.Entry<Integer,String> e : subTree.entrySet()){
	    System.out.println(e.getValue()+": "+e.getKey());
	}
    }
}

Java 1.4

put メソッドにはキーと値の組を java.lang.Object 型で与えます。したがって int のような基本データ型をキーとして与えるには注意が必要です。 int は基本データ型であってオブジェクトではないので、キーとして使うにはラッパークラスjava.lang.Integer でオブジェクトに変換する必要があります。なお、java.lang.Integer は java.lang.Comparable を実装していますのでそのままキーとして使えます。


import java.util.*;
class TestTree{
    public static void main(String[] arg){
	TreeMap seisekiMap = new TreeMap();
	seisekiMap.put(new Integer(100), "02kc963");
	seisekiMap.put(new Integer(62), "02kc903");
	seisekiMap.put(new Integer(85), "02kc923");
	seisekiMap.put(new Integer(73), "02kc911");
	seisekiMap.put(new Integer(85), "02kc987");//重複キーはサポートされず上書き
	System.out.println("size ="+seisekiMap.size());
	Set aSet = seisekiMap.entrySet();
	Iterator i=aSet.iterator();
	Map.Entry e;
	while(i.hasNext()){
	    e = (Map.Entry) i.next();
	    System.out.println(e.getValue()+": "+e.getKey());
	}
	System.out.println("---------------------------------");
	i=seisekiMap.subMap(new Integer(70), new Integer(90)).entrySet().iterator();
	while(i.hasNext()){
	    e = (Map.Entry) i.next();
	    System.out.println(e.getValue()+": "+e.getKey());
	}
    }
}

なお、上のようにすると重複キーが使えず、期待したとおりには値を扱うことができません。 C++ では重複キーを許さない map と重複キーを許す multimap が使えましたが、 java.util.TreeMap では許されません。例のように点数順に並べようとしても、同点の人が最大で一人しか存在できないのです。このような場合、重複キーを許すには、「同一であることがわからない」ような比較子を与えれば解決します。そのため、並べる順序をコンストラクタに与えることにします。並べる順序を与えるためにコンストラクタに渡すオブジェクトは java.util.Comparetor インタフェースを実装したクラスから生成します。 java.util.Comparator を実装するには compare() メソッドを与える必要があります。compare(x,y) は x<y なら正の数、 compare(x,y) が等しいなら 0、 x>y なら負の数を整数値で返さねばなりません。ここで、等しくても 1 を返すようにしてしまえば同じキーを使っても別のキーと認識され、同じキーで複数の要素を与えることができます。以下のクラスを付け足し TreeMap のオブジェクト生成でこの比較子を与えると上記のプログラムは期待通りに動きます。

Java 5


class Comp implements java.util.Comparator<Integer> {
    public int compare(Integer o1, Integer o2) {
	int result=o1.compareTo(o2);
	if(result==0){
	    result=1;
	}
	return result;
    }
}
	Comp comp=new Comp();
	TreeMap<Integer,String> seisekiMap 
	    = new TreeMap<Integer,String>(comp);

Java 1.4


class Comp implements java.util.Comparator {
    public int compare(Object o1, Object o2) {
	int result=((Integer)o1).compareTo((Integer)o2);
	if(result==0){
	    result=1;
	}
	return result;
    }
}
	Comp comp=new Comp();
	TreeMap seisekiMap = new TreeMap(comp);

C 言語での順序木

C 言語では順序木を作るのに、構造体とポインタを使います。木の各頂点を表す構造体の中に、キーと、値と、左右の子へのポインタを格納します。木を指す変数は頂点へのポインタになります。木は始め何もない状態とします。そのため、ポインタには NULL を格納しておきます。その後、 add 関数により頂点を付け足して行きます。これはポインタの内容を書き換える事を意味します。したがって、 add 関数には木を指すポインタの番地(つまりポインタのポインタ)を与え、 add 関数内でポインタの内容を書き換えます。

値を付け加える関数 add(TREE **t, キー, 値)は、次のように再帰的に処理します。

もし、(*t) が NULL だったらそこに頂点を付け加える。
付け加えるのに成功したら 1、失敗したら 0 を返す。

注目している木の頂点 **t に格納されているキー (**t).key = (*t)->key との大小により左 (*t)->left か右 (*t)->right かを選択し、どちらかの頂点に対して改めて add((*t)->left, キー, 値) か add((*t)->right, キー, 値) かを再帰的に実行する。

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

一方、木を消去する deltree(TREE *t) は次のような手順になります。

左右の子に対して deltree を行う
自分の頂点を消す処理をする


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tr {
  int key;
  char *id;
  struct tr *left,*right;
} TREE;
int add(TREE **t, int key, char *value){
  TREE *newnode;
  if(*t==NULL){
    if((*t=(TREE *)malloc(sizeof(TREE)))!=NULL){
      (*t)->key=key;
      (*t)->id=strdup(value);
      (*t)->left=NULL;
      (*t)->right=NULL;
    }else{
      return 0;
    }
  }else{
    if((*t)->key>key){
      add(&((*t)->left),key,value);
    }else{
      add(&((*t)->right),key,value);
    }
  }
  return 1;
}
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;
  if(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;
  }else{
    fprintf(stderr,"木の付け加え失敗\n");
    return 1;
  }
}

なお、このままでは木の構造がわかりづらいので、木のどの頂点にあるかを表示する関数 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,"Memory Error\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);
  }
}

演習8-2

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

8-2. クイックソート

順序木は中央の頂点の値は左側のどの頂点の値よりも大きく、右側のどの頂点の値よりも小さいです。従って、順序木が出来上がった時、木の構造を縦に自然に潰すと、値の小さい頂点から大きい頂点まで整列することがわかります。

そこで、与えられた配列に対して、順序木に格納しているように値を振り分けることで、配列の中身を整列できます。つまり、次のような手順になります。

配列が与えられた時、その配列の中で中央の頂点へ入れる値を一つ決め、
左側に配置する値と右側に配置する値を分類します。
そして、左側、右側双方で同様のことを繰り返します。

まず、配列の中で中央の頂点に入れる値を勝手に 0 番目の値と決めてしまいましょう。次に分類ですが、配列の左と右の両方から見て行き、中央の頂点より大きい値を左から探し、中央の頂点より小さい値を右から探すようにします。そして、両方とも見つかったら交換します。このようにすると最終的に左側に小さい値、右側に大きい値が得られます。そして、左と右に再帰的に同じ処理をすれば全ての値が整列できます。このような整列法をクイックソートと言います。この整列法は現在知られている整列法のうち、実際実装して使用する上ではもっとも速い整列法として知られています。


#include <stdio.h>
int a[]={7,10,3,6,1,9,2,4,5,8,-1};
void show(void){
  int i;
  for(i=0;a[i]!=-1;i++){
    printf("%d ",a[i]);
  }
  printf("\n");
}
void partition(int from, int to){
  int s,x,f=from,t=to;
  if(from==to){
    return;
  }else{
    s=a[from];
    while(f!=t){
      while((a[f]<s)&&(f!=to)){f++;};
      while((a[t]>s)&&(t!=from)){t--;};
      x=a[f];
      a[f]=a[t];
      a[t]=x;
    }
    partition(from,f);
    partition(++t,to);
  }
}
void quicksort(void){
  partition(0,9);
}
int main(void){
  show();
  quicksort();
  show();
  return 0;
}

演習8-3

上のプログラムを手で動きを追っていき、どのように配列が整列されるか解析しなさい。例えば partition を呼び出す時のパラメータ、その時の配列の様子などを列挙して動きを理解しなさい。

8-3. バランス木

木に対する処理の実行速度は木の深さに依存します。頂点数 N の木は一番コンパクトに詰め込むと $O (log N)$ の深さになりますが、一直線に頂点が並ぶと $O (N)$ になってしまいます。これは木に対する操作のコストに響きます。クイックソートにおいても、ランダムなデータに対する平均的な計算量は $O (N log N)$ ですが、あらかじめ整列されたデータを与えられた場合などには、 partition 関数を呼び出す深さが $O (N)$ 回になってしまうので、最悪実行時間は $O (N^{2})$ になります。

このように木の形により計算効率は大きく変わります。したがって、効率の良い木を作ることは重要です。

効率のよい木にする一つのアイディアは回転です。演習8-1で見たように同じデータでどのようにも二分木に格納できますので木の構造を都合が良いように変えることです。そのために行うことは根の頂点を変更することです。

このアイディアで木の深さを $O (log N)$ に保つ方式にはスプレー木や二色木、赤黒木、Red-Brack-Tree と呼ばれるものがあります。赤黒木は効率が良く、C++ や Java の内部で実現されています。しかしこれらの手順は複雑なため、ここでは省略します。

この他、二分木という構造を変えて効率を良くした木に2-3木、 B木、B⁺木、B^*木などがあります。詳しくは、インターネットやクリフォード・シェーファーの本などを参照して下さい(但しこの本には赤黒木のことは書いてありません)。

8-4. ヒープ木

順序木はデータの数と木の形が決まると一つの入力に対してデータの格納方法は一通りしかありません(定理)。そのため、入力により木の形が変化します。つまり、入力の並び方が、プログラムの効率に影響を与えます。そこで、順序木とは別のルールを定めます。順序木では三つのデータのうち、中間の値が根となる二分木を考えましたが、ここでは最大の値を根とする木を考えます。このような木をヒープ木と言います。このようにすると、木の形に対して、何通りもデータの格納方法が得られます。さらにヒープに対して新たなデータを付け加える場合も、左側にも右側にも付け足すことができます。

演習8-4

次の木をヒープ木とする時 1,2,3,4 の値の格納の仕方は何通りあるか?

二分木のうち、根から葉、左から右という風に頂点を増やしてできた木を完全二分木と言います。ヒープ木では次のように完全二分木を保ったまま頂点を追加することができます。

まず、得られた値を完全二分木を保つように付け加えます。
そして、付け加えた頂点と親の頂点との関係を調べます。もし、親より大きい値であれば、親とその頂点の値を交換します。
そして、さらに同様にその付け加えた値とその親の関係を調べます。

このようにすると、付け加えた値の付近だけしかヒープ木の条件が壊れてません。そして、付け加えた値と親とを順に交換していくことでいつかはヒープ木の条件を満たすことになります。したがって、付け加える手間は完全二分木の深さに比例することがわかりますので、頂点数 N に対して $O (log N)$ の手間になります。

一方、根の値はヒープ木全体に対して最大値になっています。これを一つずつ取り出せれば、入れたデータを大きい順に整列できます。しかし、取り出す際に完全二分木を保つ必要があります。

そのため、根の値を取り除いた後、完全二分木を保つために取り除くべき頂点の値を根に移動します。
そして、根と二つの子との間で最大値が親になるように値を交換していきます。

交換した値を次々子との間で値を交換していくといずれはすべてがヒープ木の条件を満たすことになります。このようにすると $O (log N)$ の手間で最大の値を得られることになります。残ったヒープ木は、完全二分木であり、根に二番目に大きい値があります。したがって、根から値を取り除き続ければ大きい順に値が得られるので、データを整列できることになります。このような整列法をヒープソートと言います。 N 個のデータのそれぞれに対して、付け加える手間も、取り除く手間もともに $O (log N)$ なので、全体で $O (N log N)$ とクイックソートと同じオーダになります。なお、クイックソートでは与えるデータにより効率が落ちましたが、ヒープソートではそのようなことはありません。但し、ヒープソートではデータを全て木の操作で扱うため、繰り返し内部で、データを扱う部分の計算が遅くなります。そのため、通常のランダムに並んだデータに対してはクイックソートの方が数倍効率が良くなります。

ヒープ木は完全二分木で作れるので、配列で実現できます。根から順に 0, 1, 2 と番号を付けていくと、 n 番目の頂点に対する親と子はそれぞれ $(n - 1) / 2$ 番目と、 $2 n + 1$ と $2 n + 2$ 番目になります。

配列により実現したヒープソートのプログラムを示します。


#include <stdio.h>
int a[]={7,10,3,6,1,9,2,4,5,8,-1};
int b[10];
int size=0;
void add(int n){
  int i=size++,next,c;
  b[i]=n;
  while(i>0){
    next=(i-1)/2;
    if(b[i]>b[next]){
      c=b[i];
      b[i]=b[next];
      b[next]=c;
      i=next;
    }else{
      break;
    }
  }
}
int pop(void){
  int value=b[0];
  int i=0,c,next1,next;
  b[0]=b[--size];
  while(i<size){
    next=2*i+1;
    if(next<size){
      if(next+1<size){
	if(b[next]<b[next+1]){
	  next++;
	}
      }
      if(b[i]<b[next]){
	c=b[i];
	b[i]=b[next];
	b[next]=c;
	i=next;
      }else{
	break;
      }
    }else{
      break;
    }
  }
  return value;
}
int main(void){
  int i;
  for(i=0;a[i]!=-1;i++){
    printf("%d ",a[i]);
    add(a[i]);
  }
  printf("\n");
  while(size!=0){
    printf("%d ",pop());
  }
  printf("\n");
  return 0;
}

参考

ヒープソート

ヒープソートでは、実際は値を取り出す際に、ヒープを実現している配列の後ろから取り出した値を格納します。これは、値を取り出すたびにうしろから使わなくなった領域ができてきますので、そこに大きい順に値を入れていくと最終的に小さい順に値を整列できます。

定理

データの数と木の形が決まると、順序木にデータを格納する方法は一通りしかない。

証明

根の頂点の値は、左側にある頂点よりも大きく、右側にある頂点よりも小さいので、左側の頂点の数と右側の頂点の数から、頂点に格納すべき値と、左側、右側に分けられるべきデータが決まる。これを帰納的に適応すると、根から順に頂点に割り当てるデータが一通りに決まる。(証明終り)

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 8 回 木

本日の内容

8-1. 順序木

順序木の定義

演習8-1

ヒント

C++ での順序木

補足

Java での順序木

Java 5

Java 1.4

Java 5

Java 1.4

C 言語での順序木

演習8-2

8-2. クイックソート

演習8-3

8-3. バランス木

8-4. ヒープ木

演習8-4

参考

ヒープソート

定理

証明

第 8 回木