재시민

struct bucket* hashTable = NULL;
struct bucket* hashTable1 = NULL;
struct bucket* hashTable2 = NULL;
int SIZE = 11;
int SIZE1 = 101;
int SIZE2 = 1001;


struct Node {
	int key;
	int value;
	struct Node* next;
};

struct bucket {

	struct Node* head;
	int count;
};

struct Node* createNode(int key, int value) {

	struct Node* newNode;

	newNode = new Node;

	newNode->key = key;
	newNode->value = value;

	newNode->next = NULL;

	return newNode;
}

int hashFunction(int key, int SIZE) {

	return key % SIZE;
}

int hashBuild = 0;
int hashBuild1 = 0;
int hashBuild2 = 0;
void insert(struct bucket* hashTable, int key, int value, int SIZE) {

	int hashIndex = hashFunction(key, SIZE);

	struct Node* newNode = createNode(key, value);

	if (hashTable[hashIndex].count == 0) {
		hashTable[hashIndex].head = newNode;
		hashTable[hashIndex].count = 1;
		hashBuild++;

	}

	else {
		newNode->next = hashTable[hashIndex].head;
		hashTable[hashIndex].head = newNode;
		hashTable[hashIndex].count++;
		hashBuild++;

	}

	return;
}
int nodeCompare = 0;
void search(struct bucket* hashTable, int key, int SIZE) {

	int hashIndex = hashFunction(key, SIZE);
	struct Node* node = hashTable[hashIndex].head;

	if (node == NULL) {

		nodeCompare++;
		return;
	}

	while (node != NULL) {
		if (node->key == key) {
			nodeCompare++;
			//std::cout << "key found key = " << node->key << " value = " << node->value;
			break;
		}
		nodeCompare++;
		node = node->next;
	}
	//std::cout << "\nno key found";
	return;
}

void display() {
	struct Node* horse;
	int i = 0;

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

		horse = hashTable[i].head;

		std::cout << "Bucket[" << i << "] : ";

		while (horse != NULL) {
			printf("(key:%d, val:%d) -> ", horse->key, horse->value);
			horse = horse->next;

		}
		printf("\n");
	}
	printf("\n-------end of display--------");
	return;
}

int isPointInside(struct point A, vector<point>& v, int N) {
	int Count, i, LastPoint;
	bool PointOnTestLine = false;
	struct line TestLine, PolyLine;
	Count = LastPoint = 0;
	TestLine.p1 = A; TestLine.p2 = A;
	TestLine.p2.x = 9999;
	for (i = 0;i <= N;i++) {
		PolyLine.p1 = PolyLine.p2 = v[i];
		if (intersection(TestLine, PolyLine)) {
			PointOnTestLine = true;
			LastPoint = i;
		} //테스트 라인에 점이 있다
		else {// 테스트 라인과 변끼리 교차 확인
			PolyLine.p2 = v[LastPoint];
			LastPoint = i;
			if (!PointOnTestLine) {// false 라면
				if (intersection(PolyLine, TestLine)) Count++;
			}
			else {// true 라면
				if (direction(TestLine.p1, PolyLine.p2, PolyLine.p1) * direction(TestLine.p1, PolyLine.p2, v[LastPoint - 2]) < 0) {
					Count++; PointOnTestLine = false;
				}
			}
		}
	}
	if ((Count % 2) == 1) {
		cout << "true"; return 0;
	}
	else {
		cout << "false";
		return 0;
	}
}

void quickSort(vector<int>& v, int start, int end) {
	int pivot, left, right;
	pivot = start;
	left = start + 1;
	right = end;
	if (start >= end) return;
	while (left <= right) {
		while (left <= end && v[left] <= v[pivot]) {
			left++;
		}
		while (right > start && v[right] >= v[pivot] ) {
			right--;
		}
		if (left > right) swap(v[pivot], v[right]);
		else swap(v[left], v[right]);
	}

	quickSort(v, start, right - 1);
	quickSort(v, right + 1, end);
}

삽입연산

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)