이진탐색트리 Search 후 remove 구현

이진 탐색트리 삭제를 구현해보자

 

이진 탐색트리에서 search후 삭제를 할 때 다음 같은 상황이 있다.

 

1. 삭제할 노드의 자식 노드가 left 노드만 존재하는 경우

 

2. 삭제할 노드의 자식 노드가 right 노드만 존재 하는 경우

 

3. 삭제할 노드의 자식 노드가 양쪽 노드가 모두 존재하는 경우

 

4. 삭제할 노드의 자식 노드가 없는 경우

 

 

1. 삭제할 노드의 자식 노드가 left 노드만 존재하는 경우

 

위 그림에서 4의 자식노드는 left 노드만 있으므로 4를 삭제한다고 해보자 

 

쉽게 판단 할 수 있듯이 4의 자식 노드를 8의 자식노드에 붙여 주면 끝이다.

 

4 노드를 삭제 후 8의 자식노드를 2에 연결 해주면 끝~!!!

 

 

2. 삭제할 노드의 자식 노드가 right 노드만 존재 하는 경우

 

삭제할 노드의 자식노드가 right 노드만 있는 경우도 1번과 방식이 똑같다.

 

어차피 노드는 하나이므로 위 루틴과 동일하게 타면 크게 문제 없다.

 

3. 삭제할 노드의 자식노드가 둘다 존재 하는 경우

 

삭제할 노드의 자식노드가 둘다 존재하는 경우의 삭제 방법은 크게 두가지가 방법이 있다.

