第9章の演習

ソースのダウンロード

今後の演習では，ホームフォルダの下にmis2というフォルダを作って，そこで作業することを前提とする．作成していない時は，ターミナルから

mkdir ~/mis2

を実行する． http://opendatastructures.orgのc++ edition, c++ sources ( C++ sources(講義独自版) ) からダウンロードしたファイルをホームフォルダの下のmis2に置く．ods.cpp.tgzというファイルができた時は，

cd ~/mis2
tar zxvf ods-cpp.tgz

ods-cpp.tarというファイルができた時は，

cd ~/mis2
tar xvf ods-cpp.tar

を実行するとcppというフォルダができる．Finderからダブルクリックしてもアーカイブユーティリティが立ち上がり展開されるので，そちらでも良い．

[投票]赤黒木を知っていた?

名前をこの講義で初めて知った
名前は聞いたことがあるが，どのようなものかは知らない
どのようなものかは知っているが使ったことはない
他の人が作ったライブラリを使ったことがある．
自分で実装したことがある

[投票]次の中で赤黒木を使って実装されているものは?(正解は複数)

C++のmap
C++のunordered_map
Rubyの配列
Pythonのdictionary(辞書)
Javascriptのオブジェクト

[投票]図はLeft-Leaning Red-Black Tree?

はい
Red-Black TreeだがLeft-Leaningではない
Red-Black Treeではない

[投票]図はLeft-Leaning Red-Black Tree?

はい
Red-Black TreeだがLeft-Leaningではない
Red-Black Treeではない

[投票]図はLeft-Leaning Red-Black Tree?

はい
Red-Black TreeだがLeft-Leaningではない
Red-Black Treeではない

[投票]図はLeft-Leaning Red-Black Tree?

はい
Red-Black TreeだがLeft-Leaningではない
Red-Black Treeではない

演習(RedBlackTree)

~/mis2/cpp 以下にredBlackTreeTest.cpp というファイルを作成する．

#include "RedBlackTree.h"
#include <iostream>
#include <vector>
#include <algorithm>

int main(){
  int null = -1;
  ods::RedBlackTree1<int> primes;
  for(int i = 2; i < 1000; i++)  primes.add(i);
  std::cout << "Tree height=" << primes.height() << std::endl;
  for(int i = 2; i < 1000; i++){
    if(primes.find(i) == i){
      std::cout << i << std::endl;
      for(int j = i + i; j < 1000; j += i){
        primes.remove(j);
      }
    }
  }
  std::cout << "Tree height=" << primes.height() << std::endl;
  std::cout << "Tree size=" << primes.size() << std::endl;
}

これを，

cd ~/mis2/cpp
g++-5 -Wall  -o redBlackTreeTest redBlackTreeTest.cpp

でコンパイルし，

./redBlackTreeTest

で実行する．