Chapter 5-4 : Tree (Binary Search Tree)

binary search tree는 우리가 이전에 배운 탐색 알고리즘을 용이하게 하기 위한 자료구조입니다.

각 root node의 왼쪽은 root node보다 작고 오른쪽은 root node보다 큰 수가 들어가게 되면서

어떤 수를 찾을 때 root node와 비교해주어 작으면 왼쪽으로가고 크면 오른쪽으로 가면서 탐색을하게 됩니다.

typedef struct node* tree_pointer;
typedef struct node {
	int data;
	tree_pointer left, right;
}node;

다음과 같은  tree 선언을 해줍니다.

---

Search (Recursive) 재귀함수

탐색과정을 재귀적으로 수행하는 방법입니다.

tree_pointer search(tree_pointer root, int key) {
	if (!root) return NULL;
	if (key == root->data) return root;
	if (key < root->data) //찾는 숫자가 root node보다 작을때
		return search(root->left, key);
	return search(root->right, key); //찾는 숫자가 root node보다 클때
}

---

Search (Iterative) 반복

탐색과정을 반복적으로 수행하는 방법입니다.

tree_pointer iter_search(tree_pointer tree, int key) {
	while (tree) {
		if (key == tree->data)return tree;
		if (key < tree->data)
			tree = tree->left;
		else
			tree = tree->right;
	}
	return NULL; //못찾았을떄
}

---

Inserting Into A Binary Search Tree (삽입)

먼저 새로운 node를 삽입하기 전에 기존에 tree에 해당 node가 중복되지 않은지 확인해야합니다.

void insert(tree_pointer* node, int num) {
	tree_pointer ptr, temp = modified_search(*node, num); //num이 기존tree에 있는지 확인
	if (temp || !(*node)) { 
		ptr = (tree_pointer)malloc(sizeof(node));
		if (IS_FULL(ptr)) {
			fprintf(stderr, "The memory is full");
			exif(1);
		}
		ptr->data = num;
		ptr->left = ptr->right = NULL;
		if (*node)
			if (num < temp->data)
				temp->left = ptr;
			else temp->right = ptr;
		else *node = ptr;
	}
}

modified_search는 num이 기존 tree에 있는지 확인하고 있으면 NULL을 반환하고, 그게 아니면 tree의 마지막 node pointer를 반환합니다.