(단 위 방법은 정렬할 때 조건이 https://kjt9109.tistory.com/entry/이진탐색트리-Insert-Search-구현 의 2, 3번을 만족하여 정렬했다는 가정하에서만 만족한다.)

 

3-1. 삭제할 노드의 왼쪽 노드를 타고 들어가 가장 큰 수를 찾아 대체한다!!

3-2. 삭제할 노드의 오른쪽 노드를 타고 들어가 가장 작은 수를 찾아 대체한다!!

 

 

3-1 방법으로 아래 그림의 노드 8을 삭제한다고 가정해보자

3-A 삭제할 노드의 왼쪽 노드에서 가장 큰 수를 찾는다. (가장 큰 수는 4이다)

 

3-B 삭제할 노드(8)의 값을 이전에 찾은 가장 큰 수(4)로 대체하고 만약 4의 자식노드 왼쪽이 있는 경우 연결한다.

 

3-B의 노드에서 3-A의 왼쪽 자식 노드가 있는 경우 연결하면 되고 오른쪽 노드는 볼 필요가 없다.

왜냐하면 오른쪽 노드가 있는 경우 4가 가장 큰 수가 될수 없기 때문이다.

 

3-2의 방법도 위 루틴과 똑같으므로 언급을 하지 않겠다.

 

이제 코드로 구현해보자

 

Delete를 구현 한 함수는 다음과 같다.

 

BTreeDelete()

BTData BTreeDelete(BTreeNode *root, BTData findData)
{
    TR_FUNC(TRACE);

    BTreeNode *_local_pNode = root;
    BTreeNode *_local_findNode = NULL;

    /* == Find Data == */
    if((_local_findNode = _BTreeSearchWithPNode(&_local_pNode, findData)) == NULL) {
	printf("BTree Search No Data #2\r\n");
	return 0xdeadbeef;
    }
    /* == Delete Data == */
    else {
	int check = _checkChildNode(*_local_findNode);

	if (check < 0) {
	    printf(" BTreeDelete ERROR \r\n");
	}
	/* == 삭제 할 노드의 자식 노드가 left만 있을 때 == */
	else if (check == LEFTONENODE) {
	    _local_pNode->left = _local_findNode->left;
	    if (!(DeleteTree(_local_findNode) < 0)) {
		printf(" Delete Sucess !! (left one Node) \r\n");
	    }
	}
	/* == 삭제 할 노드의 자식 노드가 right만 있을 때 == */
	else if (check == RIGHTONENODE) {
	    _local_pNode->right = _local_findNode->right;
	    if (!(DeleteTree(_local_findNode) < 0)) {
		printf(" Delete Sucess !! (right one Node) \r\n");
	    }
	}
	/* == 삭제 할 노드의 자식 노드가 둘다 있을 때 == */
	else if (check == TWONODE) {
	    BTreeNode *_largeNode = findLargeValueTree(_local_findNode->left); 
	    /* == largeNode의rightNode가 있을 순 없다 (더 큰수 이기 때문에) == */
	    if (_largeNode->left) {
		_local_findNode->left = _largeNode->left;
		_largeNode->left = NULL;
	    }	

	    _local_findNode->data = _largeNode->data;
	    if (!(DeleteTree(_largeNode) < 0)) {
		printf(" Delete Sucess !! (Two Node) \r\n");
	    }
	}
	else if (check == NONODE) {
	    if (!(DeleteTree(_local_findNode) < 0)) {
		printf(" Delete Sucess !! (No Node) \r\n");
	    }
	}
    }

    return 0xdeadbeef;
}

BTreeDelete함수의 Arg로 root 노드와 삭제하고자 하는 데이터를 넣는다.

 

삭제하고자 하는 데이터의 노드와 그 노드의 부모노드를 찾는다. 찾고자 하는 노드가 존재하지 않으면 Error를 Print하고 return 한다.

 

삭제하는 노드의 자식노드를 검사하여 자식 노드가 없느냐, 하나만 있느냐(left or right), 둘 다 존재 하느냐에 따른 상황에 맞게 동작한다.

 

다음은 삭제하고자 하는 데이터노드와 부모노드를 찾는 함수이다.

 

_BTreeSearchWithPNode()

static BTreeNode *_BTreeSearchWithPNode(BTreeNode **pNode, BTData findData)
{
    TR_FUNC(TRACE);

    BTreeNode *_local_parent_node = *pNode;

    if (GetData(GetLeftSubTree(_local_parent_node)) == findData)
	return GetLeftSubTree(_local_parent_node);

    else if (GetData(GetRightSubTree(_local_parent_node)) == findData)
	return GetRightSubTree(_local_parent_node);

    else if (((*pNode = GetLeftSubTree(_local_parent_node)) != NULL) && (findData < GetData(_local_parent_node)))
	return _BTreeSearchWithPNode(pNode, findData);

    else if (((*pNode = GetRightSubTree(_local_parent_node)) != NULL) && (findData > GetData(_local_parent_node)))
	return _BTreeSearchWithPNode(pNode, findData);

    printf("BTree Search No Data #1\r\n");
    return NULL;
}

찾고자 하는 데이터 및 부모 노드를 찾는 함수는 재귀함수를 활용하였다.

 

현 노드의 왼쪽 노드가 찾는 노드인 경우 리턴 or 오른쪽 노드가 찾는 경우 리턴하지만 둘 다 없는 경우는 다음 루틴을 탄다,

 

왼쪽 자식 노드가 있는 지 체크후 찾고자 하는 데이터가 왼쪽 자식 노드보다 작은 경우 parent Node의 포인터변수를 왼쪽 자식 노드로 변경하여 다시 자기 함수로 들어간다.

 

만약 작지 않는 경우 오른쪽 자식 노드가 있는지 체크하고 오른쪽 자식 노드가 있는지 체크하고 찾는 데이터 값이 오른쪽 자식 노드 데이터 값보다 큰 경우 parent Node의 포인터 변수를 왼쪽 자식 노드로 변경하여 다시 자기 함수로 들어간다.

 

만약 위 조건을 만족하지 않는 경우 데이터가 없는 경우이므로 Error를 Print하고 Return한다.

 

나머지 함수들은 간단하므로 다음 링크를 코드를 보면 쉽게 알 수있다.

https://github.com/KJT9109/Data_Structure/blob/master/Binary_Tree/BinaryTree.c

 

다음 실행 및 lldb를 통해 정상적으로 삭제 되었음을 확인하였다.