課題5(6/17出題)

課題

• 教科書の6.3 Discussion and Exercisesの Exercise 6.4, 6.5 を解きなさい．
• 教科書の9.4 Discussion and Exercisesの Exercise 9.1, 9.2 を解きなさい．
  • Figure 9.11 のRed-Black Treeにはノードに数字が書かれているので，これに対応する2-4木のノードには「{6,10}」とか「{1,2,3}」，「{5}」のようにRed-Black Treeとの対応が分かるようにすると良い(教科書の2-4木はノードに何も書かれていないものばかりだが)．

ヒント

• checkEx6_4.cpp

  #include "BinaryTree.h"
  
  class MyBinaryTree : public ods::BinaryTree{
    typedef ods::BTNode1 Node;
  public:
    MyBinaryTree(ods::BTNode1* nil_, ods::BTNode1* r_) :ods::BinaryTree(nil_){
      r = r_;
    }
  };
  
  int main(){
    ods::BTNode1 *r = new ods::BTNode1();
    ods::BTNode1 *n1 = new ods::BTNode1();
    ods::BTNode1 *n2 = new ods::BTNode1();
    ods::BTNode1 *n3 = new ods::BTNode1();
    std::cout << "r = " << r << ",n1=" << n1 << ",n2=" << n2 << ",n3=" << n3 << std::endl;
    r->left = n1; n1->parent = r;
    r->right = n2; n2->parent = r;
    n2->left = n3; n3->parent = n2;
    /*
                  r
                 / \ 
                n1  n2
                   /
                  n3
    */
    MyBinaryTree t(0, r);
    // t.size2(r) -> 4
    std::cout << "t.size2(r)=" << t.size2(r) << std::endl;
    // t.size(n2) -> 2
    std::cout << "t.size2(n2)=" << t.size2(n2) << std::endl;
    // t.size(n3) -> 1
    std::cout << "t.size2(n3)=" << t.size2(n3) << std::endl;
  }
  

  コンパイル, 実行例

  bash-3.2$ g++-mp-4.8 -o checkEx6_4 checkEx6_4.cpp
  bash-3.2$ ./checkEx6_4
  r = 0x7fbcfac03990,n1=0x7fbcfac039b0,n2=0x7fbcfac039d0,n3=0x7fbcfac039f0
  t.size2(r)=4
  t.size2(n2)=2
  t.size(n3)=1
  

• checkEx6_5.cpp

  #include "BinaryTree.h"
  
  class MyBinaryTree : public ods::BinaryTree{
    typedef ods::BTNode1 Node;
  public:
    MyBinaryTree(ods::BTNode1* nil_, ods::BTNode1* r_) :ods::BinaryTree(nil_){
      r = r_;
    }
  };
  
  int main(){
    ods::BTNode1 *r = new ods::BTNode1();
    ods::BTNode1 *n1 = new ods::BTNode1();
    ods::BTNode1 *n2 = new ods::BTNode1();
    ods::BTNode1 *n3 = new ods::BTNode1();
    std::cout << "r = " << r << ",n1=" << n1 << ",n2=" << n2 << ",n3=" << n3 << std::endl;
    r->left = n1; n1->parent = r;
    r->right = n2; n2->parent = r;
    n2->left = n3; n3->parent = n2;
    /*
                  r
                 / \ 
                n1  n2
                   /
                  n3
    */
    MyBinaryTree t(0, r);
    // t.height2(r) -> 2
    std::cout << "t.height2(r)=" << t.height2(r) << std::endl;
    // t.height2(n2) -> 1
    std::cout << "t.height2(n2)=" << t.height2(n2) << std::endl;
    // t.height2(n3) -> 0
    std::cout << "t.height2(n3)=" << t.height2(n3) << std::endl;
  }
  

  コンパイル, 実行例

  bash-3.2$ g++-mp-4.8 -o checkEx6_5 checkEx6_5.cpp
  bash-3.2$ ./checkEx6_5
  r = 0x7fbcfac03990,n1=0x7fbcfac039b0,n2=0x7fbcfac039d0,n3=0x7fbcfac039f0
  r = 0x7fb610d00000,n1=0x7fb610d00020,n2=0x7fb610d00040,n3=0x7fb610d00060
  t.height2(r)=2
  t.height2(n2)=1
  t.height2(n3)=0
  

提出方法

締切は，7/4(金) 23:59．締切を過ぎても2014年7月末までは6割を上限に採点する．

全部の問題が解けなくても，解けたものをなるべく締切前に提出するように．

オプション課題

• 第6, 9章の他の練習問題に取り組む