본문 바로가기
자료구조

[ 자료구조 ] 탐색 - 03 . 이진 탐색 트리

파울로 디발자 2023. 3. 7. 00:32

[ 이진 탐색 트리 ]

[ 이진 탐색 트리 ]

이진 탐색 트리 ( Binary Search Tree)는 이진 탐색을 위한 트리이자 , 탐색을 위한 이진트리이다 .

즉 , 이진 탐색 트리는 이진탐색을 위한 이진트리이다 .

 

[필요 이유]

이진 탐색은 데이터 집합이 배열인 경우에만 사용이 가능하기 때문이다 .

이진 탐색에는 다음이 조건이 필요하다

  1. 데이터 집합의 처음과 끝을 알아야 한다 .
  2. 순식간에 데이터 집합의 중앙 요소를 계산 할 수 있어야 한다 .
  3. 계산된 중앙요소에 즉시 접근이 가능해야 한다 .

ex) 링크드 리스트는 다음의 작업들이 불가하다 . 헤드와 테일 사이 중앙 요소를 알 수 없기 때문이다 .

 

=>따라서 , 이진탐색은 사전에 정의된 크기의 데이터 집합에 대해서만 사용이 가능하고 , 동적으로

크기가 달라지는 데이터 집합에는 적용이 불가하다 . 이를 해결하기 위한 자료구조가 이진 탐색 트리이다 .

 

[ 이진 탐색 트리의 구성]

이진 탐색 트리는 자식이 최대 두개뿐인 노드로 이루어진 이진트리이다 . 

또한 , 다음의 규칙을 따른다 .

"왼쪽 자식 노드는 나보다 작고 , 오른쪽 자식 노드는 나보다 크다 "

 

[ 이진 탐색 트리의 기본 연산 : 탐색 ]

[ 탐색 ]

이진 탐색을 위한 중요한 단서는 " 각 노드가 중앙 요소라는 점이다"

중앙 요소를 찾아 좌/우의 대소를 비교하여 탐색 범위를 정하고,또 다시 중앙 요소를 찾아 좌/우의 대소를 비교하는 과정은

배열의 이진 탐색과 다를 바가 없다 .

 

[ 탐색 : 코드로 구현 ]

BSTNode* BST_SearchNode(BSTNode* Tree , ElementType Target)
{
	if(Tree == NULL)
    return;
    
    if(Tree->Data == Target)
    	return Tree;
    
    //목표값이 현재 노드보다 크다면
    else if (Tree->Data < Target)
    	return BST_SearchNode(Tree->Right,Target);
    
    //목표값이 현재 노드보다 작다면
     else if (Tree->Data > Target)
    	return BST_SearchNode(Tree->Left,Target);

}

 

[ 이진 탐색 트리의 기본 연산 : 삽입 ]

[ 삽입 ]

이진 탐색 트리에서 노드의 삽입은 새 노드가 삽입될 곳을 이진 탐색으로 찾아야 한다 .

탐색을 수행하며 탐색 노드가 새 노드보다 크다면 왼쪽으로 , 작다면 오른쪽으로 이동해가며 , 해당 위치에 자식이 없다면 그곳이 새 노드의 자리이다 .

 

[ 삽입 : 코드로 구현 ]

void BST_InsertNode(BSTNode ** Tree , BSTNode * NewNode)
{
    //새 노드가 현재 노드보다 크다면
    if( (*Tree)->Data < NewNode->Data )
    {
    	//우측에 자식이 없다면 자식으로
    	if( (*Tree)->Right == NULL)
        (*Tree)->Right = NewNode;
        //있다면 자식에서 다시 삽입가능한지 확인
        else
        BST_InsertNode( &(*Tree)->Right , NewNode);      
    }
    //새 노드가 현재 노드보다 작다면
    else if( (*Tree)->Data > NewNode->Data )
    {
        //좌측에 자식이 없다면 자식으로
    	if( (*Tree)->Left == NULL)
        (*Tree)->Left = NewNode;
        //있다면 자식에서 다시 삽입가능한지 확인
        else
        BST_InsertNode( &(*Tree)->Left , NewNode);      
    }
}

 

