[자료구조 - C++] Assignment 4 Search Tree 구현하기

마지막 과제는 바로 Search Tree를 구현하는 것이었다. 일반적인 BST와 AVL Tree들을 구현해서 실행시간을 비교하고 레포트까지 작성하는 것이 과제였다. 사실 이번 과제는 교재(Data Structures&Algorithms in C++ 2nd Edition by Michael T.Goodrich, Roberto Tamissa, David M.Mount)에서 많은 도움을 얻었다. 교수님께서도 그래도 된다고 하시기도 하셨고, 스켈레톤 코드도 상당 부분 유사했다. 그러나 완전히 동일하지는 않았고 어느 정도 응용을 했어야 했다. 

 

주어진 파일은 6개로, AVL Tree 구현에 사용되는 파일 두 개, BST 구현에 사용되는 파일 두 개, 메인 파일 한 개, AVL과 BST의 기초가 되는 Linked Binary Tree 헤더 파일 한 개로 구성되어 있었다.

 

1-1) 구현해야 하는 함수들 - SearchTree.txx

Iterator& operator++()
TPos eraser(TPos& v)
TPos finder(const K& k, const TPos& v)
TPos inserter(const K& k, const V& x) // replace if k exists

 

1-2) 구현해야 하는 함수들 - AVLTree.txx

void erase(const K& k)
Iterator insert(const K& k, const V& x) // replace if k exists
void rebalance(const TPos& v)
TPos restructure(const TPos& v)

 

참고사항 : 

1. insert operation in SearchTree and AVLTree must replace the existing key rather than duplicating same keys. : SearchTree와 AVLTree에서 이미 존재하는 키 값을 insert operation을 통해 입력받으면 같은 키를 복제하는 것이 아니라 대체해야 함.

2. You will be able to find most of the implementation of the above functions from our textbook, so you may use them. However, simple cut-and-paste would not work because the code in the textbook may have some errors/bugs. Make sure your code works correctly. : 위 함수들의 구현의 많은 부분을 책에서 찾을 수 있으므로 그것을 사용해도 된다. 그러나 단순 복사 및 붙여넣기는 작동하지 않을 것이다. 확실히 작동하도록 작성할 것.

3. You can freely modify main.cpp for your experiment (see below) : 자유롭게 main.cpp 파일을 조작해도 된다.

 

main.cpp 파일 조작 관련 안내 :

(a) insert operations only - 두 트리의 삽입 연산 시간 비교

- skewed order, random order 두 가지로 삽입

- 삽입되는 key와 value pair의 size가 각각 1000, 10000, 100000, 1000000일 때 비교

 

(b) find operations only - 두 트리의 검색 연산 시간 비교

- skewed order, random order 두 가지로 삽입

- 삽입되는 key와 value pair의 size가 각각 1000, 10000, 100000, 1000000일 때 비교

 

2) LinkedBinaryTree.h

#ifndef BINARYTREE_H
#define BINARYTREE_H

#include <list>

using namespace std;

//
// Binary Tree Class
//
//typedef int Elem;					// base element type



template <typename K, typename V>
  class Entry {						// a (key, value) pair
  public:						// public functions
    typedef K Key;				// a key
    typedef V Value;
  
    Entry(const K& k = K(), const V& v = V())		// constructor
      : _key(k), _value(v) { }	
    const K& key() const { return _key; }		// get key
    const V& value() const { return _value; }		// get value
    void setKey(const K& k) { _key = k; }		// set key
    void setValue(const V& v) { _value = v; }		// set value
  private:						// private data
    K _key;						// key
    V _value;						// value
  };
  
  
typedef Entry<int,float> Elem;  

template <typename E>
class LinkedBinaryTree {
  protected:
	struct Node {					// a node of the tree
      E    elt;					// element value
      Node*   par;					// parent
      Node*   left;					// left child
      Node*   right;					// right child
      Node() : elt(), par(NULL), left(NULL), right(NULL) { } // constructor
    };
    
  public:
    class Position {					// position in the tree
    //private:
    public:
      Node* v;						// pointer to the node
    public:
      Position(Node* _v = NULL) : v(_v) { }		// constructor
      E& operator*() const					// get element
        { return v->elt; }
      Position left() const				// get left child
        { return Position(v->left); }
      Position right() const				// get right child
        { return Position(v->right); }
      Position parent() const				// get parent
        { return Position(v->par); }
      bool isRoot() const				// root of the tree?
        { return v->par == NULL; }
      bool isExternal() const				// an external node?
        { return v->left == NULL && v->right == NULL; }
    
    	// additional
      bool isInternal() const
      	{ return !isExternal(); }  
      bool operator==(const Position& p) const		// are iterators equal?
        { return v == p.v; }
      bool operator!=(const Position& p) const		// are iterators equal?
        { return v != p.v; }
    
    
    
      friend class LinkedBinaryTree;			// give tree access
    };
	typedef std::list<Position> PositionList;		// list of positions

