[c++] 알고리즘 레드-블랙 트리

레드-블랙 트리 (Red-Black Tree)

- 2-3-4 트리를 표준 이진 트리로 표현하는 방법

- 노드당 추가로 1 비트가 더 필요함

- 블랙 링크는 보통의 노드이고, 3-노드와 4-노드는 레드 링크로 연결된 이진 트리로 표현

 

 

 

 

 

 

 

성질

- 루트나 외부 노드는 모두 블랙

- 루트에서 외부 노드까지의 경로 상에는 2개의 연속된 레드 노드가 포함되지 않음

- 루트에서 각 외부 노드까지의 경로에 있는 블랙 노드의 수는 모두 같음

- 동일한 키를 가지는 레코드는 노드의 왼쪽과 오른쪽에 모두 올 수 있음

- 동일한 키가 여러 개 있을 때 주어진 키를 갖는 모든 노드를 찾는 것이 어려움

 

 

 

 

 

4-노드의 분할

 

 

 

 

4-노드의 분할 (회전 필요)

 

 

 

단일 회전

 

 

이중 회전

 

 

 

 

 

 

구축 과정

키(2, 1, 8, 9, 7, 3, 6, 4, 5)

 

 

 

 

 

 

 

성능 특성

- r을 서열(rank)이라 할 때, 노드 수(키 값의 수) N은 N ≥ 2r-1

> 서열 : 어느 한 내부 노드에서 외부 노드까지의 경로 상에 있는 블랙 포인터의 수

- 레드-블랙 트리의 높이 h는 h ≤ 2log(N+1)이므로, 삽입 시간 복잡도는 Ο(logN)

- 레드-블랙 트리는 이진 탐색 트리이기 때문에 탐색은 일반 이진 탐색 트리의 탐색 연산으로 수행할 수 있으므로 레드-블랙 트리의 탐색 시간 복잡도는 Ο(logN)

 

 

 

 

 

소스 코드

#include <iostream>

#include <time.h>

#include <stdlib.h>

#include <fstream>

 

using namespace std;

const int black = 0;

const int red = 1;

 

const int N = 1000000;

 

double key[N+1], search_key[N+1];

 

struct node {

           int b;

           double key;

           struct node *l, *r;

           node(int bb, double k, struct node *ll, struct node *rr)

           { b = bb, key = k; l = ll, r = rr; };   

} *head, *z, *gg, *g, *p, *x;

 

void split(double v);

struct node *rotate(double v, struct node *y);

 

class Dict

{

public:

           Dict() {

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

                     z->l = z; z->r = z;

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

           }

           double search(double search_key);

           void insert(double v);

           void init(int k);

           void initSearch();

};

 

double Dict::search(double search_key)

{

           struct node *x = head->r;

           while (x != z) {

                     if (x->key == search_key) return x->key;

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

 

           }

           return -1;

}

 

void Dict::insert(double v)

{

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

           while (x != z) {

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

                     if (x->key == v) return;

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

                     if (x->l->b && x->r->b) split(v);

           }

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

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

           else p->r = x;

           split(v); head->r->b = black;

}

 

void split(double v)

{

           x->b = red; x->l->b = black; x->r->b = black;

           if (p->b) {

                     g->b = red;

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

                     x = rotate(v, gg);

                     x->b = black;

           }

}

 

struct node *rotate(double v, struct node *y)

{

           struct node *gc, *c;

           c = (y->key > v) ? y->l : y->r;

           if (c->key > v) {

                     gc = c->l; c->l = gc->r; gc->r = c;

           }

           else {

                     gc = c->r; c->r = gc->l; gc->l = c;

           }

           if (y->key > v) y->l = gc;

           else y->r = gc;

           return gc;

}

 

 

void Dict::init(int k)

{

           ifstream file1, file2;

 

           int i=0; //4개씩 묶음만들기

           int j=1; //묶음갯수

           char ch;

 

           if(k==1)

           {

                     file1.open("sorted_dict.txt");

                     if(file1.is_open())

                                cout<<"open"<<endl;

                     else

                                cout<<"error"<<endl;

 

                     while(!file1.eof())

                     {

                                file1.get(ch); //파일에서 문자하나씩 얻기

                                if(i<4)

                                          key[j]=key[j]*1000+(int)ch;

                                i++;

                                if(i==5)

                                {

                                          insert(key[j]);

                                          j++;

                                          i=0;

                                }

                     }

                     file1.close();

           }

 

           else if(k==2)

           {

                     file2.open("dict.txt");

                     if(file2.is_open())

                                cout<<"open"<<endl;

                     else

                                cout<<"error"<<endl;

 

                     while(!file2.eof())

                     {

                                file2.get(ch); //파일에서 문자하나씩 얻기

                                if(i<4)

                                          key[j]=key[j]*1000+(int)ch;

                                i++;

                                if(i==5)

                                {

                                          insert(key[j]);

                                          j++;

                                          i=0;

                                }

                     }

                     file2.close();

           }

}

 

void Dict::initSearch()

{         

           ifstream searchKeyFile;

           searchKeyFile.open("search_key.txt");

 

           double start_time;

           char searchCh;

           int i=0; //4개씩 묶음만들기

           int j=1; //묶음갯수

           double result;

 

           if(searchKeyFile.is_open())

                     cout<<"open"<<endl;

           else

                     cout<<"error"<<endl;

 

           start_time = clock();

 

           while(!searchKeyFile.eof())

           {

                     searchKeyFile.get(searchCh); //파일에서 문자하나씩 얻기

                     if(i<4)

                                search_key[j]=search_key[j]*1000+(int)searchCh;

                     i++;

                     if(i==5)

                     {

                                result = search(search_key[j]);

                                if (result == -1 || result != search_key[j]) {

                                          cout << "탐색 오류." << endl;

                                }

                                j++;

                                i=0;

                     }                   

           }

 

           cout << "레드 블랙 트리의 실행 시간 (N = " << N << ") : " <<

                     clock() - start_time << endl;

           cout << "탐색 완료." << endl;

 

           searchKeyFile.close();

}

 

 

void main()

{

           Dict d;

           int input;

 

           cout<<"원하는 파일의 숫자를 입력하세요"<<'\n'<<"1. sorted_dict 탐색"<<'\n'<<"2. dict 탐색"<<endl;

           cin>>input;

 

           if(input==1 || input==2)

                     d.init(input);

           else

           {

                     cout<<"숫자를 잘못 입력했습니다."<<endl;

                     return;

           }

 

           cout<<"insert finish"<<endl;

           d.initSearch();

}