[ 이진 탐색 트리의 기본 연산 : 삭제 ]

[ 삭제 ]

임의의 노드를 삭제하는 단계는 다음과 같다 .

 

1. 임의의 노드를 이진탐색으로 찾는다 .

2.노드를 트리에서 떼어낸다.

 

2-1 .만약 노드가 잎 노드라면 노드의 주소를 반환하여 끝낸다 .

 

2-2 .해당 노드가 자식 노드가 있다면

 

2-2-A . 양쪽 모두 자식 노드를 갖고 있는 경우

=>삭제된 노드의 오른쪽 하위 트리에서 가장 작은 값을 가진 노드를 삭제된 노드의 위치에 옮긴다

만약 자식이 있다면 (이때는 오른쪽 자식만 있음 : 최소값 노드니까 ! ) 해당 자식을 최소값 노드의 부모에 연결한다 .

 

2-3-B . 한쪽만 자식 노드를 가지고 있는 경우

=>삭제되는 노드의 자식을 삭제되는 노드의 부모에 연결한다 .

 

[ 삭제 : 코드로 구현 ]

BSTNode* BST_RemoveTree( BstNode* Tree , BSTNode* Parent , ElementType Target )
{
	BSTNode* Removed= NULL;
    
    if(Tree == NULL)
    	return;
    
    //탐색 : 타켓보다 트리가 크다면 왼쪽 탐색
    if(Tree - > Data > Target )
    Removed = BST_RemoveNode ( Tree - > Left, Tree , Target );
    
    //탐색 : 타겟보다 트리가 작다면 오른쪽 탐색
    else if(Tree - > Data < Target )
    Removed = BST_RemoveNode ( Tree - > Right, Tree , Target );
    
    //삭제 : 값을 찾은 경우
    else
    {
    	Removed = Tree ; 
        
        //경우 1 : 잎 노드일 경우
        if(Tree -> Left == NULL && Tree -> Right == NULL)
        {
        	//부모의 왼쪽 자식일 경우
        	if(Parent->Left == Tree)
            Parent -> Left = NULL;
            //부모의 오른쪽 자식일 경우
            else
            Parent -> Right = NULL;          
        }
        //자식이 있을경우
        else
        {
        	//경우 2 : 자식이 모두 있을 경우
        	if(Tree->Left!=NULL&&Tree->Right!=NULL)
            {
            	//오른쪽 자식의 최소값 노드를 찾는다 .
            	BSTNode* MinNode = BST_SerchMinNode(Tree->Right);
                //최소값 노드에 대한 뒤처리가 필요해서 (자식등..) 호출
                Removed = BST_ RemoveNode(Tree,NULL,MinNode->Data);
                //tree자리에 삽입
                Tree->Data = MinNode->Data;
            	
            }
            //경우 3 : 자식이 하나만 있을 경우
            else
            {
            	BSTNode* Temp = NULL;
                //왼쪽 자식이 있는 경우
                if(Tree ->Left !=NULL)
                	Temp = Tree->Left;
                //오른쪽 자식이 있는 경우
                else
                	Temp = Tree->Right;
                
                //트리가 부모의 왼쪽 자식일 경우
        		if(Parent->Left == Tree)
            	Parent -> Left = Temp;
            	//트리가 부모의 오른쪽 자식일 경우
            	else
            	Parent -> Right = Temp;        
            
            }
        }
    }
    
}

[ 이진 탐색 트리의 단점 ]

[ 삭제 ]

동적으로 크기가 증가하는 데이터 집합에 대해 잘 대처하며 속도 역시 훌륭하지만,

다음의 경우 검색 효율을 극단적으로 떨어뜨린다.