  public:
    LinkedBinaryTree();					// constructor
	~LinkedBinaryTree();				// destructor
    int size() const;					// number of nodes
    bool empty() const;					// is tree empty?
    Position root() const;				// get the root
    PositionList positions() const;  			// list of nodes
    void addRoot();					// add root to empty tree
    void expandExternal(const Position& p);		// expand external node
    Position removeAboveExternal(const Position& p);	// remove p and parent
    // housekeeping functions omitted...
  protected: 						// local utilities
    void preorder(Node* v, PositionList& pl) const;	// preorder utility
  private:
    Node* _root;					// pointer to the root
    int n;						// number of nodes
  };
  
  
  //
  // Implementation
  //
  
  template <typename E>
  void LinkedBinaryTree<E>::expandExternal(const Position& p) {
    Node* v = p.v;					// p's node
    v->left = new Node;					// add a new left child
    v->left->par = v;					// v is its parent
    v->right = new Node;				// and a new right child
    v->right->par = v;					// v is its parent
    n += 2;						// two more nodes
  }
  
  template <typename E>
  typename LinkedBinaryTree<E>::PositionList LinkedBinaryTree<E>::positions() const {
  PositionList pl;
  preorder(_root, pl);					// preorder traversal
  return PositionList(pl);				// return resulting list
}

// preorder traversal
template <typename E>
void LinkedBinaryTree<E>::preorder(Node* v, PositionList& pl) const {
  pl.push_back(Position(v));				// add this node
  if (v->left != NULL)					// traverse left subtree
    preorder(v->left, pl);
  if (v->right != NULL)					// traverse right subtree
    preorder(v->right, pl);
}

template <typename E>
typename LinkedBinaryTree<E>::Position				// remove p and parent
  LinkedBinaryTree<E>::removeAboveExternal(const Position& p) {
    Node* w = p.v;  Node* v = w->par;			// get p's node and parent
    Node* sib = (w == v->left ?  v->right : v->left);
    if (v == _root) {					// child of root?
      _root = sib;					// ...make sibling root
      sib->par = NULL;
    }
    else {
      Node* gpar = v->par;				// w's grandparent
      if (v == gpar->left) gpar->left = sib; 		// replace parent by sib
      else gpar->right = sib;
      sib->par = gpar;
    }
    delete w; delete v;					// delete removed nodes
    n -= 2;						// two fewer nodes
    return Position(sib);
  }
  
  template <typename E>
  LinkedBinaryTree<E>::LinkedBinaryTree()			// constructor
    : _root(NULL), n(0) { }
	
  template <typename E>
  LinkedBinaryTree<E>::~LinkedBinaryTree()			// destructor
    {
		PositionList pl = positions();
		for(typename PositionList::iterator it = pl.begin();it != pl.end();it++)
		{
			Node* w = (*it).v;
			delete w;
		}
	}
    
  template <typename E>  
  int LinkedBinaryTree<E>::size() const			// number of nodes
    { return n; }
    
  template <typename E>  
  bool LinkedBinaryTree<E>::empty() const			// is tree empty?
    { return size() == 0; }
    
  template <typename E>  
  typename LinkedBinaryTree<E>::Position LinkedBinaryTree<E>::root() const // get the root
    { return Position(_root); }
    
  template <typename E>  
  void LinkedBinaryTree<E>::addRoot()			// add root to empty tree
    { _root = new Node; n = 1; }
  
  #endif

 

3) SearchTree.h

#ifndef SEARCHTREE_H
#define SEARCHTREE_H

#include <iostream>
#include "LinkedBinaryTree.h"

//
// SearchTree Class
//  
template <typename E>
class SearchTree {					// a binary search tree
  public: 						// public types
    typedef typename E::Key K;				// a key
    typedef typename E::Value V;			// a value
    class Iterator;					// an iterator/position
  public:						// public functions
    SearchTree();					// constructor
    int size() const; 					// number of entries
    bool empty() const;					// is the tree empty?
    Iterator find(const K& k);				// find entry with key k
    Iterator insert(const K& k, const V& x);		// insert (k,x)
    void erase(const K& k);				// remove key k entry
    void erase(const Iterator& p);			// remove entry at p
    Iterator begin();					// iterator to first entry
    Iterator end();					// iterator to end entry
  protected:						// local utilities
    typedef LinkedBinaryTree<E> BinaryTree;		// linked binary tree
    typedef typename BinaryTree::Position TPos;		// position in the tree
    TPos root() const;					// get virtual root
    TPos finder(const K& k, const TPos& v);		// find utility
    TPos inserter(const K& k, const V& x);		// insert utility
    TPos eraser(TPos& v);				// erase utility
    TPos restructure(const TPos& v); 			// restructure
      	
  private: 						// member data
    BinaryTree T;					// the binary tree
    int n;						// number of entries
  public:
    class Iterator {	                      		// an iterator/position
    private:
      TPos v;						// which entry
    public:
      Iterator(const TPos& vv) : v(vv) { }		// constructor
      const E& operator*() const { return *v; }		// get entry (read only)
      E& operator*() { return *v; }			// get entry (read/write)
      bool operator==(const Iterator& p) const		// are iterators equal?
        { return v == p.v; }   
      bool operator!=(const Iterator& p) const		// are iterators not equal?
        { return v != p.v; }
      Iterator& operator++();				// inorder successor
      friend class SearchTree;				// give search tree access
    };
  };
  
      
