C로 만드는 자료구조 - 연결 리스트로 구현한 이진 탐색 트리(Binary Search Tree)

dsbook.tistory.com/270

C로 만드는 자료구조 - 이진 탐색 트리(Binary Search Tree)

이진 탐색 트리 (Binary Search Tree)란? 이진 탐색 트리는 이진 트리에서 탐색(Search)란 단어가 들어가 있다. 탐색이 뜻하는 바와 같이 이진 트리에서 '자료의 검색'이 주된 기능이 된다. 이진 탐색 트

dsbook.tistory.com

연결 리스트를 이용한 이진 탐색 트리 구현

소스 파일 구성은 다음과 같다.

파일 이름	내용
binsearchtree.h	구조체 및 함수 선언
binsearchtree.cpp	함수 구현
binsearchtreemain.cpp	main 함수 실행

1.binsearchtree.h

구현하기 앞서 힙의 추상자료형을 다시 한번 보자

이름		입력	출력	설명
이진 탐색 트리 생성	createBST()		이진탐색트리 T	이진 탐색 트리 T 생성
이진 탐색 트리 삭제	deleteBST()	이진탐색트리 T	N/A	이진 탐색 트리 T 메모리 해제
노드 추가	inseertBSTNode()	이진탐색트리 T 원소 e	성공/실패 여부	이진 탐색 트리에 새로운 원소 추가
노드 제거/반환	deleteBSTNode()	이진탐색트리 T 값 k		이진 탐색 트리에 값 k를 제거
검색	search()	이진탐색트리 T 값 k		이진 탐색 트리의 노드중 k와 같은 값을 가지는 노드 반환

코드 구현은 다음과 같다.

#pragma once
#include<iostream>
using namespace std;

#define TRUE 1
#define FALSE 0

struct BSTNode {
	int key; // 값

	struct BSTNode* pLeftChild; 
	struct BSTNode* pRightChild;
};
struct BST {
	BSTNode* pRoot;
};

BST* crateBST(); // 트리 생성
int insertBSTNode(BST* pTree, BSTNode element);// 노드 추가
int deleteBSTNode(BST* pTree, int key);// 노드 삭제
BSTNode* search(BST* pTree, int key); // 탐색 연산

void deleteBST(BST* pTree);
void deleteBSTInternal(BSTNode* pTreeNode);

2.binsearchtree.cpp

- createBST()

BST* crateBST() {
	BST* pReturn = NULL;
	pReturn = (BST*)malloc(sizeof(BST));

	if (pReturn != NULL) {
		pReturn->pRoot = NULL;
	}
	return pReturn;
}

이진 탐색 트리를 생성하는 함수이다. 간단하게 메모리만 할당해주면 된다.

- insertBSTNode()

삽입 연산은 크게 2단계로 이루어진다.

1단계: 새로운 노드를 추가 할 위치를 찾음
2단계: 새로운 노드를 추가하고 링크 재설정

int insertBSTNode(BST* pTree, BSTNode element) {
	int ret = TRUE;
	BSTNode *pParentNode = NULL;
	BSTNode *pNewNode = NULL;

	if (pTree == NULL) {
		ret = FALSE;
		return ret;
	}
     // 삽입할 위치 찾기
	pParentNode = pTree->pRoot;
	while (pParentNode != NULL) {
		if (element.key == pParentNode->key) { // 입력받은 키와 현재 노드의 값이 같은경우
			printf("중복된 키 입니다 - [%d]\n", element.key);
			ret = FALSE;
			return ret;
		}
		else if (element.key < pParentNode->key) { // 입력받은 키가 현재 노드의 값보다 작을 경우
			if (pParentNode->pLeftChild == NULL) {
				break;	// 삽입할 위치 발견
			}
			else {
				pParentNode = pParentNode->pLeftChild; // 왼쪽 서브트리로 이동
			}
		}
		else {// 입력받은 키가 현재 노드의 값보다 클 경우
			if (pParentNode->pRightChild == NULL) {
				break;	// 삽입할 위치 발견
			}
			else {
				pParentNode = pParentNode->pRightChild; // 오른쪽 서브트리로 이동
			}
		}
	}
   
   // 새로운 노드 삽입 후 링크 재설정
	pNewNode = (BSTNode *)malloc(sizeof(BSTNode));
	if (pNewNode != NULL) {
		*pNewNode = element;
		pNewNode->pLeftChild = NULL;
		pNewNode->pRightChild = NULL;

		if (pParentNode == NULL) { // 루트노드가 NULL인 경우 입력 값이 새로운 루트노드가 됨
			pTree->pRoot = pNewNode;
		}
		else {
			if (pNewNode->key < pParentNode->key) {  // 입력 값이 부모 노드의 값보다 작다면 왼쪽 서브트리로
				pParentNode->pLeftChild = pNewNode;
			}
			else { // 입력 값이 부모 노드의 값보다 크다면 오른쪽 서브트리로
				pParentNode->pRightChild = pNewNode;
			}
		}
		ret = TRUE;
	}
	else {
		printf("메모리 할당 오류\n");
		ret = FALSE;
	}
	
	return ret;
}