실제 데이터를 담는 경우 역시 위와 같이 성장할 확률이 높다

=>이를 해결하기 위해 레드 블랙 트리를 알아본다 .

 

[ 이진 탐색 트리 구현 ]

[ BST.h ]

#ifndef BST
#define BST

#include<stdio.h>
#include<stdlib.h>

typedef int ElementType;

typedef struct tagBSTNode
{
	tagBSTNode* Left;
	tagBSTNode* Right;

	ElementType Data;
}BSTNode;

//노드 생성
BSTNode* BST_CreateNode(ElementType NewData);
//노드 삭제
void BST_DestroyNode(BSTNode* Node);
//트리 삭제
void BST_DestroyTree(BSTNode* Tree);

//탐색
BSTNode* BST_SearchNode(BSTNode* Tree, ElementType Data);
//최소 노드의 탐색
BSTNode* BST_SearchMinNode(BSTNode* Tree);
//노드 삽입
void BST_InsertNode(BSTNode* Tree, BSTNode* NewNode);
//노드 제거
BSTNode* BST_RemoveNode(BSTNode* Tree, BSTNode* Parent, ElementType Target);
//출력
void BST_InOrederPrintTree(BSTNode* Tree);


#endif

[ BST.cpp ]

#include "BST.h"
//노드 생성
BSTNode* BST_CreateNode(ElementType NewData)
{
	BSTNode* NewNode = (BSTNode*) malloc(sizeof(BSTNode));
	NewNode->Left = NULL;
	NewNode->Right = NULL;
	NewNode->Data = NewData;
	return NewNode;
}
//노드 삭제
void BST_DestroyNode(BSTNode* Node)
{
	free(Node);
}

//트리 삭제
void BST_DestroyTree(BSTNode* Tree)
{
	if (Tree->Right != NULL)
		BST_DestroyTree(Tree->Right);
	if (Tree->Left != NULL)
		BST_DestroyTree(Tree->Left);

	Tree->Right = NULL;
	Tree->Left = NULL;

	BST_DestroyNode(Tree);
}

//탐색
BSTNode* BST_SearchNode(BSTNode* Tree, ElementType Data)
{
	if (Tree == NULL)
		return NULL;

	//타겟이 현재 트리보다 크다면
	if (Tree->Data < Data)
	{
		return BST_SearchNode(Tree->Right,Data);
	}
	//타겟이 현재 트리보다 작다면
	else if(Tree->Data > Data)
	{
		return BST_SearchNode(Tree->Left, Data);
	}
	//타겟을 찾았다면
	else
	{
		return Tree;
	}
}
//최소 노드의 탐색
BSTNode* BST_SearchMinNode(BSTNode* Tree)
{
	if (Tree == NULL)
		return NULL;

	if (Tree->Left == NULL)
		return Tree;
	else
		BST_SearchMinNode(Tree->Left);
}
//노드 삽입
void BST_InsertNode(BSTNode* Tree, BSTNode* NewNode)
{
	//새 노드의 데이터가 트리의 데이터 보다 크다면
	if (Tree->Data < NewNode->Data)
	{
		if (Tree->Right == NULL)
			Tree->Right = NewNode;
		else
			BST_InsertNode(Tree->Right, NewNode);
	}
	//새 노드의 데이터가 트리의 데이터 보다 작다면
	else
	{
		if (Tree->Left == NULL)
			Tree->Left = NewNode;
		else
			BST_InsertNode(Tree->Left, NewNode);
	}
}
//노드 제거
BSTNode* BST_RemoveNode(BSTNode* Tree, BSTNode* Parent, ElementType Target)
{
	BSTNode* Removed = NULL;
	if (Tree == NULL)
		return NULL;

	//타겟이 더 크다면
	if (Tree->Data < Target)
	{
		Removed = BST_RemoveNode(Tree->Right,Tree,Target);
	}
	//타겟이 더 작다면
	else if (Tree->Data > Target)
	{
		Removed = BST_RemoveNode(Tree->Left, Tree, Target);
	}
	//타겟을 찾았다면
	else
	{
		Removed = Tree;

		//잎노드라면
		if (Tree->Right == NULL && Tree->Left && NULL)
		{
			//오른쪽 자식 노드였다면
			if (Parent->Right == Tree)
				Parent->Right = NULL;
			//왼쪽 자식 노드였다면
			else
				Parent->Left = NULL;
		}
		//자식이 있다면
		else
		{
			//자식이 둘 다 있다면
			if (Tree->Right != NULL && Tree->Left != NULL)
			{
				//최소값 노드를 찾아 제거
				BSTNode* MinNode = BST_SearchMinNode(Tree->Right);
				BST_RemoveNode(Tree, NULL, MinNode->Data);
				Tree->Data = MinNode->Data;
			}
			//홀 자식이라면
			else
			{
				BSTNode* Temp = NULL;
				//오른쪽 자식이 있다면
				if (Tree->Right != NULL)
					Temp = Tree->Right;
				//왼쪽 자식이 있다면
				else
					Temp = Tree->Left;

				//오른쪽 자식 노드였다면
				if (Parent->Right == Tree)
					Parent->Right = Temp;
				//왼쪽 자식 노드였다면
				else
					Parent->Left = Temp;
			}
		}
	}
	return Removed;
}
//중위 출력
void BST_InOrederPrintTree(BSTNode* Tree)
{
	if (Tree == NULL)
		return;

	BST_InOrederPrintTree(Tree->Left);
	printf("%d\t", Tree->Data);
	BST_InOrederPrintTree(Tree->Right);
}

