[자료구조] 이진탐색트리(BinarySearchTree)

[Insert]

특정 노드 값보다 작으면 left로 크면 right로 떨어진다.

낙수효과 생각하면 된다. 자기 자리 찾을때까지 left or right로 떨어지는 것이다.

그래서 무조건 leaf node로 배치된다.

 

---

[Delete]

삭제 과정이 좀 골치아픈데 케이스를 나눠보면 된다.

 

삭제할 노드가 delNode이고 이 노드를 찾았다고 할때 케이스가 다음과 같이 나눠진다.

 

1) leaf node 일때2) 자식이 한 명일때3) 자식이 두 명 일때

 

그리고 자식이 두 명일때는 자신의 밑에 있는 놈들 중 어떤 자식을 내가 빠진 자리에 배치할 것인가를 선택해야한다.그 방법으로는 두 가지가 있다

 

1) delNode의 오른쪽 브랜치에서 맨 왼쪽 끝에 있는 leaf node(나보다 큰 놈 중에 제일 작은 놈)2) delNode의 왼쪽 브랜치에서 맨 오른쪽 끝에 있는 leaf node

 

---

[이진탐색트리의 Insert와 Search 과정]

이진탐색트리를 구현할때는 Insert와 Search 코드가 복잡하지 않다.
삽입과 탐색 과정 자체가 ㅈㄴ 단순하기 때문이다.

이진 "탐색" 트리는 heap(우선순위큐 구현 때 쓴 트리구조)처럼
새 데이터가 추가될때마다 재배치과정이 필요없기 때문이다.
(같은 트리구조라 해도 목적 자체가 다르기 때문)

 

---

[BSTInsert]

사실 이 함수는 별게 없다 ( 참고할 함수들은 맨아래 적어놨다 )
이진탐색트리에서는 노드를 추가하면 무조건 단말에 추가되기 때문이다

상술했듯이 heap 같이 새로운 데이터가 추가되었다고 해서
모든 노드들을 재배치하거나 이진트리 구조를 바꿀 필요가 없다.

그냥 삽입규칙에 맞게 내려가다
단말노드에 새로운 데이터를 추가해주면 된다.

 

void BSTInsert(BTreeNode** pRoot, BSTData data) {
	// 제자리를 찾기위해 사용하는 임시포인터
	BTreeNode* temp=*pRoot;
	// 부모포인터
	BTreeNode* pnode = NULL;

	// 저장할 위치 파악하기
	// 저장 위치의 pnode 찾기
	while (temp != NULL) {
		pnode = temp;
		if (data == GetData(temp)) return;
		if (data < GetData(temp)) temp = GetLeftSubTree(temp);
		else temp = GetRightSubTree(temp);
	}
    
	// 새 노드 생성
	BTreeNode* newnode = MakeBTreeNode();
	SetData(newnode, data);
	
    // pnode에 새 노드 연결시켜주기
	// 루트노드가 아니라면
	if (pnode != NULL) {
		if (data < GetData(pnode)) MakeLeftSubTree(pnode,newnode);
		else MakeRightSubTree(pnode, newnode);
	}
	// 루트노드이면
	else {
		*pRoot = temp;
	}
}

여기서 주의깊게 봐야하는 점은
함수인자를 더블포인터로 받았다는 것인데
이는 Insert 함수 내에서 main함수에 있는 bstRoot 변수를 참조하기 위함이다.

외부 변수를 참조( 함수 -> main )하기 위해서 포인터를 쓰는데

main함수 내의 bstRoot 변수가 (BTreeNode*)형 이므로
Insert 함수는 BTreeNode** 형으로 받아 참조해야하는 것이다.

그림으로 보면 다음과 같다.

 

데이터가 없을때 / bstRoot가 NULL일때

 

데이터가 존재할때 / bstRoot가 주소값일때

마지막 if 문에서는 루트노드일때와 아닐때를 구별하여 작성했다.

 

---

[BSTSearch]

탐색코드는 Insert보다 쉽다.

BTreeNode* BSTSearch(BTreeNode* bst, BSTData target) {
	while (bst != NULL) {
		if (target == GetData(bst)) return bst;
		else if (target < GetData(bst)) bst = GetLeftSubTree(bst);
		else bst = GetRightSubTree(bst);
	}
	return NULL;
}

 

---

[참고할 함수들 (전에 정의해놓음)]

void BSTMakeAndInit(BTreeNode** pRoot) { *pRoot = NULL; }

BSTData GetData(BTreeNode* bt) { return bt->data; }

BTreeNode* MakeBTreeNode(void) { 
	BTreeNode* node = (BTreeNode*)malloc(sizeof(BTreeNode)); 
	node->left = NULL;
	node->right = NULL;
	return node;
}

 

---

[main]

int main() {
	BTreeNode* bstRoot;
	BSTMakeAndInit(&bstRoot);
	BSTInsert(&bstRoot, 5);
	BSTSearch(&bstRoot, 5) != NULL ? printf("1") : printf("0");
}