레드-블랙 트리 탐색.

2-3-4트리라는게 있는데 2노드가 많을 경우 공간의 낭비가 심하다는 단점이 있다. 이것의 단점을 극복한 것이다. 2-3-4트리에 관한 설명은 여기에 잘 되어 있다.

레드-블랙 트리의 성질.

1. 루트나 외부 노드는 모두 블랙이다.

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

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

4. 루트에서 각 외부 노드까지의 경로에 있는 블랙 링크의 수는 모두 같다.

레드-블랙 트리의 자세한 설명은 이 블로그에 잘 나와있다.

실행시간은 표본이 작아서 그런지 이진 탐색 트리랑 비슷하다.

// ConsoleApplication5.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//
#include "stdafx.h"
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

const int black = 0;
const int red = 1;

const int N=10000;

class Dict
{
public:
	Dict()
	{
		z = new node(0,0,0);
		z->l = z; z->r = z;
		head = new node(0,0,z);
	}
	int search(int search_key);
	void insert(int v);
private:
	struct node
	{
		int key;
		struct node *l, *r;
		node(int k, struct node *ll, struct node *rr)
		{ key = k; l = ll; r = rr; }
	};
	struct node *head, *z;
};

int Dict::search(int 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(int v)
{
	struct node *p, *x;
	p = head; x = head->r;
	while(x != z)
	{
		p = x;
		if(x->key==v) return;
		x = (x->key > v) ? x->l : x->r;
	}
	x = new node(v,z,z);
	if(p->key > v) p->l = x;
	else p->r = x;
}

void init(int key[], int search_key[])
{
	int i,index, temp[N+1];
	for(i=1;i<=N;i++)
	{
		key[i] = i;
		search_key[i] = i;
		temp[i] = 0;
	}
	srand(time(NULL));
	for(i=1;i<=N;i++)
	{
		index = rand()%N+1;
		if(temp[index]==0)
			temp[index] = key[i];
		else
		{
			while(temp[index] != 0)
				index = (index % N) + 1;
			temp[index] = key[i];
		}
	}
	for(i=1;i<=N;i++)
	{
		key[i] = temp[i];
	}
}

//red_black tree
struct node 
{
	int b;
	int key;
	struct node *l, *r;
	node(int bb, int k, struct node *ll, struct node *rr)
	{ b = bb, key = k; l = ll, r = rr; };
} *head, *z, *gg, *g, *p, *x;

void split(int v);
struct node *rotate(int v, struct node *y);

class Dict2
{
public:
	Dict2()
	{
		z = new node(black,0,0,0);
		z->l = z; z->r=z;
		head = new node(black,0,0,z);
	}
	int search(int search_key);
	void insert(int v);
};

int Dict2::search(int 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 Dict2::insert(int 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(int 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(int 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 init2(int key[], int search_key[])
{
	int i,index,temp[N+1];
	for(i=1;i<=N;i++)
	{
		key[i] = i;
		search_key[i] = i;
		temp[i] = 0;
	}
	srand(time(NULL));
	for(i=1;i<=N;i++)
	{
		index = rand() % N+1;
		if(temp[index] == 0)
			temp[index] = key[i];
		else
		{
			while (temp[index] != 0)
				index = (index % N) + 1;
			temp[index] = key[i];
		}
	}
	for(i=1;i<=N;i++)
	{
		key[i] = temp[i];
	}
}
int main()
{
	Dict d2;
	int i,result,key[N+1],search_key[N+1];
	double start_time;

	init2(key, search_key);
	for(i=1;i<=N;i++) d2.insert(key[i]);
	start_time = clock();

	for(i=1;i<=N;i++)
	{
		result = d2.search(search_key[i]);
		if(result == -1 || result != search_key[i])
		{
			cout<<"탐색 오류."<<endl;
		}
	}
	cout<<"레드 블랙 트리의 실행 시간 (N = "<<N<<") : "<<clock() - start_time<<endl;
	cout<<"탐색 완료."<<endl;
	return 0;
}