[ Test.cpp ]

#include"BST.h"
int main(void)
{
	//노드 생성
	BSTNode* Tree = BST_CreateNode(123);
	BSTNode* Node = NULL;

	//트리에 노드 추가
	BST_InsertNode(Tree, BST_CreateNode(22));
	BST_InsertNode(Tree, BST_CreateNode(9918));
	BST_InsertNode(Tree, BST_CreateNode(424));
	BST_InsertNode(Tree, BST_CreateNode(17));
	BST_InsertNode(Tree, BST_CreateNode(3));

	BST_InsertNode(Tree, BST_CreateNode(98));
	BST_InsertNode(Tree, BST_CreateNode(34));

	BST_InsertNode(Tree, BST_CreateNode(760));
	BST_InsertNode(Tree, BST_CreateNode(317));
	BST_InsertNode(Tree, BST_CreateNode(1));

	//트리 출력
	BST_InOrederPrintTree(Tree);
	printf("\n");

	//특정 노드 삭제
	printf("Removing 98 \n");
	Node = BST_RemoveNode(Tree, NULL, 98);
	BST_DestroyNode(Node);

	//트리 출력
	BST_InOrederPrintTree(Tree);
	printf("\n");

	//새 노드 삽입
	printf("Inserting 111 \n");
	BST_InsertNode(Tree, BST_CreateNode(111));

	//트리 출력
	BST_InOrederPrintTree(Tree);
	printf("\n");

	//트리 소멸
	BST_DestroyTree(Tree);
	return 0;
}

 

'자료구조' 카테고리의 다른 글

[ 자료구조 ] 탐색 - 04 - 2 . 레드 블랙 트리 <삭제>  (0) 2023.03.10
[ 자료구조 ] 탐색 - 04 - 1 . 레드 블랙 트리 <회전 , 삽입>  (0) 2023.03.07
[ 자료구조 ] 탐색 - 02 . 이진탐색  (0) 2023.03.03
[ 자료구조 ] 탐색 - 01 . 순차탐색  (0) 2023.03.02
[ 자료구조 ] 정렬 - 05 . qsort  (0) 2023.02.18

'자료구조' Related Articles

티스토리툴바