알고리즘(Algorithm) 실습6

Posted by Patchman
2010.02.15 15:07 Univ Study/알고리즘과 실습

 

6-1. 다음에 주어진 프로그램을 참고해서 N(>100) 개의 자료를 rand()로 발생하고 이진 탐색트리에 BSTinsert()해서 이진 탐색트리(Binary search tree) T1을 만들고, 입력된 자료를 각각 탐색하는데 소요된 키의 평균비교회수를 출력하시오. (단, 평균비교회수는 각 자료 탐색을 위한 키의 비교회수 합계를 구한 다음에 전체 자료수 N으로 나누어서 계산함)

 

 

#include <iostream>

#include<stdlib.h>

using namespace std;

 

#define MAX 150

#define infoLILk 0 // 더미노드 이자 마지막 노드인 z의값

#define itemMIN -1 // Binary search tree의 head 값,

head의 오른쪽부터 노드가 오게 하기 위하여

 

typedef int itemType;

typedef int infoType;

 

int comparision = 0;

 

class BST

{

private:

struct node

{

itemType key;

infoType info;

struct node *l, *r;

// 구조체 초기화를 위해

node(itemType k, infoType i, struct node *ll, struct node *rr)

{ key = k; info = i; l = ll; r = rr; }

};

struct node *head, *z;

 

public:

BST(int max)

{

z = new node(0, infoLILk, 0, 0);

head = new node(itemMIN, 0, z, z);

}

 

~BST()

{

delete(z);

delete(head);

}

 

infoType BSTsearch(itemType v);

void BSTinsert(itemType v, infoType info);

void BSTresult();

};

 

infoType BST::BSTsearch(itemType v) // Binary search tree 를 탐색하는 함수

{

struct node *x = head->r;

z->key = v;

 

while(v != x->key){ // tree를 순회하며 v의 값을 탐색한다

comparision++; // 비교연산회수 카운터 증가

x = (v < x->key) ? x->l : x->r;

}

return x->info;

}

void BST::BSTinsert(itemType v, infoType info) // Binary search tree 를 구현하는 함수

{

struct node *p, *x;

p = head;

x = head->r;

 

while(x != z) // 전달받은 킷값이 들어갈 노드의 위치를 탐색한다

{

p = x;

x = (v < x->key) ? x->l : x->r;

}

 

x = new node(v, info, z, z); // 위치를 탐색한 x에 새로운 노드를 생성한다

if(v < p->key) p->l = x; // 부모 노드인 p와비교하여 l,r 위치를 결정한다.

else p->r = x;

}

 

void result() // 결과출력함수

{

cout << " 총 비교연산회수는: " << comparision << "\n"

cout << " 평균비교연산회수는: " << (comparision/MAX) << "\n\n"

}

 

void main()

{

BST T1(MAX);

 

itemType a[MAX];

itemType info = 0;

 

int i;

 

cout << "\n----------- Rand(" << MAX << ") ---------------\n\n"

for(i=0; i < MAX; i++){

a[i] = (rand() % MAX) + 1;

printf("%5d ; ", a[i]);

T1.BSTinsert(a[i], info++); // Rand() 함수를 통한 임의의 수 발생과 동시에 BSTinsert를 이용하여 Binary search tree 를 구현한다.

}

cout << "\n------------------------------------------------\n"

 

for(i=0; i < MAX; i++) T1.BSTsearch(a[i]); // Binary search tree 에 입력된 모든 자료를 탐색한다

 

cout << "----------- Tree T1 -----------\n\n"

result(); // 총 비교회수와, 평균 비교회수를 출력한다.

cout << "-------------------------------\n\n"

 

}

 

▣ 결과 출력

 








6-2. 6-1에서 만들어진 트리 T1의 자료들을 INORDER로 트래버설(출력)하면서 각 자료를 새로운 이진탐색트리 T2에 BSTinsert()해서 이지탐색트리를 생성한 다음에, T2의 각 자료를 탐색하는데 소요된 키의 평균비교회수를 출력하고, 6-1의 결과와 비교하시오.(참고, T2는 skewed binary search tree가 됨)

 

 