#ifndef SEARCHTREE_TXX
#define SEARCHTREE_TXX
#include "SearchTree.txx"
#endif
#endif

 4) SearchTree.txx

  template <typename E>					// constructor
  SearchTree<E>::SearchTree() : T(), n(0)
    { T.addRoot(); T.expandExternal(T.root()); }	// create the super root
  
  template <typename E>					// get virtual root
  typename SearchTree<E>::TPos SearchTree<E>::root() const
    { return T.root().left(); }				// left child of super root
  
   template <typename E>					// iterator to first entry
  typename SearchTree<E>::Iterator SearchTree<E>::begin() {
    TPos v = root();					// start at virtual root
    while (v.isInternal()) v = v.left();		// find leftmost node
    return Iterator(v.parent());
  }
  
  template <typename E>					// iterator to end entry
  typename SearchTree<E>::Iterator SearchTree<E>::end()
    { return Iterator(T.root()); }			// return the super root
    
  template <typename E>					// remove key k entry
  void SearchTree<E>::erase(const K& k) { //throw(NonexistentElement) {
    TPos v = finder(k, root());				// search from virtual root
    if (v.isExternal())					// not found?
      throw "Erase of nonexistent";//NonexistentElement("Erase of nonexistent");
    eraser(v);						// remove it
  }
  
  template <typename E>					// erase entry at p
  void SearchTree<E>::erase(const Iterator& p)
    { eraser(p.v); }
    
  template <typename E>					// find entry with key k
  typename SearchTree<E>::Iterator SearchTree<E>::find(const K& k) {
    TPos v = finder(k, root());				// search from virtual root
    if (v.isInternal()) return Iterator(v);		// found it
    else return end();					// didn't find it
  }  
  
  template <typename E>					// insert (k,x)
  typename SearchTree<E>::Iterator SearchTree<E>::insert(const K& k, const V& x)
    { TPos v = inserter(k, x); return Iterator(v); }  
 
  template <typename E>
  int SearchTree<E>::size() const { return n; }  
    
    
//
// ToDo
//    
 
  template <typename E>					// inorder successor
  typename SearchTree<E>::Iterator& SearchTree<E>::Iterator::operator++() {
TPos w = v.right();
if (w.isInternal()){
    do{v = w; w = w.left();}
        while (w.isInternal());
}
else{
    w = v.parent();
    while (v == w.right())
    {v = w; w = w.parent();}
    v = w;
}
return *this;
}
     
    
    
  template <typename E>					// remove utility
  typename SearchTree<E>::TPos SearchTree<E>::eraser(TPos& v) {
TPos w;
if (v.left().isExternal()) w = v.left();
else if (v.right().isExternal()) w = v.right();
else { w = v.right(); do{w = w.left();} while (w.isInternal());
TPos u = w.parent();
(*v).setKey((*u).key()); (*v).setValue((*u).value());}
n--;
return T.removeAboveExternal(w);
  }
      
  template <typename E>					// find utility
  typename SearchTree<E>::TPos SearchTree<E>::finder(const K& k, const TPos& v) {
if (v.isExternal()) return v;   //key not found
if (k < (*v).key()) return finder(k, v.v->left); //search left subtree
else if ((*v).key() < k) return finder(k, v.v->right);   //search right subtree
else return v;
  }
  
  template <typename E>					// insert utility
  typename SearchTree<E>::TPos SearchTree<E>::inserter(const K& k, const V& x) {
    TPos v = finder(k, root());
    if((*v).key() == k){}
    else{
        while (v.isInternal()) v = finder(k, v.right());
        T.expandExternal(v);
        (*v).setKey(k);
        n++;}
    (*v).setValue(x);
    return v;
  }

5) AVLTree.h

#ifndef AVLTREE_H
#define AVLTREE_H

#include <iostream>
#include "SearchTree.h"

template <typename E>  class AVLTree;


template <typename E>
  class AVLEntry : public E {				// an AVL entry
  private:
    int ht;						// node height
  protected:						// local types
    typedef typename E::Key K;				// key type
    typedef typename E::Value V;			// value type
    int height() const { return ht; }			// get height
    void setHeight(int h) { ht = h; }			// set height
  public:						// public functions
    AVLEntry(const K& k = K(), const V& v = V())	// constructor
        : E(k,v), ht(0) { }	
    friend class AVLTree<E>;				// allow AVLTree access
  };

//
// AVL Tree class
//  
template <typename E>					// an AVL tree
  class AVLTree : public SearchTree< AVLEntry<E> > {
  public:						// public types
    typedef AVLEntry<E> Entry;			// an entry
    typedef typename SearchTree<Entry>::Iterator Iterator; // an iterator
  protected:						// local types
    typedef typename Entry::Key K;			// a key
    typedef typename Entry::Value V;			// a value
    typedef SearchTree<Entry> ST;			// a search tree
    typedef typename ST::TPos TPos;			// a tree position
  public:						// public functions
    AVLTree();						// constructor
    Iterator insert(const K& k, const V& x);		// insert (k,x)
    void erase(const K& k);	// remove key k entry
    void erase(const Iterator& p);			// remove entry at p
  protected:						// utility functions 
    int height(const TPos& v) const;			// node height utility
    void setHeight(TPos v);				// set height utility
    bool isBalanced(const TPos& v) const;		// is v balanced?
    TPos tallGrandchild(const TPos& v) const;		// get tallest grandchild
    void rebalance(const TPos& v);			// rebalance utility
    TPos restructure(const TPos& v); 			// restructure
  };

      
#ifndef AVLTREE_TXX
#define AVLTREE_TXX
#include "AVLTree.txx"

#endif
#endif

6) AVLTree.txx

