재시민

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)

음수에는 사용 불가능

void countSort(vector<int>& v, int n) {
	vector<int> count(30, 0);// count 초기화
	int i;
	for (i = 0;i < n;i++) {
		count[v[i]]++;
	}
	for (i = 0;i < 30;i++) {
		for (int j = 0;j < count[i];j++) {
			printf("%d ", i);
		}
	}
}

제자리성 : 제자리 x

안정성 : 안정

(순서대로 배치)

시간 복잡도

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

알고리즘 

1. count 배열 초기화

2. 배열을 순회하여 배열의 인덱스 값에 해당하는 count index 에 ++

3. 이중 반복문 사용하여 count에 할당된 값만큼 index 값 출력

특정 배열에 대해 아주 빠르지만 count 에 할당되는 index 가 커지면 커질 수록 메모리 낭비가 매우심함