이진 탐색 트리(Binary Search Tree)란?

■ 탐색을 효육적으로 하기 위한 자료구조

 

※ 특징

• 이진트리이며 모든 원소는 서로 다른 유일한 키(key)를 가진다.
• (왼쪽 sub-트리의 key값) < (루트의 key값) < (오른쪽 sub-트리의 key값)
• 왼쪽 sub-트리와 오른쪽 sub-트리도 이진탐색트리이다.

 

※ 탐색 : searchBST()연산

• ROOT에서 시작.
• 탐색할 key값을 루트 노드의 key값과 비교.
• (1) (키값 = 루트 노드의 키값) : 원하는 원소를 찾았으므로 탐색 성공.
• (2) (키값 < 루트 노드의 키값) : 루트 노드의 왼쪽 sub-트리에 대해서 탐색연산 수행.
• (3) (키값 > 루트 노드의 키값) : 루트 노드의 오른쪽 sub-트리에 대해서 탐색연산 수행.

▷예시 코드

BinTree* searchBST(BunTree* bt, BTData x)

{

    BinTree* p = bt;

    while(p != NULL) {

        if(x == p->key) return p;

        if(x < p->key) p = p->left;

        else p = p->right;

    }

    printf("Error: 찾는 키가 없습니다.\n");

    retrun NULL;

}

 

※ 삽입 : insertBST() 연산

• 먼저 탐색 연산을 수행
• 탐색 실패한 위치에 원소를 삽입

▷예시 코드

void insertBST(BinTree* bt, BTData x) {

    BinTree* p = bt;

    BinTree* parent = NULL;

 

//삽입할 노드 탐색

    while(p != NULL) {

        if(x == p->key) {

            printf("Error: 이미 같은 키가 있습니다.\n");

            return;

        }

        parent = p;

        if(x < p->key) p = p->left;

        else p = p->right;

    }

//삽입할 노드 생성

    BinTree* newNode = (BinTree*)malloc(sizeof(BinTree));

    newNode->key = x;

    newNode->left = NULL;

    newNode->right = NULL;

 

//삽입노드 연결

    if(bt == NULL) bt = newNode;

    if(x < parent->key) parent->left = newNode;

    else parent->right = newNode;

}

 

※ 삭제 : deleteBST() 연산

• Case 1: 삭제할 노드의 차수가 0인 경우
•     부모의 해당 자식의 필드를 NULL로 처리후 노드 삭제
• Case 2: 삭제할 노드의 차수가 1일 경우
•     삭제될 노드의 자식을 삭제될 노드의 부모노드에 연결후 노드 삭제
• Case 3: 삭제할 노드의 차수가 2인 경우
•      1. 삭제할 노드의 자손들 중 후계자를 선택하여 자리를 물려줌
•      2. 후계자: 왼쪽 sub-트리 중 가장 큰 원소 or 오른쪽 sub-트리 중 가장 작은 원소
•      3. 후계자 노드는 자식이 1 또는 0이므로 CASE1, CASE2 이용