//
// Implementation
//
template <typename E>					// constructor
  AVLTree<E>::AVLTree() : ST() { }

template <typename E>					// node height utility
  int AVLTree<E>::height(const TPos& v) const
    { return (v.isExternal() ? 0 : (*v).height()); }

template <typename E>					// set height utility
  void AVLTree<E>::setHeight(TPos v) {
    int hl = height(v.left());
    int hr = height(v.right());
    (*v).setHeight(1 + std::max(hl, hr));			// max of left & right
  }

template <typename E>					// is v balanced?
  bool AVLTree<E>::isBalanced(const TPos& v) const {	
    int bal = height(v.left()) - height(v.right());
    return ((-1 <= bal) && (bal <= 1));
  }

template <typename E>					// get tallest grandchild
  typename AVLTree<E>::TPos AVLTree<E>::tallGrandchild(const TPos& z) const {
    TPos zl = z.left();
    TPos zr = z.right();
    if (height(zl) >= height(zr))			// left child taller
      if (height(zl.left()) >= height(zl.right()))
        return zl.left();
      else
        return zl.right();
    else 						// right child taller
      if (height(zr.right()) >= height(zr.left()))
        return zr.right();
      else
        return zr.left();
  }


//
// ToDo
//

template <typename E>					// remove key k entry
  void AVLTree<E>::erase(const K& k) {
    TPos v = finder(k, ST::root());
    TPos w = eraser(v);
    rebalance(w);
  }

template <typename E>					// insert (k,x)
  typename AVLTree<E>::Iterator AVLTree<E>::insert(const K& k, const V& x) {
    TPos v = ST::inserter(k, x);
    setHeight(v);
    rebalance(v);
    return Iterator(v);
  }
  
template <typename E>					// rebalancing utility
  void AVLTree<E>::rebalance(const TPos& v) {
    TPos z = v;
    while (!(z == ST::root()))
    {
        z = z.parent();
        setHeight(z);
        if (!isBalanced(z))
        {
            TPos x = tallGrandchild(z);
            z = restructure(x);
            setHeight(z.left());
            setHeight(z.right());
            setHeight(z);
        }
    }
  }

template <typename E>				// Binary Search Tree Rotation
  typename AVLTree<E>::TPos AVLTree<E>::restructure(const TPos& v) {

    TPos x = v;
    TPos y = v.parent();    //parent node of x
    TPos z = y.parent();    //parent node of y(== grandparent node of x)
    TPos GP = z;    //grandparent node is z, it needs to compare with great grand parent
    TPos GGP = z.parent();  //great grand parent node is parent node of z

    K key_z = (*z).key();
    K key_y = (*y).key();
    K key_x = (*x).key();

    if(key_z < key_y) // Left rotation
    {
        if(key_y < key_x)   //RR rotation
        {
            TPos ylc = y.left();
            y.v->par = z.v->par;
            z.v->right = ylc.v;
            y.v->left = z.v;
            z.v->par = x.v->par = y.v;
            ylc.v->par = z.v;
            if(GGP.left() == GP)
                GGP.v->left = y.v;
            else if(GGP.right() == GP)
                GGP.v->right = y.v;
            return y;
        }
        else if(key_y > key_x)  //RL rotation
        {
            TPos xlc = x.left();
            TPos xrc = x.right();
            x.v->par = y.v->par;    //LL rotation begins
            y.v->left = xrc.v;
            x.v->right = y.v;
            xlc.v->par = y.v->par = x.v;
            xrc.v->par = y.v;   //LL rotation ends
            x.v->par = z.v->par;    //RR rotation begins
            z.v->right = xlc.v;
            x.v->left = z.v;
            z.v->par = y.v->par = x.v;
            xlc.v->par = z.v; //RR rotation ends
            if(GGP.left() == GP)
                GGP.v->left = x.v;
            else if(GGP.right() == GP)
                GGP.v->right = x.v;
            return x;
        }
    }
    else  //Right rotation
    {
        if(key_y > key_x)   //LL rotation
        {
            TPos yrc = y.right();
            y.v->par = z.v->par;
            z.v->left = yrc.v;
            y.v->right = z.v;
            z.v->par = x.v->par = y.v;
            yrc.v->par = z.v;
            if(GGP.left() == GP)
                GGP.v->left = y.v;
            else if(GGP.right() == GP)
                GGP.v->right = y.v;
            return y;
        }
        else if(key_y < key_x)  //LR rotation
        {
            TPos xlc = x.left();
            TPos xrc = x.right();
            x.v->par = y.v->par;    //RR rotation begins
            y.v->right = xlc.v;
            x.v->left = y.v;
            y.v->par = xrc.v->par = x.v;
            xlc.v->par = y.v;   //RR rotation ends
            x.v->par = z.v->par;    //LL rotation begins
            z.v->left = xrc.v;
            x.v->right = z.v;
            z.v->par = y.v->par = x.v;
            xrc.v->par = z.v; //LL rotatiion ends
            if(GGP.left() == GP)
                GGP.v->left = x.v;
            else if(GGP.right() == GP)
                GGP.v->right = x.v;
            return x;
        }
    }
return NULL;    //if an error occurs
  }

7) main.cpp

#include "LinkedBinaryTree.h"
#include "SearchTree.h"
#include "AVLTree.h"

