재시민

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 heapify(vector<int>& v, int size, int i) {
	int c = 2 * i + 1; // 왼쪽자식 선택
	if (c < size - 1 && v[c] < v[c + 1]) c++; //오른쪽자식 존재하면서, 오른쪽자식이 더크면 오른쪽 자식 선택
	if (c < size && v[i] < v[c]) swap(v[i], v[c]); // 부모보다 자식이 더크면 둘이 바꿈
	if (c < size / 2) heapify(v, size, c); //내부노드에서 한정하여 반복
}

void heapSort(vector<int>& v, int size) {
	for (int i = size / 2;i >= 0;i--) {
		heapify(v, size, i);
	}
	for (int i = size - 1;i >= 0;i--) {
		swap(v[i], v[0]);//힙이 만들어지고 맨처음값과 맨 뒷 값 변경
		heapify(v, i, 0);// 사이즈 조절 후 
	}
}

제자리성 : 제자리 정렬

시간복잡도

최악시간 복잡도 = O(nlogn) (완전 이진트리)

알고리즘

1. 전체 이진트리로 만들기

2. 서브트리마다 최대 힙구조로 만들기

3. 맨 첫번째 원소와 마지막 원소를 스왑

4. 위의 과정 반복