1단계: 새로운 노드를 추가 할 위치를 찾음

while문과 탐색 연산을 활용하여 삽입할 위치를 찾아 주었다. 방문한 노드의 값과 새로운 노드의 값을 비교하여 만약 같은 값이 존재한다면 즉시 오류 메세지 출력과 함께 함수를 중단 시켜주고 입력값이 더 크면 오른쪽 서브트리로 더 작으면 왼쪽 서브트리로 NULL값을 만날 때 까지 이동 시켜 적절한 빈 공간을 찾는다. 이때 우리가 저장하는 노드는 NULL값을 가지느 노드의 부모 노드이다.

2단계: 새로운 노드를 추가하고 링크 재설정

1단계에서 찾은 부모 노드와 새로운 노드에 메모리를 할당하고 값을 비교하여 적절한 곳에 삽입 및 연결 시켜준다.

- deleteBSTNode()

삭제 연산은 크게 2단계로 이루어진다.

1단계: 삭제 대상 노드 찾음
2단계: 삭제 대상 노드 삭제 후 부모 노드와 링크 재서정

int deleteBSTNode(BST* pTree, int key) {
	int ret = TRUE;
	BSTNode* pDelNode = NULL;
	BSTNode* pParentNode = NULL;
	BSTNode* pPredecessor = NULL;
	BSTNode* pSuccessor = NULL;
	BSTNode* pChildNode = NULL;

	// 삭제 대상 노드를 찾는 부분
	if (pTree == NULL) {
		ret = FALSE;
		return ret;
	}
	pParentNode = NULL;
	pDelNode = pTree->pRoot;
	while (pDelNode != NULL) {
		if (key == pDelNode->key) {
			break;
		}
		pParentNode = pDelNode;
		if (key < pDelNode->key) {
			pDelNode = pDelNode->pLeftChild;
		}
		else {
			pDelNode = pDelNode->pRightChild;
		}
	}
	if (pDelNode == NULL) {
		printf("존재하지 않는 키 입니다 - [%d]\n", key);
		ret = FALSE;
		return ret;
	}

	// 삭제 대상 노드 삭제 연산 부분
    // 자식 노드가 없을때
	if (pDelNode->pLeftChild == NULL && pDelNode->pRightChild == NULL) { // 해당 노드의 서브트리가 존재하지 않을 경우
		if (pParentNode != NULL) {
			if (pParentNode->pLeftChild == pDelNode) {
				pParentNode->pLeftChild = NULL;
			}
			else {
				pParentNode->pRightChild = NULL;
			}
		}
		else {
			pTree->pRoot = NULL;
		}
	}
    // 자식노드가 2개일때
	else if (pDelNode->pLeftChild != NULL && pDelNode->pRightChild != NULL) { // 해당 노드의 자식 노드가 2개인 경우
		pPredecessor = pDelNode;
		pSuccessor = pDelNode->pLeftChild;
		
		// 왼쪽 서브트리에서 가장 큰 값 찾기 
		while (pSuccessor->pRightChild != NULL) {
			pPredecessor = pSuccessor;
			pSuccessor = pSuccessor->pRightChild;
		}
		pPredecessor->pRightChild = pSuccessor->pLeftChild;
		pSuccessor->pLeftChild = pDelNode->pLeftChild;
		pSuccessor->pRightChild = pDelNode->pRightChild;

		if (pParentNode!= NULL) {
			if (pParentNode->pLeftChild = pDelNode) {
				pParentNode->pLeftChild = pSuccessor;
			}
			else {
				pParentNode->pRightChild = pSuccessor;
			}
		}
		else {
			pTree->pRoot = pSuccessor;
		}
	}

	else {// 해당 노드의 자식 노드가 1개인 경우
		if (pDelNode->pLeftChild != NULL) {
			pChildNode = pDelNode->pLeftChild;
		}
		else {
			pChildNode = pDelNode->pRightChild;
		}
		if (pParentNode != NULL) {
			if (pParentNode->pLeftChild == pDelNode) {
				pParentNode->pLeftChild = pChildNode;
			}
			else {
				pParentNode->pRightChild = pChildNode;
			}
		}
		else {
			pTree->pRoot = pChildNode;
		}
	}
	free(pDelNode);
	return ret;
}

1단계: 삭제 대상 노드 찾음

삭제 대상 노드를 찾는 것은 삽입 연산때와 마찬가지로 while문과 탐색 연산 방식을 사용한다. 방문한 노드와 값 비교를 통해 왼쪽 또는 오른쪽 서브트리를 이동하면서 입력값과 방문한 노드의 값이 일치할 때까지 반복한다. 이때 삭제할 노드는 pDelNode에 저장한다. 이때 pParentNode에는 pDelNode의 부모 노드를 저장한다.

2단계: 삭제 대상 노드 삭제 후 부모 노드와 링크 재설정

삭제 대상 노드를 찾고 나서는 삭제 대상 노드의 부모 노드와 자식 노드의 링크 재설정이 필요하고 3가지 경우로 나누어서 처리한다.