#include <cstdlib>
#include <iostream>
#include <ctime>
#include <time.h>       /* clock_t, clock, CLOCKS_PER_SEC */

#include <iostream>

using namespace std;

int main()
{
    typedef Entry<int, float> EntryType;

    LinkedBinaryTree<EntryType> t;

    std::cout << "Size : " << t.size() << std::endl;

    t.addRoot();

    std::cout << "Size : " << t.size() << std::endl;


    //
    //
    //
    SearchTree<EntryType>    st;

    std::cout << "Size : " << st.size() << std::endl;
    st.insert(1, 2.5);
    st.insert(3, 4.5);
    st.insert(7, 5.5);
    st.insert(2, 1.5);
    st.insert(3, 8.5);
    std::cout << "Size : " << st.size() << std::endl;

    for(SearchTree<EntryType>::Iterator it = st.begin(); it != st.end(); ++it)
    {
        std::cout << (*it).key() << " , " << (*it).value() << std::endl;
    }

    st.erase(3);
    std::cout << "Size : " << st.size() << std::endl;
    for(SearchTree<EntryType>::Iterator it = st.begin(); it != st.end(); ++it)
    {
        std::cout << (*it).key() << " , " << (*it).value() << std::endl;
    }

    std::cout << "------------" << std::endl;


    //
    //
    AVLTree<EntryType>    avl;
    //
    // random test
    int nElem = 100000; //100000000;

    int *key = new int[nElem*2];
    float *val = new float[nElem*2];

    std::srand((unsigned int)time(NULL)); // use current time as seed for random generator


    // initialize
    for(int i=0; i<nElem*2; i++)
    {
        key[i] = i+1;
        val[i] = (float) std::rand()/RAND_MAX * 20000;
    }


    //
    // AVL tree Insert test
    //
    clock_t tm;
    tm = clock();
    for(int i=0; i<nElem; i++)
    {
        avl.insert(key[i], val[i]);
    }
    tm = clock() - tm;
    printf ("It took me %f seconds.\n",((float)tm)/(float)CLOCKS_PER_SEC);


    //
    // AVL tree Find test
    //
    tm = clock();
    for(int i=nElem; i<nElem*2; i++)
    {
        avl.find(key[i]);
    }
    tm = clock() - tm;
    printf ("It took me %f seconds.\n",((float)tm)/(float)CLOCKS_PER_SEC);
    delete[] key;
    delete[] val;
    std::cout << "------------" << std::endl;

    //
    //Test Cases Implementation
    //
    std::cout << "Test Cases Implementation" << std::endl;
    //1) size = 1000
    std::cout << " 1. size = 1000" << std::endl;
    //In skewed order(increasing order)
    std::cout << " " << std::endl;
    std::cout << "  1-(1). Skewed Order(Increasing Order)" << std::endl;
    std::cout << " " << std::endl;
    std::cout << "    (a). Insert Operation" << std::endl;

    int n1Elem = 1000;
    int *n11key = new int[n1Elem];
    float *n11val = new float[n1Elem];

    for(int i=0; i<n1Elem; i++)    //initialize
    {
        n11key[i] = i+1;   //keys are initialized in increasing order.
        n11val[i] = (float) std::rand()/RAND_MAX * 20000;  //value doesn't matter, so I will use it repeatedly
    }

    //Search Tree Insertion
    SearchTree<EntryType>    st_test1_1;

    tm = clock();
    for(int i=0; i<n1Elem; i++)
        st_test1_1.insert(n11key[i], n11val[i]);
    tm = clock() - tm;
    float st_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (i)  Search Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //AVL Tree Insertion
    AVLTree<EntryType>    avl_test1_1;
    tm = clock();
    for(int i=0; i<n1Elem; i++)
        avl_test1_1.insert(n11key[i], n11val[i]);
    tm = clock() - tm;
    float avl_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;

    //Comparison
    std::cout << "       (ii) AVL Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;
    if(st_Clock < avl_Clock)
        std::cout << "          -> Search Tree Insertion was faster than AVL Tree's." << std::endl;
    else
        std::cout << "          -> AVL Tree Insertion was faster than Search Tree's." << std::endl;
    std::cout << " " << std::endl;

    std::cout << "    (b). Find Operation" << std::endl;

    //Search Tree Find
    tm = clock();
    for(int i=0; i<n1Elem; i++)
        st_test1_1.find(n11key[i]);
    tm = clock() - tm;
    st_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (i)  Search Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //AVL Tree Find
    tm = clock();
    for(int i=0; i<n1Elem; i++)
        avl_test1_1.find(n11key[i]);
    tm = clock() - tm;
    avl_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (ii) AVL Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;
    if(st_Clock < avl_Clock)
        std::cout << "          -> Search Tree Find was faster than AVL Tree's." << std::endl;
    else
        std::cout << "          -> AVL Tree Find was faster than Search Tree's." << std::endl;

    delete[] n11key;
    delete[] n11val;

    std::cout << " " << std::endl;

    std::cout << "  1-(2). Random Order" << std::endl;
    std::cout << " " << std::endl;
    std::cout << "    (a). Insert Operation" << std::endl;

    int* n12key = new int[n1Elem];
    float* n12val = new float[n1Elem];

    for(int i=0; i<n1Elem; i++)    //randomly initialize
    {
        n12key[i] = std::rand();
        n12val[i] = (float) std::rand()/RAND_MAX * 20000;
    }

    //Search Tree Insertion
    SearchTree<EntryType>    st_test1_2;
    tm = clock();
    for(int i=0; i<n1Elem; i++)
        st_test1_2.insert(n12key[i], n12val[i]);
    tm = clock() - tm;
    st_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (i)  Search Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //AVL Tree Insertion
    AVLTree<EntryType>    avl_test1_2;
    tm = clock();
    for(int i=0; i<n1Elem; i++)
        avl_test1_2.insert(n12key[i], n12val[i]);
    tm = clock() - tm;
    avl_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (ii) AVL Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //comparison
    if(st_Clock < avl_Clock)
        std::cout << "          -> Search Tree Insertion was faster than AVL Tree's." << std::endl;
    else
        std::cout << "          -> AVL Tree Insertion was faster than Search Tree's." << std::endl;
    std::cout << " " << std::endl;
    std::cout << "    (b). Find Operation" << std::endl;

    //Search Tree Find
    tm = clock();
    for(int i=0; i<n1Elem; i++)
        st_test1_2.find(n12key[i]);
    tm = clock() - tm;
    st_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (i)  Search Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //AVL Tree Find
    tm = clock();
    for(int i=0; i<n1Elem; i++)
        avl_test1_2.find(n12key[i]);
    tm = clock() - tm;
    avl_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (ii) AVL Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //comparison
    if(st_Clock < avl_Clock)
        std::cout << "          -> Search Tree Find was faster than AVL Tree's." << std::endl;
    else
        std::cout << "          -> AVL Tree Find was faster than Search Tree's." << std::endl;

    delete[] n12key;
    delete[] n12val;

    std::cout << " ------------" << std::endl;
    std::cout << " 2. size = 10000" << std::endl;
    //In skewed order(increasing order)
    std::cout << " " << std::endl;
    std::cout << "  2-(1). Skewed Order(Increasing Order)" << std::endl;
    std::cout << " " << std::endl;
    std::cout << "    (a). Insert Operation" << std::endl;

    int n2Elem = 10000;
    int* n21key = new int[n2Elem];
    float* n21val = new float[n2Elem];

    for(int i=0; i<n2Elem; i++)    //initialize
    {
        n21key[i] = i+1;   //keys are initialized in increasing order.
        n21val[i] = (float) std::rand()/RAND_MAX * 20000;  //value doesn't matter, so I will use it repeatedly
    }

    //Search Tree Insertion
    SearchTree<EntryType>    st_test2_1;

    tm = clock();
    for(int i=0; i<n2Elem; i++)
        st_test2_1.insert(n21key[i], n21val[i]);
    tm = clock() - tm;
    st_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (i)  Search Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //AVL Tree Insertion
    AVLTree<EntryType>    avl_test2_1;

    tm = clock();
    for(int i=0; i<n2Elem; i++)
        avl_test2_1.insert(n21key[i], n21val[i]);
    tm = clock() - tm;
    avl_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (ii) AVL Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //comparison
    if(st_Clock < avl_Clock)
        std::cout << "          -> Search Tree Insertion was faster than AVL Tree's." << std::endl;
    else
        std::cout << "          -> AVL Tree Insertion was faster than Search Tree's." << std::endl;
    std::cout << " " << std::endl;
    std::cout << "    (b). Find Operation" << std::endl;

    //Search Tree Find
    tm = clock();
    for(int i=0; i<n2Elem; i++)
        st_test2_1.find(n21key[i]);
    tm = clock() - tm;
    st_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (i)  Search Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //AVL Tree Find
    tm = clock();
    for(int i=0; i<n2Elem; i++)
        avl_test2_1.find(n21key[i]);
    tm = clock() - tm;
    avl_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (ii) AVL Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //comparison
    if(st_Clock < avl_Clock)
        std::cout << "          -> Search Tree Find was faster than AVL Tree's." << std::endl;
    else
        std::cout << "          -> AVL Tree Find was faster than Search Tree's." << std::endl;

    delete[] n21key;
    delete[] n21val;

    std::cout << " " << std::endl;

    std::cout << "  2-(2). Random Order" << std::endl;
    std::cout << " " << std::endl;
    std::cout << "    (a). Insert Operation" << std::endl;

    int* n22key = new int[n2Elem];
    float* n22val = new float[n2Elem];

    for(int i=0; i<n2Elem; i++)    //randomly initialize
    {
        n22key[i] = std::rand();
        n22val[i] = (float) std::rand()/RAND_MAX * 20000;
    }

    //Search Tree Insertion
    SearchTree<EntryType>    st_test2_2;

    tm = clock();
    for(int i=0; i<n2Elem; i++)
        st_test2_2.insert(n22key[i], n22val[i]);
    tm = clock() - tm;
    st_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (i)  Search Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //AVL Tree Insertion
    AVLTree<EntryType>    avl_test2_2;

    tm = clock();
    for(int i=0; i<n2Elem; i++)
        avl_test2_2.insert(n22key[i], n22val[i]);
    tm = clock() - tm;
    avl_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (ii) AVL Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //comparison
    if(st_Clock < avl_Clock)
        std::cout << "          -> Search Tree Insertion was faster than AVL Tree's." << std::endl;
    else
        std::cout << "          -> AVL Tree Insertion was faster than Search Tree's." << std::endl;
    std::cout << " " << std::endl;
    std::cout << "    (b). Find Operation" << std::endl;

    //Search Tree Find
    tm = clock();
    for(int i=0; i<n2Elem; i++)
        st_test2_2.find(n22key[i]);
    tm = clock() - tm;
    st_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (i)  Search Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //AVL Tree Find
    tm = clock();
    for(int i=0; i<n2Elem; i++)
        avl_test2_2.find(n22key[i]);
    tm = clock() - tm;
    avl_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (ii) AVL Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //comparison
    if(st_Clock < avl_Clock)
        std::cout << "          -> Search Tree Find was faster than AVL Tree's." << std::endl;
    else
        std::cout << "          -> AVL Tree Find was faster than Search Tree's." << std::endl;

    delete[] n22key;
    delete[] n22val;

    std::cout << " ------------" << std::endl;

    std::cout << " 3. size = 100000" << std::endl;
    //In skewed order(increasing order)
    std::cout << " " << std::endl;

    std::cout << "  3-(1). Skewed Order(Increasing Order)" << std::endl;
    std::cout << " " << std::endl;
    std::cout << "    (a). Insert Operation" << std::endl;

    int n3Elem = 100000;
    int *n31key = new int[n3Elem];
    float *n31val = new float[n3Elem];
    
    for(int i=0; i<n3Elem; i++)    //initialize
    {
        n31key[i] = i+1;   //keys are initialized in increasing order.
        n31val[i] = (float) std::rand()/RAND_MAX * 20000;  //value doesn't matter, so I will use it repeatedly
    }
    
    //Search Tree Insertion
    SearchTree<EntryType>    st_test3_1;

    tm = clock();
    for(int i=0; i<n3Elem; i++)
        st_test3_1.insert(n31key[i], n31val[i]);
    tm = clock() - tm;
    st_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (i)  Search Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //AVL Tree Insertion
    AVLTree<EntryType>    avl_test3_1;

    tm = clock();
    for(int i=0; i<n3Elem; i++)
        avl_test3_1.insert(n31key[i], n31val[i]);
    tm = clock() - tm;
    avl_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (ii) AVL Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //comparison
    if(st_Clock < avl_Clock)
        std::cout << "          -> Search Tree Insertion was faster than AVL Tree's." << std::endl;
    else
        std::cout << "          -> AVL Tree Insertion was faster than Search Tree's." << std::endl;
    std::cout << " " << std::endl;
    std::cout << "    (b). Find Operation" << std::endl;

    //Search Tree Find
    tm = clock();
    for(int i=0; i< n3Elem; i++)
        st_test3_1.find(n31key[i]);
    tm = clock() - tm;
    st_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (i)  Search Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //AVL Tree Find
    tm = clock();
    for(int i=0; i<n3Elem; i++)
        avl_test3_1.find(n31key[i]);
    tm = clock() - tm;
    avl_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (ii) AVL Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //comparison
    if(st_Clock < avl_Clock)
        std::cout << "          -> Search Tree Find was faster than AVL Tree's." << std::endl;
    else
        std::cout << "          -> AVL Tree Find was faster than Search Tree's." << std::endl;

    delete[] n31key;
    delete[] n31val;

    std::cout << " " << std::endl;
    std::cout << "  3-(2). Random Order" << std::endl;
    std::cout << " " << std::endl;
    std::cout << "    (a). Insert Operation" << std::endl;

    int *n32key = new int[n3Elem];
    float *n32val = new float[n3Elem];

    for(int i=0; i<n3Elem; i++)    //randomly initialize
    {
        n32key[i] = std::rand();
        n32val[i] = (float) std::rand()/RAND_MAX * 20000;
    }

    //Search Tree Insertion
    SearchTree<EntryType>    st_test3_2;

    tm = clock();
    for(int i=0; i<n3Elem; i++)
        st_test3_2.insert(n32key[i], n32val[i]);
    tm = clock() - tm;
    st_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (i)  Search Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //AVL Tree Insertion
    AVLTree<EntryType>    avl_test3_2;

    tm = clock();
    for(int i=0; i<n3Elem; i++)
        avl_test3_2.insert(n32key[i], n32val[i]);
    tm = clock() - tm;
    avl_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (ii) AVL Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //comparison
    if(st_Clock < avl_Clock)
        std::cout << "          -> Search Tree Insertion was faster than AVL Tree's." << std::endl;
    else
        std::cout << "          -> AVL Tree Insertion was faster than Search Tree's." << std::endl;
    std::cout << " " << std::endl;
    std::cout << "    (b). Find Operation" << std::endl;

    //Search Tree Find
    tm = clock();
    for(int i=0; i<n3Elem; i++)
        st_test3_2.find(n32key[i]);
    tm = clock() - tm;
    st_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (i)  Search Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //AVL Tree Find
    tm = clock();
    for(int i=0; i<n3Elem; i++)
        avl_test3_2.find(n32key[i]);
    tm = clock() - tm;
    avl_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (ii) AVL Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;
    if(st_Clock < avl_Clock)
        std::cout << "          -> Search Tree Find was faster than AVL Tree's." << std::endl;
    else
        std::cout << "          -> AVL Tree Find was faster than Search Tree's." << std::endl;

    delete[] n32key;
    delete[] n32val;
    
    std::cout << " ------------" << std::endl;
    std::cout << " 4. size = 1000000" << std::endl;
    
    //In skewed order(increasing order)
    std::cout << " " << std::endl;
    
    std::cout << "  4-(1). Skewed Order(Increasing Order)" << std::endl;
    std::cout << " " << std::endl;
    std::cout << "    (a). Insert Operation" << std::endl;
    
    int n4Elem = 1000000;
    int *n41key = new int[n4Elem];
    float *n41val = new float[n4Elem];
    
    for(int i = 0; i < n4Elem; i++)    //initialize
    {
        n41key[i] = i+1;   //keys are initialized in increasing order.
        n41val[i] = (float) std::rand()/RAND_MAX * 20000;  //value doesn't matter, so I will use it repeatedly
    }

    //Search Tree Insertion
    SearchTree<EntryType>    st_test4_1;

    tm = clock();
    for(int i = 0; i < n4Elem; i++)
        st_test4_1.insert(n41key[i], n41val[i]);
    tm = clock() - tm;
    st_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (i)  Search Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    
    //AVL Tree Insertion
    AVLTree<EntryType>    avl_test4_1;
    
    tm = clock();
    for(int i = 0; i < n4Elem; i++)
        avl_test4_1.insert(n41key[i], n41val[i]);
    tm = clock() - tm;
    avl_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (ii) AVL Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;
    
    //comparison
    if(st_Clock < avl_Clock)
        std::cout << "          -> Search Tree Insertion was faster than AVL Tree's." << std::endl;
    else
        std::cout << "          -> AVL Tree Insertion was faster than Search Tree's." << std::endl;
    std::cout << " " << std::endl;
    std::cout << "    (b). Find Operation" << std::endl;

    //Search Tree Find
    tm = clock();
    for(int i = 0; i < n4Elem; i++)
        st_test4_1.find(n41key[i]);
    tm = clock() - tm;
    st_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (i)  Search Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;

    //AVL Tree Find
    tm = clock();
    for(int i=0; i<n4Elem; i++)
        avl_test4_1.find(n41key[i]);
    tm = clock() - tm;
    avl_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (ii) AVL Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;
    
    //comparison
    if(st_Clock < avl_Clock)
        std::cout << "          -> Search Tree Find was faster than AVL Tree's." << std::endl;
    else
        std::cout << "          -> AVL Tree Find was faster than Search Tree's." << std::endl;

    delete[] n41key;
    delete[] n41val;
    
    std::cout << " " << std::endl;
    std::cout << "  4-(2). Random Order" << std::endl;
    std::cout << " " << std::endl;
    std::cout << "    (a). Insert Operation" << std::endl;
    
    int *n42key = new int[n4Elem];
    float *n42val = new float[n4Elem];
    
    for(int i = 0; i < n4Elem; i++)    //randomly initialize
    {
        n42key[i] = std::rand();
        n42val[i] = (float) std::rand()/RAND_MAX * 20000;
    }
    
    //Search Tree Insertion
    SearchTree<EntryType>    st_test4_2;
    
    tm = clock();
    for(int i=0; i<n4Elem; i++)
        st_test4_2.insert(n42key[i], n42val[i]);
    tm = clock() - tm;
    st_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (i)  Search Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;
    
    //AVL Tree Insertion
    AVLTree<EntryType>    avl_test4_2;
    
    tm = clock();
    for(int i=0; i<n4Elem; i++)
        avl_test4_2.insert(n42key[i], n42val[i]);
    tm = clock() - tm;
    avl_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (ii) AVL Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;
    
    //comparison
    if(st_Clock < avl_Clock)
        std::cout << "          -> Search Tree Insertion was faster than AVL Tree's." << std::endl;
    else
        std::cout << "          -> AVL Tree Insertion was faster than Search Tree's." << std::endl;
    std::cout << " " << std::endl;
    std::cout << "    (b). Find Operation" << std::endl;
    
    //Search Tree Find
    tm = clock();
    for(int i=0; i<n4Elem; i++)
        st_test4_2.find(n42key[i]);
    tm = clock() - tm;
    st_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (i)  Search Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;
    
    //AVL Tree Find
    tm = clock();
    for(int i=0; i<n4Elem; i++)
        avl_test4_2.find(n42key[i]);
    tm = clock() - tm;
    avl_Clock = ((float)tm)/(float)CLOCKS_PER_SEC;
    std::cout << "       (ii) AVL Tree : " << ((float)tm)/(float)CLOCKS_PER_SEC << " seconds." << std::endl;
    
    //comparison
    if(st_Clock < avl_Clock)
        std::cout << "          -> Search Tree Find was faster than AVL Tree's." << std::endl;
    else
        std::cout << "          -> AVL Tree Find was faster than Search Tree's." << std::endl;
    
    delete[] n42key;
    delete[] n42val;
    std::cout << " ------------" << std::endl;

    return 0;
    
}

8) 레포트

점수 : 97/100

대부분의 구현을 책에서 찾을 수 있어서 그렇게 어렵지는 않았으나 restructure 함수를 구현하는데는 애를 좀 먹었다. 여러가지 케이스들을 생각해야 됐기 때문이다. 오히려 레포트를 쓰는 것이 더 힘들었던 것 같다. 함수가 구현되어 있는 방식 때문에 size가 커질 경우에 본인 컴퓨터에서 작동이 잘 되지 않았던 부분도 있었다. 그래도 실제로 AVLTree와 BST를 구현해볼 수 있었다는 것이 이번 과제의 장점이 아닐까 싶다.