재시민

삽입연산

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;

}

회전

struct node* rotate(itemType k, node* y)// k - 탐색키, 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;
	}

스플릿 (분할)

void RBtree::split(itemType k)

{

	x->tag = red;

	x->l->tag = black;//NILL

	x->r->tag = black;//NILL



	if (p->tag)//부모가 레드라면

	{

		g->tag = red;

		if (k < g->key != k < p->key) p = rotate(k, g); // p = g->l, x = p->r 이거나, p = g->r, x = p->l 일때

		x = rotate(k, gg);

		x->tag = black;

	}

}

탐색은 BST 탐색과 똑같음

특징

• BST 는 편향트리 (skewed tree) 로 불균형 트리가 될 수 있는 반면 RBTree 는 균형 트리이다.
• 따라서, 모든 삽입, 제거, 탐색 연산은 O(logn)

struct node {
	int key;
	struct node* l;
	struct node* r;
};


struct node* TreeInit() {
	node* t, * head;
	head = new node;
	head->l = NULL;
	head->r = NULL;
	head->key = 0;

	return head;
}

struct node* TreeSearch(struct node* head, int xkey) {
	struct node* t;
	if (head->key == xkey) return (head);
	t = head->r;
	while (t != NULL) {
		if (xkey == t->key) return(t);
		if(t!=NULL) if (xkey < t->key) t = t->l;
		if(t!= NULL) if (xkey > t->key) t = t->r;
	}
	return(NULL);
}

void TreeInsert(struct node* head, int xkey) {
	struct node* p, * t;
	p = head; t = p->r;
	while (t != NULL) {
		p = t;
		if (xkey == t->key)return;
		else if (xkey < t->key) t = t->l;
		else t = t->r;
	}
	t = new node;//새로운 노드 생성
	t->key = xkey; t->l = NULL; t->r = NULL; // 자식없음
	if (xkey < p->key) p->l = t; //부모와 비교하여 크면 좌 작으면 우에 배치
	else p->r = t;
}

struct node* minValueNode(struct node* node) {
	struct node* current = node;

	while (current->l != NULL) {
		current = current->l;
	}

	return current;
}
struct node* deleteNode(struct node* root, int key) {
	if (root == NULL) return root;

	if (key < root->key) root->l = deleteNode(root->l, key);
	else if (key > root->key) root->r = deleteNode(root->r, key);
	else {
		if (root->l == NULL) { // 자식이 없을때
			struct node* temp = root->r;
			free(root);
			return temp;
		}
		else if (root->r == NULL) // 자식이 하나
		{
			struct node* temp = root->l;
			free(root);
			return temp;
		}
		//자식이 둘
		struct node* temp = minValueNode(root->r);
		root->key = temp->key;
		root->r = deleteNode(root->r, temp->key);
	}
	return root;
}

시간 복잡도

삽입 : O(logN)

제거 : O(logN)

탐색 : O(logN)

단, 편향트리일 경우 O(N) 가능

int BSearch(vector<int>& v, int k) {
	int low = 0;
	int high = v.size() - 1;
	int mid;

	while (low <= high) {
		mid = (low + high) / 2;
		if (v[mid] == k)
			return mid;
		else if (v[mid] > k)
			high = mid - 1;
		else low = mid + 1;
	}
	return -1;
}

시간 복잡도

평균 시간복잡도 = O(logn)

최악 시간복잡도 = O(logn)

알고리즘

1.  mid 값설정

2. v[mid] 값이 k 와 같다면 리턴

3. v[mid] > k 이면 high = mid + 1 로 설정 (이미 정렬되어있기 때문에 mid + 1 초과로는 탐색할 필요 없음)

4. v[mid] < k 이면 low = mid + 1

5. 반복

int get_Max_radix(vector<int> &v, int n) {// 가장 큰 값을 찾고 그 값의 자릿수 리턴
	int max_val = 0;
	int i;
	for (i = 0;i < n;i++) {
		if (max_val < v[i]) max_val = v[i];
	}
	int max_radix = 1;
	while (max_val / 10 > 0) {
		max_val /= 10;
		max_radix *= 10;
	}
	return max_radix;
}

void radixSort(vector<int>& v, int n) {
	int max_radix = get_Max_radix(v, n);
	queue<int> q[10];//0~9

	for (int i = 1; i <= max_radix;i*=10) {//자릿수 값을 증가시키면서 정렬순회
		for (int j = 0;j < n;j++) {
			int k = 0;// 자리수
			if (v[j] >= i) k = (v[j] / i) % 10;
			q[k].push(v[j]);
		}
		int idx = 0;
		for (int j = 0;j < 10;j++) {
			while (!q[j].empty()) {
				v[idx] = q[j].front();
				q[j].pop();
				idx++;
			}
		}
	}
}

제자리성 : 제자리 정렬 x (추가 자료구조 사용)

안정성 : 안정 (순서대로 뒤쪽 레코드 부터 가장 뒤쪽에 배치)

시간 복잡도

평균 시간복잡도 = O(n)

음수에는 사용 불가능