[자료구조] 탐색(Search) 1 - 이진 탐색 트리 (11-2-2) 삽입

서희찬·2021년 4월 17일
0

이진 탐색 트리의 헤더파일

구현에 앞서 우리는 구현방법을 결정해야 한다.
다음 두 가지중 한가지 방법을 선택하자 !

  • 구현 방법 1
    이전에 구현한 이진 트리를 참조하여 처음부터 완전히 다시 구현한다.
  • 구현 방법 2
    이진 탐색트리도 이진 트리이니, 이전에 구현한 이진 트리를 활용하여 구현한다.

첫번째 방법을 이용하면, 앞서 공부한 이진 트리의 코드를 이해 없이 바로 분석할 수 있다.
반면!!
두번째 방법에는

  • "이진 탐색 트리가 이진 트리의 확장이라는 사실을 코드 레벨에서 확인할 수 있다.
  • "앞서 구현한 이진 트리를 점검하는 기회가 된다. 이진 트리의 ADT를 통해서 정의한 함수들이 기능적으로 부족하다면 이에 대한 반성 및 개선의 기회가 된다. "
  • " 이진 트리를 활용한 이진 탐색 트리의 구현을 경험하는 것은, 좋은 프로그래밍 모델을 경험하는 기회도 된다."

이라는 장점이 있다.

그렇다면 어떤 방법을 선택해야할지 바로 뙇! 알지 않겠는가!?
바로 두번째 방법이다.
이 방법이 우리가 흔히 말하는 " 프로그래밍을 구조적으로 잘하는 사람"들이 선택하는 방법이다!

(이렇게 자료구조에서는 이미 만들었던것을 활용하는 것이 매우 중요한것같다 ! )

자!
이진 탐색 트리를 위해서는

  • BinaryTree2.h,c 파일이 필요하다.

기억이 안날수도 있으니 BinaryTree2.h 에는

이 함수들이 선언되어있다.

옛날에 저자가 했던 말이 생각나는가?

"위에서 소개한 함수들은 이진 트리를 만드는 "도구"로써 정의된 것이다. 도구인 이 함수들을 이용해서 이진 트리르 구성해야 하는 것이지, 이진 트리가 자동으로 만들어지는 것이 아니다 ! "

그러므로! 이 도구를 활용하여 이진 탐색트리를 구현 해보자 !
우선 헤더파일 선언부터 하자 !
BinarySearchTree.h

//
//  BinarySearchTree.h
//  BinarySearchTree
//
//  Created by 서희찬 on 2021/04/17.
//

#ifndef BinarySearchTree_h
#define BinarySearchTree_h

#include "BinaryTree2.h"

typedef BTData BSTData;

//BST의 생성 및 초기화
void BSTMakeAndInit(BTreeNode ** pRoot);

// 노드에 저장된 데이터 반환
BSTData BSTGetNodeData(BTreeNode * bst);

// BST를 대상으로 데이터 저장(노드의 생성과정 포함)
void BSTInsert(BTreeNode ** pRoot, BSTData data);

// BST를 대상으로 데이터 탐색
BTreeNode * BSTSearch(BTreeNode * bst, BSTData target);

#endif /* BinarySearchTree_h */

이제 간단한 메인 함수를 보고 헤더파일에 선언된 함수들의 사용법을 알아보자 .

BTreeNode * bst = bstRoot
BTreeNode ** pRoot = &bstRoot

이진 탐색 트리의 구현 : 삽입과 삭제

삽입은 정말 말 그대로

"비교대상이 없을 때까지 내려간다"
"비교대상이 없는 그 위치가 새 데이터가 저장될 위치이다."

이다.
그림을 통해 예를 보자 !

어떤가! 말 그대로이지 않는가!
이제 이를 그대로 코드로 옮겨보자 .


void BSTInsert(BTreeNode ** pRoot, BSTData data)
{
    BTreeNode * pNode = NULL; //parent Node
    BTreeNode * cNode = *pRoot; // Current Node
    BTreeNode * nNode = NULL; // New Node
    
    // 새노드 저장될 위치 찾는다.
    while(cNode != NULL)
    {
        if(data == GetData(cNode))
            return; // 데이터 중복 허용 x
        
        pNode = cNode;
        
        if(GetData(cNode)>data)
        {
            cNode = GetLeftSubTree(cNode);
        }
        else
            cNode = GetRightSubTree(cNode);
    
    }
    
    //pNode의 자식 노드로 추가할 새 노드의 생성
    nNode = MakeBTreeNode(); // 새 노드 생성
    SetData(nNode, data);
    
    // pNode 의 자식 노드로 추가할 새 노드의 생성
    if(pNode != NULL) // 새  노드가 루트노드아니라면
    {
        if(data < GetData(pNode))
            MakeLeftSubTree(pNode, nNode);
        else
            MakeRightSubTree(pNode, nNode);
    }
    else{ //새노드가 루트노라면
        *pRoot = nNode;
    }
    

}

추가 설명을 하고 끝마치겠다.
먼저 while문을 보자.
이 while문은 저장할 값의 크기에 따라 왼/오로 이동하며 새 노드의 저장 위치를 찾는것이다.

따라서 이 while문이 끝나면
cNode에 저장될 위치정보가 담긴다.

그런데!!!!!

이 이취에 노드를 저장하기 위해 필요 한것은 바로!
이 위치를 자식으로 하는 부모 노드의 주소 값이다 !!
왜냐!?
부모 노드에 자식노드의 주소값이 저장 되기 때문이다!!

그래서 !

이후 부모 노드의 주소 값이 담긴 pNod를 기반으로 자식 노드를 추가 한다!!

그래서 while문을 통해 저장할 위치의 부모 노드를 pNode에 저장하고 탈출 한 후, nNode를 pNode의 데이터와 비교한 후 왼/오 중 한 곳에 저장한다.

이제 다음 포스트에서 탐색함수를 배워보자 !

profile
부족한 실력을 엉덩이 힘으로 채워나가는 개발자 서희찬입니다 :)

0개의 댓글