red black tree: 1개의 글

알고리즘(Algorithm) 실습7

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

 

7-1. N(>100) 개의 자료를 rand()로 발생하고 이진 탐색트리에 insert()해서 이진 탐색트리(Binary search tree) T1을 만들고, 이 트리 T1의 자료들을 INORDER 트래버설 순서로 트래버설(출력)하면서, 각 자료를 insert()해서 새로운 이진탐색트리 T2와 red-black tree T3를 각각 생성한다. T1, T2 및 T3의 각 자료를 탐색하는데 소요된 키 평균비교회수를 출력하고, 비교하시오.

 

#include <iostream>

#include<stdlib.h>

using namespace std;

 

#define MAX 150

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

#define itemMIN -1 // Binary search tree의 head 값, // head의 오른쪽부터 노드가 오게하기 위하여

 

// Red Black Tree tag

#define black 0

#define red 1

 

typedef int itemType;

typedef int infoType;

 

float comparision = 0.0;

 

 

////////////////////////////////////////////////////////////////////////////////////

//////////////////////////////// RB Tree Class /////////////////////////////////////

 

class RBtree

{

private:

 

struct node

{

itemType key, tag;

infoType info;

struct node *l, *r;

// 구조체초기화

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

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

};

struct node *head, *tail, *x, *p, *g, *gg, *z;

 

public:

 

RBtree(int max)

{

z = new node(0, infoNIL, black, 0, 0);

z->l = z;

z->r = z;

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

}

 

~RBtree()

{

delete head;

delete z;

delete x;

}

 

infoType RBTsearch(itemType v);

void RBTinsert(itemType v, infoType info);

void split(itemType k);

 

// rotate 함수, class밖으로 꺼내 보았으나 에러발생

// 에러를 잡지못해 class 안에 구현하였습니다.

struct node *rotate(itemType k, node *y)

{

struct node *high, *low;

high = (k < y->key) ? y->l : y->r;

 

if(k < high->key)

{

low = high->l;

high->l = low->r;

low->r = high;

}

else

{

low = high->r;

high->r = low->l;

low->l = high;

}

 

if(k < y->key) y->l = low;

else y->r = low;

 

return low;

}

 

};

 

// Red Black Tree는물리적으로Binary Search Tree와같으므로

// 똑같은Search 함수를사용한다.

infoType RBtree::RBTsearch(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;

}

 

// Red Black 형태를유지하기위해insert 하며split한다.

void RBtree::RBTinsert(itemType k, infoType info)

{

x = head; p = head; g = head;

 

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

{

gg = g; g = p; p = x;

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

if(x->l->tag && x->r->tag) split(k);

}

 

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

 

// 부모노드인p와비교하여l,r 를결정한다.

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

else p->r = x;

split(k);

head->r->tag = black;

}

 

// split과rotate를통해Red Black 트리형태를구현한다.

void RBtree::split(itemType k)

{

x->tag = red;

x->l->tag = black;

x->r->tag = black;

 

if(p->tag)

{

g->tag = red;

if(k < g->key != k < p->key) p = rotate(k, g);

x = rotate(k, gg);

x->tag = black;

}

}

 

 

////////////////////////////////////////////////////////////////////////////////////

//////////////////////////////// BS Tree Class /////////////////////////////////////

 

// Binary Search Tree 는 6번실습에서 구현 하였으므로 주석 생량합니다.

class BStree

{

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:

BStree(int max)

{

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

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

}

 

~BStree()

{

delete(z);

delete(head);

}

 

infoType BSTsearch(itemType v);

void BSTinsert(itemType v, infoType info);

 

void BStree::BSTInorderTraverse(BStree *t2, RBtree *t3);

void BSTInorderTraverse(node *t, BStree *t2, RBtree *t3);

 

};

 

infoType BStree::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 BStree::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;

}

 

// Overloarding 을통해BStree T1을InorderTraverse하며

// T2, 그리고RBtree Class의T3를구현한다.

void BStree::BSTInorderTraverse(BStree *t2, RBtree *t3)

{

BSTInorderTraverse(head->r, t2, t3);

}

 

void BStree::BSTInorderTraverse(node *t, BStree *t2, RBtree *t3)

{

if(t != z)

{

BSTInorderTraverse(t->l, t2, t3);

t2->BSTinsert(t->key,t->key); // T2 생성

t3->RBTinsert(t->key,t->key); // T3 생성

BSTInorderTraverse(t->r, t2, t3);

}

}

 

 

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

{

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

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

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

}

 

 

void main()

{

BStree T1(MAX), T2(MAX);

 

RBtree T3(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++);

}

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, &T3);

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

 

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

result();

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

 

 

for(int i=0; i < MAX; i++) T3.RBTsearch(a[i]);

 

cout << "----------- Tree T3 -----------\n\n"

result();

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

 

 

}

 

 

▣ 결과 출력

 

 

 

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

알고리즘(Algorithm) 실습10  (0) 2010.02.15
알고리즘(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