[자료구조] 이진 탐색 트리(Binary Search Tree)

이진 탐색 트리란?

'이진 탐색'을 위한 트리이자 탐색을 위한 '이진 트리'입니다. 다시 말해 이진 탐색 트리는 '이진 탐색'을 위한 '이진 트리'입니다.

앞 서 배운 이진 탐색으로는 배열에만 사용 가능한 알고리즘입니다. 데이터의 처음과 끝을 알아야 하고 순식간에 데이터의 중앙 요소를 계산할 수 있어야 하며 중앙 요소에 접근 할 수 있어야 합니다.

하지만 링크드 리스트는 위와 같은 작업들이 불가능한 자료구조입니다. 헤드와 테일 사이의 '중앙 요소'는 알 수 없기 때문입니다. 

이러한 문제를 해결하여 링크드 리스트처럼 동적으로 노드를 추가하거나 제거할 수 있으면서 이진 탐색 알고리즘도 사용할 수 있도록 하는 자료구조가 바로 '이진 탐색 트리' 입니다.

 

이진 탐색 트리의 표현은 생각보다 간단합니다. 이진 트리는 자식이 최대 2개뿐인 노드로만 이루어진 트리이기때문에 각 노드가 다음 규칙을 따른다면 이진 탐색 트리의 조건을 만족하는 것입니다.

왼쪽 자식 노드는 나보다 작고 오른쪽 자식 노드는 나보다 크다 즉 각 노드가 중앙 요소, 자식 노드가 각각 중앙 요소 기준 왼쪽, 오른쪽이 되는 것입니다.

---

이진 탐색 트리의 기본 연산과 구현

배열이 정렬되어 있어야 이진 탐색이 가능한 것처럼, 이진 탐색 트리도 이진 탐색이 가능한 상태로 정렬되어 있어야 합니다.

따라서 이진 탐색 트리는 삽입과 삭제가 이루어 질 때 부가적인 작업이 필요합니다.

 

탐색 연산

BSTNode* BST_SearchNode(BSTNode* Tree, ElementType Target){
    if(Tree == NULL)
        return NULL;
    
    if(Tree->Data == Target)
        return Tree;
    else if(Tree->Data > Target)
        return BST_SearchNode(Tree->Left, Target);
    else
        return BST_SearchNode(Tree->Right, Target);
}

 

해당 요소를 찾는 과정을 보면 배열에서와 같이 중앙 노드와 해당 요소를 비교하며 중앙 노드보다 작으면 왼쪽 자식 노드, 크면 오른쪽 자식 노드로 연산을 이어나갑니다.

삽입 연산

void BST_InsertNode(BSTNode* Tree, BSTNode *Child){
    if(Tree->Data < Child->Data){
        if(Tree->Right == NULL)
            Tree->Right = Child;
        else
            BST_InsertNode(Tree->Right, Child);
    }
    else if(Tree->Data > Child->Data){
        if(Tree->Left == NULL)
            Tree->Left = Child;
        else
            BST_InsertNode(Tree->Left, Child);
    }
}

노드 삽입의 연산의 핵심은 새 노드가 삽입될 곳이 어디인지를 찾아내는 일입니다. 이진 탐색 트리의 조건에 맞되 빈 공간에 노드를 삽입시킵니다.

삭제 연산

이진 탐색 트리의 삭제 연산은 생각해야할 부분이 상당히 많습니다. 삭제되는 노드의 자식 노드 갯수에 따라 케이스가 나뉘게 됩니다.

• 삭제되는 노드의 자식 노드가 없는경우 => 따로 신경쓸 것 없이 삭제된 노드의 자리를 NULL값으로 채워주면 됩니다.
• 삭제되는 노드의 자식 노드가 하나인 경우 => 삭제되는 노드의 자식 노드가 붕 뜨게됩니다. 이는 삭제되는 노드의 부모 노드에 이 붕 뜨는 노드를 연결해주면 됩니다.
• 삭제되는 노드의 자식 노드가 두개인 경우 => 삭제 노드의 오른쪽 하위 트리에서 가장 작은 값을 가진 노드(최솟값 노드)를 삭제된 위치에 옮깁니다. 이 때 최솟값 노드도 자식 노드를 갖고 있을 수 있는데 이 노드 자체가 최솟값이기 때문에 자식 노드를 갖는다면 오른쪽 노드만을 갖습니다. 이 오른쪽 노드는 그대로 부모 노드에 연결 시키고 최솟값 노드는 예정대로 삭제된 위치에 옮기면 됩니다.

BSTNode* BST_SearchMinNode(BSTNode* Tree){	//최소값 노드 탐색 연산(삭제 연산에 필요)
	if(Tree == NULL)
    	return NULL;
    
    if(Tree->Left == NULL)
    	return Tree;
    else
    	return BST_SearchMinNode(Tree->Left);
}

BSTNode* BST_RemoveNode(BSTNode* Tree, BSTNode* Parent, ElementType Target){
    BSTNode* Remove = NULL;
    
    if(Tree == NULL) return NULL;
    
    if(Tree->Data > Target)
        Remove = BST_RemoveNode(Tree->Left, Tree, Target);
    else if(Tree->Data < Target)
        Remove = BST_RemoveNode(Tree->Right, Tree, Target);
    
    else{   //삭제할 노드를 찾음
        Remove = Tree;
        
        if(Tree->Left == NULL && Tree->Right == NULL){  //삭제할 노드의 자식 노드가 없는 경우
            if(Parent->Left == Tree)
                Parent->Left = NULL;
            else
                Parent->Right = NULL;
        }
        
        else{
            if(Tree->Left != NULL && Tree->Right != NULL)  {    //삭제할 노드의 자식 노드가 양쪽 모두 있는 경우
                BSTNode* MinNode = BST_SearchMinNode(Tree->Right);
                MinNode = BST_RemoveNode(Tree, NULL, MinNode->Data);    //최소 노드의 자식노드도 신경써줘야 함
                Tree->Data = MinNode->Data;
            }
            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;
            }
        }
    }
}

---

지금까지 이진 탐색 트리에 대해 정리해 보았는데, 이진 탐색 트리에는 치명적인 문제점이 한가지 있습니다.

만약 이진 탐색 트리가 한쪽 방향으로만 길게 늘어나 기형적으로 성장하면 검색 효율이 극단적으로 떨어진다는 점입니다.

계속해서 최솟값이 들어오거나 계속해서 최댓값이 들어오면 이러한 모양이 되겠네요. 

실제로 데이터를 담는 경우 이러한 경우가 심심치 않게 발생합니다.

이러한 문제점을 해결하기 위해 다음 포스팅에서 '레드 블랙 트리'에 대해 알아보겠습니다.

 

2023.01.09 - [자료구조/트리(Tree)] - [자료구조] 레드 블랙 트리(Red Black Tree) - 코딩밥상

[자료구조] 레드 블랙 트리(Red Black Tree) - 코딩밥상