자료구조-이진탐색트리 BST

트리 개념, 이진 트리, C로 트리 구현: https://foxtrotin.tistory.com/184

자료구조-트리 순회(전위 순회, 중위 순회, 후위 순회) https://foxtrotin.tistory.com/187

 

 

이진 탐색 트리

이진 트리를 탐색용 자료구조로 쓰기 위해

원소 크기에 따라 노드 위치를 정의한 트리

 

-모든 원소는 서로 다른 유일한 키를 갖는다

-왼쪽 서브 트리에 있는 원소의 키는 루트의 키보다 작다

-오른쪽 서브 트리에 있는 원소의 키는 루트의 키보다 크다

-왼쪽/오른쪽 서브 트리도 이진 탐색 트리다

 

 

 

이진 탐색 트리의 탐색 연산

1. 루트에서 시작한다

2. 탐색할 키 값 x과 노드의 키 값을 비교

2-1. (x==루트 노드의 키 값)인 경우: 찾음

2-2. (x<루트 노드의 키 값)인 경우: 왼쪽 서브트리 탐색

2-3. (x>루트 노드의 키 값)인 경우: 오른쪽 서브트리 탐색

3. 서브트리로 내려가서 해당 노드를 루트로 1~2번 과정 반복

 

 

이진 탐색 트리에서 원소 11 탐색하는 과정

 

1. 루트 8 < 11이므로 오른쪽 서브트리 탐색

2. 10 < 11이므로 오른쪽 서브트리 탐색

3. 11 < 14이므로 왼쪽으로

4. 11==11 탐색 종료

 

선언

typedef struct node { 
    int key;
    struct node *left, *right; 
}  NODE; 

NODE *newNode(int item) { 
    NODE *temp =  (struct node *)malloc(sizeof(NODE)); //메모리 할당
    temp->key = item; //데이터 넣음
    temp->left = temp->right = NULL; //왼쪽,오른쪽 자식 NULL
    return temp; 
} 

 

삽입 연산

1. 삽입할 원소와 같은 원소가 트리에 있는지 탐색으로 확인 (모든 원소의 값은 유일하다)

2. 탐색 실패한 위치에 원소 삽입

 

 

원소 4를 삽입하는 예시

1. 찾는 키 값 4 < 루트 노드의 키 값 8 이므로 왼쪽으로

2. 4 > 노드의 키 값 3 이므로 오른쪽 서브 트리로

3. 4 < 5이므로 왼쪽으로.. 가야 하지만 갈 곳이 없으므로 탐색 실패

탐색 실패한 자리가 삽입할 원소의 자리니까 4의 위치는 5의 왼쪽 자식

 

NODE* insert(NODE* node, int key)
{
	if (node == NULL) return newNode(key); //트리가 비었다면 새로 노드를 만듦

	if (key < node->key) node->left = insert(node->left, key); //찾는키<노드키면 왼쪽
	else if (key > node->key) node->right = insert(node->right, key); //반대면 오르쪽

	return node; //노드 포인터 반환
}  

 

삭제 연산

1. 삭제할 노드의 위치를 알아야 하므로 탐색 연산

2. 찾으면 삭제하는데 삭제하고 트리 재구성 작업이 필요

-삭제할 노드가 단말 노드인 경우 (차수가 0)

-삭제할 노드가 자식 노드를 한 개 가진 경우 (차수가 1)

-삭제할 노드가 자식을 두 개 가진 경우 (차수가 2)

 

 

삭제할 노드가 단말 노드인 경우 (차수가 0)

찾으면 그냥 삭제한다

 

삭제할 노드가 자식 노드를 한 개 가진 경우 (차수가 1)

삭제하고, 자식 노드를 삭제한 노드의 부모와 연결

 

 

삭제할 노드가 자식을 두 개 가진 경우 (차수가 2)

삭제하고 나면 서브트리 두 개가 고아가 됨

둘 중 어느 것을 이을지 결정해야 함

 

선택 방법

-왼쪽 서브트리에서 가장 큰 자손노드 선택 (왼쪽 서브트리의 가장 오른쪽 노드)

-오른쪽 서브트리에서 가장 작은 자손노드 선택 (오른쪽 서브트리의 가장 왼쪽 노드)

 

 

검색 연산

NODE* search(NODE* root, int key) {
	if (root == NULL) return NULL;

	if(root->key == key) return root; //key가 자기 자신인 경우 찾았으므로 리턴
	else if (root->key < key) return search(root->right, key); //현재키<찾으려는 키면 오른쪽 트리로(큰수로)
	else return search(root->left, key); //아니면 왼쪽 트리로
}

작으면 왼쪽 크면 오른쪽

 

 

전체 코드

#include<stdio.h> 
#include<stdlib.h> 

typedef struct node {
    int key;
    struct node* left, * right;
}  NODE;

int cnt = 0;
NODE* search(NODE* root, int key) {
    cnt++;
    if (root == NULL) return NULL;

    if (root->key == key) return root; //key가 자기 자신인 경우 찾았으므로 리턴
    else if (root->key < key) return search(root->right, key); //현재키<찾으려는 키면 오른쪽 트리로(큰수로)
    else return search(root->left, key); //아니면 왼쪽 트리로
}

NODE* newNode(int item) {
    NODE* temp = (NODE*)malloc(sizeof(NODE));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

void inorder(NODE* root) { //중위 순회로 출력
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d \n", root->key);
        inorder(root->right);
    }
}

NODE* insert(NODE* node, int key) {
    if (node == NULL) return newNode(key); //트리가 비었다면 새로 노드를 만듦

    if (key < node->key) node->left = insert(node->left, key); //찾는키<노드키면 왼쪽
    else if (key > node->key) node->right = insert(node->right, key); //반대면 오르쪽

    return node; //노드 포인터 반환
}

int main() {
    /*
                  50
               /     \
              30      70
             /  \    /  \
           20   40  60   80 */

    NODE* root = NULL;

    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    cnt = 0;
    search(root, 80);

    printf("찾는 데 몇 번 순회?: %d\n", cnt);

    inorder(root); //출력

    return 0;
}