이진탐색트리(Binary Search Tree)

이진탐색트리(Binary Search Tree)

  이진탐색(Binary Search)이 항상 동작하도록 구현하여 탐색속도를 극대화시킨 자료구조를 이진탐색트리라고 한다.

 

  이진탐색트리에서는 항상 부모노드가 왼쪽자식노드보다는 크고 오른쪽자식노드보다는 작다.

 

탐색방법

 

  여기서 37을 찾는다고 했을 때 루트노드인 30과 비교한다.

  그럼 찾는값보다 루트노드가 더 작기 때문에 더 큰값들이 있는 오른쪽 자식노드로 이동한다.

  오른쪽 자식노드인 48은 찾는값인 37보다 크기때문에 더 작은값인 왼쪽 자식노드로 이동한다.

  

  이와같이 한 노드의 값을 찾을 값과 비교하면 한쪽을 제외하고 검색할 수 있다.

  한번 확인할때마다 확인해야 하는 원소의 개수가 절반씩 줄어든다는 점에서 완전이진트리인 경우

  탐색시간에 O(logN)의 시간 복잡도를 갖는다.

 

이진탐색트리의 삭제

  1. 자식노드가 없는 경우

    삭제할 노드의 자식노드가 없는 경우 단순히 제거만 하면 된다.

 

  2. 자식노드가 하나만 존재하는 경우

     

    48처럼 하나의 자식노드를 갖고 있다면 삭제할 노드의 자리에 자식노드를 넣어준다.

    48을 삭제한다고 하면 37을 48의 위치로 바꿔주면 된다.

 

  3. 자식노드가 둘다 존재하는 경우

    위 그림에서 30처럼 자식노드가 둘다 존재한다면 삭제할 노드의 자리에 그 보다 큰 값들 중

    바로 다음으로 큰값을 넣어준다.

    30을 삭제한다면 다음으로 큰 값인 37을 30위치에 넣어준다.

 

예제코드

 

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

typedef struct{
  int data;
  struct Node* leftChild;
  struct Node* rightChild;
} Node;

Node* insertNode(Node* root, int data){ //특정 root에서 어떠한 노드를 삽입하고자 한다면
  if(root == NULL){ //그 루트가 NULL값이라면 해당 루트를 초기화
    root = (Node*)malloc(sizeof(Node));
    root->leftChild = root->rightChild = NULL;
    root->data = data;
    return root;
  }
  else{
    if(root->data > data){ //삽입하고자하는 데이터가 더 작다면 왼쪽으로 이동해서
                           //다시한번 노드를 삽입
      root->leftChild = insertNode(root->leftChild, data);
      //삽입된 결과를 자신의 왼쪽 자식노드에 넣어준다.
    }
    else{ //오른쪽 자식노드에 삽입된 결과를 넣어준다.
      root->rightChild = insertNode(root->rightChild, data);
    }
  }
  return root;
}

Node* searchNode(Node* root, int data){ //탐색
  if(root == NULL) return NULL;
  if(root->data == data) return root; //특정한 노드를 발견했다면 해당 노드 자체를 반환
  else if(root->data > data) return searchNode(root->leftChild, data);
  //해당 노드의 데이터보다 찾고자 하는 데이터가 더 작다면 왼쪽자식노드로 다시 탐색
  else return searchNode(root->rightChild, data);
  //데이터가 더 크다면 오른쪽자식노드로 다시 탐색
}

void preorder(Node* root){ //순회
  if(root == NULL) return;
  printf("%d ", root->data);
  preorder(root->leftChild);
  preorder(root->rightChild);
}


Node* findMinNode(Node* root) {//작은 노드를 탐색
  Node* node = root;
  while(node->leftChild != NULL){
    node = node->leftChild;
  }
  return node;
}

Node* deleteNode(Node* root, int data){//삭제함수
  Node* node = NULL;
  if(root == NULL) return NULL;
  if(root->data > data) root->leftChild = deleteNode(root->leftChild, data);
  //찾고자하는 데이터가 현재노드보다 작다면 왼쪽으로 탐색
  else if(root->data < data) root->rightChild = deleteNode(root->rightChild, data);
  //아니라면 오른쪽으로 탐색
  else{ //해당 노드가 데이터와 같다면
    if(root->leftChild != NULL && root->rightChild != NULL) { //자식노드가 두개 다 존재
      node = findMinNode(root->rightChild);//오른쪽 자식노드중 가장 작은값을 탐색
      root->data = node->data;//해당 노드의 데이터를 탐색한 값으로 변경
      root->rightChild = deleteNode(root->rightChild, node->data);
      //바꿔준 노드는 삭제.
    }
    else{//자식노드가 한개 이하일때
      node = (root->leftChild != NULL) ? root->leftChild : root->rightChild;
      //왼쪽 자식노드가 NULL이 아니라면 노드에 왼쪽 자식노드를 담고
      //NULL이라면 오른쪽 자식노드를 담는다.
      free(node);
      return node;
    }
  }
  return root;
}
    
int main(void){
  Node* root = NULL;
  root = insertNode(root, 30);
  root = insertNode(root, 17);
  root = insertNode(root, 48);
  root = insertNode(root, 5);
  root = insertNode(root, 23);
  root = insertNode(root, 37);
  root = insertNode(root, 50);
  root = deleteNode(root, 30);
  preorder(root);
  system("pause");
}

  삽입처리된 트리의 결과를 확인할 수 있다.

  원하는 값을 찾아 출력하는 예제코드는 아니다.

  root = deleteNode(root, 30);을 주석처리하고 실행하면

  출력값은 30 17 5 23 48 37 50 으로 출력되는데 위에 탐색방법에 있는 그림과 같은 형태다.

  preorder에서 처음에 루트값인 30을 먼저 출력하고 leftChild를 먼저 탐색하기 때문에 17 5 23이 출력되고

  그 다음 rightChild에서 48 37 50 이 출력된다.

 

  그리고 삭제함수를 포함해서 실행한다면 37 17 5 23 48 50이 출력된다.

  30을 삭제하고 그 바로 다음으로 큰 값인 37이 root로 올라오게 되는것을 확인할 수 있다.

 

  이진탐색트리의 성능을 최대로 끌어내기 위해서는 이진탐색트리가 완전 이진탐색트리에 가가워질수 있도록 설계

  해야 한다.

  

  트리를 사용하면 데이터를 처리함에 있어서 효율적이다.

  트리에서 데이터의 개수가 N개일 때 배열과 마찬가지로 O(N)의 공간만이 소요되며 삽입 및 삭제에 있어서

  일반적인 경우 기존의 배열을 이용하는 방식보다 효율적이다. 그래서 데이터베이스 등 대용량 저장 및 검색

  자료구조로 많이 사용된다.

  

  한쪽으로 치우친 편향 이진트리(Skwed Binary Tree)의 경우 탐색에 있어 O(N)의 시간 복잡도가 형성되므로

  기존의 배열을 사용하는 것 보다 오히려 많은 공간과 시간이 낭비된다.

 

  따라서 이진트리를 만들때는 트리의 균형이 맞도록 설정하는 것이 중요하다.

  

 

 

레퍼런스

패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직