1) 자식 노드가 없는 경우
자식 노드가 없는 경우는 단순히 1단계에서 저장한 부모 노드와 삭제할 노드의 연결을 제거해주면 된다.

2) 자식 노드가 2개인 경우
자식 노드가 2개인 경우는 왼쪽 서브트리에서 가장 큰값을 가지는 노드 또는 오른쪽 서브트리에서 가장 작은 값을 가지는 노드를 찾고 삭제할 노드의 위치로 이동 시켜주어야 한다. 위 코드는 왼쪽 서브트리에서 가장 큰 값을 가지는 노드를 찾고 위치를 바꾸어 주었다.

3) 자식 노드가 1개인 경우
자식 노드가 1개인 경우 삭제할 노드의 자식 노드를 삭제할 노드의 위치로 이동 시켜주면 된다.

- search()

이진 탐색 트리의 주 목적인 탐색 연산이다. 앞서 설명한 삽입 연산, 삭제 연산에서 탐색 할때 사용된 코드와 거의 비슷하다.

BSTNode* search(BST* pTree, int key) {
	BSTNode* pReturn = NULL;
	if (pTree == NULL) {
		return NULL;
	}
	pReturn = pTree->pRoot;
	while (pReturn != NULL) {
		if (key == pReturn->key) {
			break;
		}
		else if (key < pReturn->key) {
			pReturn = pReturn->pLeftChild;
		}
		else {
			pReturn = pReturn->pRightChild;
		}
	}
	return pReturn;
}

- deleteBST()

void deleteBST(BST* pTree) {
	deleteBSTInternal(pTree->pRoot);
}
void deleteBSTInternal(BSTNode* pTreeNode) {
	deleteBSTInternal(pTreeNode->pLeftChild);
	deleteBSTInternal(pTreeNode->pRightChild);
	free(pTreeNode);
}

연결 리스트의 메모리를 차례대로 해제 시켜 준다.

3.binarysearchmain.cpp

실제로 이진 탐색 트리를 만들고 여러가지 연산을 실행해 보았다.

#include "binsearchtree.h"

void displayBinSearchTreeInternal(BSTNode* pTreeNode, int level, char type) {
    int i = 0;
    for (i = 0; i < level; i++) {
        printf("    ");
    }
    if (pTreeNode != NULL) {
        printf("-[%i,%c]%i\n", level, type,
            pTreeNode->key);
        displayBinSearchTreeInternal(pTreeNode->pLeftChild, level + 1, 'L');
        displayBinSearchTreeInternal(pTreeNode->pRightChild, level + 1, 'R');
    }
    else {
        printf("NULL\n");
    }
}

int main() {
    BST* pTree = NULL;
    BSTNode* pSearchNode = NULL;
    int key = 0;

    BSTNode e1 = { 30 };
    BSTNode e2 = { 20 };
    BSTNode e3 = { 40 };
    BSTNode e4 = { 10 };
    BSTNode e5 = { 24 };
    BSTNode e6 = { 34 };
    BSTNode e7 = { 46 };
    BSTNode e8 = { 6 };
    BSTNode e9 = { 14 };
    BSTNode e10 = { 22 };
    BSTNode e11 = { 50 };
    BSTNode e12 = { 2 };
    BSTNode e13 = { 38 };
  

    pTree = crateBST();
    if (pTree != NULL)
    {
        insertBSTNode(pTree, e1);
        insertBSTNode(pTree, e2);
        insertBSTNode(pTree, e3);
        insertBSTNode(pTree, e4);
        insertBSTNode(pTree, e5);
        insertBSTNode(pTree, e6);
        insertBSTNode(pTree, e7);
        insertBSTNode(pTree, e8);
        insertBSTNode(pTree, e9);
        insertBSTNode(pTree, e10);
        insertBSTNode(pTree, e11);
        insertBSTNode(pTree, e12);
        insertBSTNode(pTree, e13);
        displayBinSearchTreeInternal(pTree->pRoot, 0, 'O');


        key = 14;
        pSearchNode = search(pTree, key);
        if (pSearchNode != NULL) {
            printf("key : [%d]\n", key);
        }

        key = 30;
        deleteBSTNode(pTree, key);
        displayBinSearchTreeInternal(pTree->pRoot, 0, 'O');

        key = 46;
        deleteBSTNode(pTree, key);
        displayBinSearchTreeInternal(pTree->pRoot, 0, 'O');

        key = 40;
        deleteBSTNode(pTree, key);
        displayBinSearchTreeInternal(pTree->pRoot, 0, 'O');
        deleteBST(pTree);
    }

    return 0;
}

728x90

저작자표시 비영리

'컴퓨터 공학 > 자료구조' 카테고리의 다른 글

C로 만드는 자료구조 - 여러가지 그래프 (0)	2021.03.01
C로 만드는 자료구조 - 그래프(Graph)란? (0)	2021.02.28
C로 만드는 자료구조 - 이진 탐색 트리(Binary Search Tree) (0)	2021.02.17
C로 만드는 자료구조- 배열로 구현하는 힙(Heap) (0)	2021.02.03
C로 만드는 자료구조- 힙(Heap)이란? (0)	2021.02.03