第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からダブルクリックしてもアーカイブユーティリティが立ち上がり展開されるので，そちらでも良い．

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

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

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

  1. C++のmap
  2. C++のunordered_map
  3. Rubyの配列
  4. Pythonのdictionary(辞書)
  5. Javascriptのオブジェクト

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


図1

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


図2

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


図3

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


図4

演習(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++ -Wall  -o redBlackTreeTest redBlackTreeTest.cpp
でコンパイルし， 
./redBlackTreeTest
で実行する．