이진 탐색 트리 설명

탐색을 하려면 뭔가 제약조건이 많이 걸린다. 

 

하지만 애초에 데이터를 제약조건을 기준으로 저장을 하면 딱히 문제 될 일은 아니다.

 

그래서 데이터를 이진 탐색에 맞춰 이진 탐색 트리의 구조로 저장한다.

typedef struct tagNode {
	struct tagNode* Left;
	struct tagNode* Right;

	int Data;
} Node;

기존의 이진트리의 노드와 구조는 같다.

 

다만 노드를 생성하고 트리에 추가할 때, 데이터의 값을 확인하여 작으면 왼쪽, 크면 오른쪽으로 추가한다.

void BST_InsertNode( Node* Tree, Node *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인지 확인하고 들어가게 된다.

 

NULL이 아니라는 거는 이미 데이터가 있으므로 그 데이터와 다시 한번 추가 함수를 수행한다.

 

그럼 결국엔 트리의 젤 밑단에 알맞은 자리에 추가될 것이다.

 

 

 

이진 탐색 트리는 치명적인 단점이 있다.

1 ~ 10000의 값을 추가한다고 할 때, 초기값을 100으로 설정하면 상당히 오른쪽으로 치우쳐지게 생성될 것이다.

 

그럼 결국 탐색하려면 상당히 많은 노드를 거치게 되고 성능 저하로 이어질 것이다.

 

이를 보완한 방법으로 레드 블랙 트리가 있다.