#include <iostream>

#include<stdlib.h>

using namespace std;

 

#define MAX 150

#define infoLILk 0

#define itemMIN -1

 

typedef int itemType;

typedef int infoType;

 

int comparision = 0;

 

class BST

{

private:

 

struct node

{

itemType key;

infoType info;

struct node *l, *r;

node(itemType k, infoType i, struct node *ll, struct node *rr)

{ key = k; info = i; l = ll; r = rr; }

};

struct node *head, *z;

 

public:

BST(int max)

{

z = new node(0, infoLILk, 0, 0);

head = new node(itemMIN, 0, z, z);

}

 

~BST()

{

delete(z);

delete(head);

}

 

infoType BSTsearch(itemType v);

void BSTinsert(itemType v, infoType info);

 

void BSTInorderTraverse(BST *t2);

void BSTInorderTraverse(node *t, BST *t2);

 

};

 

infoType BST::BSTsearch(itemType v)

{

struct node *x = head->r;

z->key = v;

 

while(v != x->key){

comparision++;

x = (v < x->key) ? x->l : x->r;

}

return x->info;

}

 

void BST::BSTinsert(itemType v, infoType info)

{

struct node *p, *x;

p = head;

x = head->r;

 

while(x != z)

{

p = x;

x = (v < x->key) ? x->l : x->r;

}

 

x = new node(v, info, z, z);

if(v < p->key) p->l = x;

else p->r = x;

}

 

// overloading을 이용해 첫 노드인 head->r을 class T2와 함께 다시 BSTInorderTraverse로 보낸다.

void BST::BSTInorderTraverse(BST *t2)

{

BSTInorderTraverse(head->r, t2);

}

 

// 전달받은 노드와 class T2를 inorder traverse 하며 BSTinsert로 보내 tree T2를 생성한다.

void BST::BSTInorderTraverse(node *t, BST *t2)

{

if(t != z)

{

BSTInorderTraverse(t->l, t2);

t2->BSTinsert(t->key,t->key);

BSTInorderTraverse(t->r, t2);

}

}

 

void result() // 결과출력함수

{

cout << " 총 비교연산회수는: " << comparision << "\n"

cout << " 평균비교연산회수는: " << (comparision/MAX) << "\n\n"

comparision = 0; // T1의비교연산회수출력후초기화

}

 

void main()

{

BST T1(MAX), T2(MAX); // T1, T2 클래스생성

 

itemType a[MAX];

itemType info = 0;

int i;

 

cout << "\n------------- Rand(" << MAX << ") -------------\n\n"

for(i=0; i < MAX; i++){

a[i] = (rand() % MAX) + 1;

printf("%5d ; ", a[i]);

T1.BSTinsert(a[i],info++);

}

cout << "\n------------------------------------------------\n"

 

for(i=0; i < MAX; i++) T1.BSTsearch(a[i]);

 

cout << "----------- Tree T1 -----------\n\n"

result();

cout << "-------------------------------\n\n"

 

T1.BSTInorderTraverse(&T2); // T1의자료를Inorder traverse 하면서

// T2에BSTinsert 하기위해T2 Class를전달한다

for(int i=0; i < MAX; i++) T2.BSTsearch(a[i]);

 

cout << "----------- Tree T2 -----------\n\n"

result();

cout << "-------------------------------\n\n"

}

 

▣ 결과 출력

 

 

 


 

6-3. 정수 a와 b를 입력하여 6-1에서 만들어진 Binary search tree T1에서 a<x<b에 해당하는 x를 모두 찾는 알고리즘 BstRange(T1, a, b)를 기술하고, 구현하여 범위 (a, b)에 속하는 원소의 값과 총 개수를 출력하시오. 단, 출력할 원소수가 10개 이상이면 10개 까지만 출력함.

 

#include <iostream>

#include<stdlib.h>

using namespace std;

 

