이진탐색트리 Insert, Search 구현

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

 

이진 탐색 트리는 '이진 트리'에 '데이터의 저장 규칙'을 더해놓는 것이 '이진 탐색 트리'이다.

 

이진 탐색트리가 되기 위해서는 다음과 같은 조건이 필요하다.

 

1. 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다.

 

2. 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.

 

3. 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.

 

4. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

 

앞에 언급한 키(key)는 탐색의 조건이 될 수 있으며 이번에 구현할 코딩에서는 데이터가 곧 key 값이 된다.

 

위 조건을 만족하는 트리를 그림으로 표현 하면 다음과 같다 (윤성우의 자료구조 참조)

 

 

위 그림을 통해 보면 다음 수식이 어디서나 만족함을 알 수 있다.

 

왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키

 

위 수식을 코드로 구현하면 이진 탐색 트리의 추가, 탐색은 자연스럽게 구현이 된다.

 

코드로 구현해보자

 

데이터 추가를 코드로 구현하면 다음과 같다.

 

BTreeInsert함수

/* @brief  이진트리 데이터 Insert 함수
 * @detail 데이터를 Arg로 받으면 정해진 규칙에 따라 데이터를 추가한다.
 *         문제가 발생한 경우 while(1)을 통해 코드가 멈춘다.
 *  
 * @param  root: 이진트리의 head Node
 *         data: 추가 하고자 하는 데이터
 *           
 * @retval None
 */
void BTreeInsert(BTreeNode *root, BTData data)
{
    TR_FUNC(TRACE);
    
    /* == Header일 경우 데이터 추가 후 return == */
    if (GetData(root) == 0xdeadbeef)
    {
        SetData(root, data);
        return;
    }

    BTreeNode *_localRoot = root;

    /* == Node 찾기 == */
    /* == 추가하고자 하는 데이터가 오른쪽 조건을 만족하는 지 확인 == */
    if ((GetLeftSubTree(_localRoot) != NULL) && (data < GetData(_localRoot)))
    {
        BTreeInsert(GetLeftSubTree(_localRoot), data);
        return;
    } /* == 추가 하고자 하는 데이터가 왼쪽 조건을 만족하는 지 확인 == */
    else if ((GetRightSubTree(_localRoot) != NULL) && (data > GetData(_localRoot)))
    {
        BTreeInsert(GetRightSubTree(_localRoot), data);
        return;
    }

    /* == 데이터 삽입 == */
    /* == 추가하고자 하는 데이터가 오른쪽 조건을 만족하는 지 확인 후 데이터를 추가한다 == */
    if ((GetLeftSubTree(_localRoot) == NULL) && (data < GetData(_localRoot)))
    {
        BTreeNode *leftNode = MakeBTreeNode();
        MakeLeftSubTree(_localRoot, leftNode);
        SetData(leftNode, data);
    } /* == 추가하고자 하는 데이터가 왼쪼 조건을 만족하는 지 확인 후 데이터를 추가한다 == */
    else if ((GetRightSubTree(_localRoot) == NULL) && (data > GetData(_localRoot)))
    {
        BTreeNode *rightNode = MakeBTreeNode();
        MakeRightSubTree(_localRoot, rightNode);
        SetData(rightNode, data);
    }
    else
    {
        printf("BTree Insert Error\r\n");
        while(1);
    }
}

 

Node를 찾을 때는 재귀 함수를 사용하여 다음 노드를 찾게 했다. 노드를 찾은 후 데이터 삽입할때 잘못된 곳에 데이터 추가될 수 있으므로 마지막에 return을 추가하였다.

 

데이터 추가시에는 자식 노드가 NULL 값인지 확인 후 NULL 값일 때에만 데이터를 추가하도록하였다.

위 if문을 모두 타지 않는 경우는 key값이 중복 또는 다른 문제가 발생한 경우이므로 while문으로 코드를 멈추게 하였다.

 

다음은 탐색 부분이다.

 

탐색 역시 앞서 말한 수식을 사용하였기에 Insert함수만 이해했다면 크게 어렵지 않을 것이다.

 

BTreeSearch함수

/* @brief  이진트리 데이터 Search 함수
 * @detail 데이터를 Arg로 받으면 정해진 규칙에 따라 데이터를 xkator한다.
 *         해당 데이터를 찾으면 데이터의 노드포인터를 리턴한다.
 *  
 * @param  root: 이진트리의 head Node
 *         data: 찾고자 하는 데이터
 *           
 * @retval 찾은 데이터의 포인터 Value or NULL
 */
BTreeNode *BTreeSearch(BTreeNode *root, BTData findData)
{
    TR_FUNC(TRACE);

    BTreeNode *_localRoot = root;
    /* == 현 노드의 데이터 가 찾고자 하는 데이터면 리턴한다. == */
    if (GetData(_localRoot) == findData)
        return root;
    /* == 찾고자 하는 데이터가 오른쪽 조건을 만족하는 지 확인 == */
    else if ((GetLeftSubTree(_localRoot) != NULL) && (findData < GetData(_localRoot)))
        return BTreeSearch(GetLeftSubTree(_localRoot), findData);
    /* == 찾고자 하는 데이터가 왼쪽 조건을 만족하는 지 확인 == */
    else if ((GetRightSubTree(_localRoot) != NULL) && (findData > GetData(_localRoot)))
        return BTreeSearch(GetRightSubTree(_localRoot), findData);

    /* == 위 조건을 만족하지 못하면 데이터를 찾지 못한 것이므로 NULL 값을 리턴한다. == */
        printf("BTree Search No Data\r\n");
        return NULL;
}

Search 함수도 Insert함수와 마찬가지로 재귀 함수로 구현하였다.

 

main 함수를 다음과 같이 코딩하여 검증하였다.

/*
 * main.c
 *
 *  Created on: 2022. 01. 2.
 *      Author: Jitae Kim
 */

#include "stdio.h"
#include "string.h"
#include "BinaryTree.h"

int array[] = {17, 9, 25, 11, 29, 10, 22};

int main(void)
{
    printf("Binary Tree !! \r\n");

    BTreeNode * root = MakeBTreeNode();

    for (int idx = 0; idx < (sizeof(array) / sizeof(int)); idx++)
    {
        BTreeInsert(root, array[idx]);
        printf("Insert Data: %d \r\n", array[idx]);
    }

    BTreeNode *findNode = BTreeSearch(root, 22);

    if (findNode == NULL)
        printf("Can not find Data \r\n");

    else
        printf("findData: %d \r\n", findNode->data);


    return 0;
}

gdb를 통해 Insert, Search 과정에서 위 그림과 동일하게 가져가는 지 확인 하였다.

 

실행화면

코드 링크: https://github.com/KJT9109/Data_Structure/tree/master/Binary_Tree