[C언어로 쉽게 풀어쓴 자료구조] 13장 탐색 내용 정리

2023. 8. 20. 14:00

출처 : https://www.booksr.co.kr/product/9788970509716/

이진탐색

절반을 딱 잘라 탐색함 찾고자 하는 값이 더 크다 그러면 오른쪽으로 낮으면 왼쪽으로 (오름차순 기준)

34탐색 출처 ; https://devyul.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0C-%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89binary-search

이진탐색 알고리즘

int search_binary2(int key, int low, int high)
{
	int middle;

	while (low <= high) {       // 아직 숫자들이 남아 있으면
		middle = (low + high) / 2;
		if (key == list[middle])
			return middle;
		else if (key > list[middle])
			low = middle + 1;
		else
			high = middle - 1;
	}
	return -1;   // 발견되지 않음 
}

AVL 트리

출처 : https://slidesplayer.org/slide/16597706/

균형인수(balance factor) = (왼쪽 서브 트리의 높이 - 오른쪽 서브트리의 높이) -1 ~ 1 까지는 균형인수

2-3트리

1면 반드시 자식은 2개 O(log2n) 2면 반드시 자식은 3개 O(log3n)

2-3트리 알고리즘

Tree23Node *tree23_search(Tree23Node* root, int key)
{
	if (root == NULL)			// 트리가 비어 있으면
		return FALSE;
	else if (key == root->data)// 루트의 키==탐색키 
		return TRUE;
	else if (root->type == TWO_NODE) {  // 2-노드
		if (key < root->key)
			return tree23_search(root->left, key);
		else
			return tree23_search(root->right, key);
	}
	else {										// 3-노드
		if (key < root->key1)
			return tree23_search(root->left, key);
		else if (key > root->key2)
			return tree23_search(root->right, key);
		else
			return tree23_search(root->middle, key);
	}
}

2-3-4 트리