#define MAX 150

#define infoLILk 0

#define itemMIN -1

 

typedef int itemType;

typedef int infoType;

 

int comparision = 0;

int rangecount = 0; // 범위에 속하는 원소의 총 개수를 구하기 위한 변수

 

class BST

{

private:

struct node

{

itemType key;

infoType info;

struct node *l, *r;

node(itemType k, infoType i, struct node *ll, struct node *rr)

{ key = k; info = i; l = ll; r = rr; }

};

struct node *head, *z;

 

public:

BST(int max)

{

z = new node(0, infoLILk, 0, 0);

head = new node(itemMIN, 0, z, z);

}

 

~BST()

{

delete(z);

delete(head);

}

 

infoType BSTsearch(itemType v);

void BSTinsert(itemType v, infoType info);

void BSTresult();

 

void BST::BstRange(int a, int b); // 범위의 원소를 찾기 위한 함수 - Overloading

void BST::BstRange(node *x, int a, int b);

};

 

infoType BST::BSTsearch(itemType v)

{

struct node *x = head->r;

z->key = v;

 

while(v != x->key){

comparision++;

x = (v < x->key) ? x->l : x->r;

}

return x->info;

}

 

void BST::BSTinsert(itemType v, infoType info)

{

struct node *p, *x;

p = head;

x = head->r;

 

while(x != z)

{

p = x;

x = (v < x->key) ? x->l : x->r;

}

 

x = new node(v, info, z, z);

if(v < p->key) p->l = x;

else p->r = x;

}

 

// overloading을 이용해 전달받은 Range값 a,b와 첫 노드인 head->r를 다시 BstRange로 보낸다.

void BST::BstRange(int a, int b)

{

BstRange(head->r, a, b);

}

 

// Range값 a,b 범위에 있는 원소의 값을 출력하고, 카운터한다.

void BST::BstRange(node *x, int a, int b)

{

if(x != z){ // 마지막 노드까지a,b 두 범위에 속하는 원소 값을 찾는다

if(x->key >= a && x->key <= b){

// 범위에 속하는 값은 10개 까지만 출력한다.

if(rangecount < 10) printf("%3d", x->key);

rangecount++; // 총 개수는 계속 카운터 한다

if(x->key == a){

BstRange(x->r, a, b);

}else{

BstRange(x->l, a, b);

BstRange(x->r, a, b);

}

}else if(x->key < a){

// 노드의 값이 a 보다 작다면 노드의 r로 다시 recursion한다

BstRange(x->r, a, b);

}else if(x->key > b){

// 노드의 값이 b 보다 크다면 노드의 l로 다시 recursion한다

BstRange(x->l, a, b);

}

}

}

 

void main()

{

BST T1(MAX);

 

itemType a[MAX];

itemType info = 0;

 

int x,y,i;

 

for(i=0; i < MAX; i++){

a[i] = (rand() % MAX) + 1;

T1.BSTinsert(a[i], info++);

}

 

for(i=0; i < MAX; i++) T1.BSTsearch(a[i]);

 

cout << "Input Range : "

cin >> x >> y; // 찾고자하는범위의두수를입력받는다

cout << "\n\nRange " << x << " " << y << " 에속하는원소의값: "

T1.BstRange(x, y); // 입력받은두수를BstRange로보낸다

cout << "\n\nRange " << x << " " << y_

_ << " 에속하는원소의개수: " << rangecount << "\n\n\n"

 

}

 

▣ 결과 출력

 

 

 

'Univ Study > 알고리즘과 실습' 카테고리의 다른 글

알고리즘(Algorithm) 실습8  (0) 2010.02.15
알고리즘(Algorithm) 실습7  (0) 2010.02.15
알고리즘(Algorithm) 실습6  (0) 2010.02.15
알고리즘(Algorithm) 실습5  (0) 2010.02.15
알고리즘(Algorithm) 실습4  (0) 2010.02.15
알고리즘(Algorithm) 실습3  (0) 2010.02.15