[C로 만드는 자료구조]이진 탐색 트리(Binary Search Tree)

이진 탐색 트리(Binary Search Tree) - 정의

이진 탐색 트리는 탐색 작업을 효율적으로 하기 위한 자료구조입니다. 다음의 정의들을 가지고 있습니다.

• 모든 원소는 서로 다른 유일한 키를 가짐
• 왼쪽 서브트리에 있는 원소들의 값은 그 루트의 값보다 작음
• 오른쪽 서브트리에 있는 원소의 값들은 그 루트의 값보다 큼
• 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리임
  

왼쪽 서브트리 값<루트 노트 값 < 오른쪽 서브트리 값의 관계가 형성되기 떄문에 중위순회를 하게되면 오름차순으로 정렬된 값을 얻을 수 있습니다. 다음 그림과 같은 형태가 됩니다.

이진 탐색 트리(Binary Search Tree) - 탐색

탐색은 루트에서 시작을 합니다. 그 다음부터의 과정은 다음과 같습니다. 탐색할 값이 x 일때

• x = 루트 노드의 키 값 인 경우 : 원하는 원소를 찾았으므로 탐색 연산 성공
• x < 루트노드의 키 값 인 경우 : 루트 노드의 왼쪽 서브 트리에 대해서 탐색
• x > 루트노드의 키 값 인 경우 : 루트 노드의 오른쪽 서브 트리에 대해서 탐색

이런식으로 서브트리로 넘어가서 순환적으로 탐색을 반복하게 됩니다. 다음의  11이란 값을 찾는 연산을 그림으로 나타내면 다음과 같습니다.

1. 11을 루트 노드의 키 값 8과 비교 -> 오른쪽으로 이동
2. 11과 10을 비교 -> 오른쪽으로 이동
3. 11과 14를 비교 -> 왼쪽으로 이동
4. 맞는값 찾으면 종료

이진 탐색 트리(Binary Search Tree) - 삽입

삽입을 하기전에 같은 원소가 있는지 확인을 해야하기 떄문에 탐색연산부터 실행하여 같은 원소가 있는 지 탐색하여 확인합니다. 탐색후 실패한 위치에 원소를 삽입하면 삽입 연산이 됩니다.

삽인 연산 과정을 다음과 같은 그림으로 나타낼 수 있습니다.

이진 탐색 트리(Binary Search Tree) - 삭제

이진 탐색트리에서 삭제연산은 좀 고려해줘야 할 것이 많습니다. 하지만 우선 삭제 연산의 순서 부터 알아보겠습니다. 우선 삭제할 값에 대한 값을 트리에서 탐색을 해야 합니다. 그 다음 은 찾은 노드를 삭제해야 하는데 3가지 경우로 나누어서 삭제경우를 나누어야 합니다.

• 삭제할 노드가 단말 노드인 경우 : 차수가 0인 경우
• 삭제할 노드가 하나의 자식 노드를 가진 경우 : 차수가 1인 경우 : 차수가 1인 경우
•  삭제할 노드가 두 개의 자식 노드를 가진 경우 : 차수가 2인 경우

단말노드의 경우(차수가 0일 경우)

단말 노드 삭제 연산은 다음과 같은 연산 과정을 거치게 됩니다. 탐색을 통해서 위치를 찾아간 다음 맞는 위치를 찾으면 대상 노드를 삭제만 하면 끝납니다. 

차수가 1일 경우

탐색을 통하여 찾아갔는데 차수가 1인 경우에는 대상 노드의 자식노드를 지우려는 대상 노드의 자리에 끼워넣어주고 대상 노드는 삭제해 줍니다.

차수가 2일 경우

2차의 경우는 좀 어렵습니다. 1차의 경우처럼 노드를 삭제하면 붙일게 하나가 아니라 2개가 되는데 이럴 때는 삭제하는 노드와 가장 비슷한 값을 가지는 노드를 삭제 노드 위치로 가져와서 삭제를 시켜줍니다. 다음은 후계자 선택 방법(삭제된 자리에 채워넣는 대상) 2가지입니다.

후계자 선택방법은 다음과 같습니다.

• 왼쪽 서브트리에서 가장 큰 자손을 선택. 즉, 루트의 왼쪽 자식노드를 루트로 하는 트리에서 가장 오른쪽에 있는 노드가 됩니다.
  
  
• 오른쪽 서브트리에서 가장 작은 자손을 선택. 즉, 루트의 오른쪽 자식노드를 루트로 하는 트리에서 가장 오른쪽에 있는 노드가 됩니다.
  

이진 탐색 트리(Binary Search Tree) - ADT 구현

구현은 3가지를 했습니다. 값이 있는 지 없는지 탐색하는 함수, 삽입하는 함수, 삭제하는 함수를 구현했습니다. 이진 탐색 트리를 구현할때는 트리구현때 처럼 다음과 같은 구조체들을 사용해서 구현합니다.

#include<stdio.h>
#include<malloc.h>
struct TreeNode
{
    int key;
    TreeNode *LNode;
    TreeNode *RNode;
};
struct Tree
{
    TreeNode *Root;
};

• void Tree_Init()
  
  

  void Tree_Init(Tree *Target_Tree)
  {
      Target_Tree->Root = NULL;
  }

  초기화 하는 함수입니다.
  
  

• bool Is_There()
  
  

  bool Is_There(Tree *Target_Tree, int Item)
  {
      TreeNode *Cur = Target_Tree->Root;
      while (1)
      {
          if (Cur->key == Item)
          {
              return true;
          }
          if (Cur->key < Item)
          {
              if (Cur->RNode == NULL)
                  return false;
              Cur = Cur->RNode;
          }
          else
          {
              if (Cur->LNode == NULL)
                  return false;
              Cur = Cur->LNode;
          }
          
      }
  }

  값이 있는지 없는지를 확인하는 함수입니다. 있을떄 true를 반환하고 없으면 false를 반환하게 됩니다.
  
  

• void Add_Node()
  
  

  void Add_Node(Tree *Target_Tree, int Item)
  {
      TreeNode *NewNode = (TreeNode *)malloc(sizeof(TreeNode));
      if (Target_Tree->Root == NULL)
      {
          Target_Tree->Root = NewNode;
          NewNode->LNode = NULL;
          NewNode->RNode = NULL;
          NewNode->key = Item;
          return;
      }
      if (Is_There(Target_Tree, Item))
      {
          printf("이미 존재 하는 값입니다.\n");
          return;
      }
      NewNode->LNode = NULL;
      NewNode->RNode = NULL;
      NewNode->key = Item;
      TreeNode *Cur = Target_Tree->Root;
      while (1)
      {
          if (Cur->key < Item)
          {
              if (Cur->RNode == NULL)
              {
                  Cur->RNode = NewNode;
                  return;
              }
              Cur = Cur->RNode;
          }
          else
          {
              if (Cur->LNode == NULL)
              {
                  Cur->LNode = NewNode;
                  return;
              }
              Cur = Cur->LNode;
          }
      }
  }

  값을 추가하는 함수입니다. 기준 보다 크면 오른쪽으로 기준보다 작으면 왼쪽으로 가며 탐색해서 실패하면 그 자리에 추가를 하게됩니다.
  
  

• Delete_Node()
  
  

  int Delete_Node(Tree *Target_Tree, int Item)
  {
      TreeNode *Cur2=NULL;
      TreeNode *Cur = Target_Tree->Root;
      TreeNode *Par_Parent=NULL;
      TreeNode *Parent=NULL;
      TreeNode *Child=NULL;
      TreeNode *Left_Temp = NULL;
      int Key_return = 0;
      if (!Is_There(Target_Tree, Item))
      {
          printf("없는 값입니다.\n");
          return 0;
      }
      while (Cur->key != Item)
      {
          if (Item > Cur->key)
          {
              Par_Parent = Parent;
              Parent = Cur;
              Cur = Cur->RNode;
          }
          else
          {
              Par_Parent = Parent;
              Parent = Cur;
              Cur = Cur->LNode;
          }
      }//특정 값 까지 이동
      if (Cur->LNode == NULL&&Cur->RNode == NULL)//터미널 노드일 때
      {
          Key_return = Cur->key;
          if (Parent->LNode == Cur)
              Parent->LNode = NULL;
          if (Parent->RNode == Cur)
              Parent->RNode = NULL;
          free(Cur);
          return Key_return;
      }
   
      if (Cur->LNode == NULL || Cur->RNode == NULL)//지우려는 값 아래에 1개의 자식이 있을 때
      {
          Child = (Cur->LNode != NULL) ? Cur->LNode : Cur->RNode;
   
          if (Parent->LNode == Cur)//지우려는 값의 부모 의 어느자식이 지우려는 값인지?
              Parent->LNode = Child;
          else
              Parent->RNode = Child;
          Key_return = Cur->key;
          free(Cur);
          return Key_return;
      }
   
      if (Cur->LNode != NULL&&Cur->RNode != NULL)//지우려는 값 아래에 2개 자식이 있을 때
      {
          Cur2 = Cur;
          Cur2 = Cur2->RNode;
          if (Cur2->LNode == NULL)//오른쪽 한칸 이동 후 왼쪽에 노드가 없을 때 
          {
              Left_Temp = Cur->LNode;
              Child = Cur2;
              if (Parent->RNode == Cur)
              {
                  Parent->RNode = Child;
                  Child->LNode = Left_Temp;
              }
              else
              if (Parent->LNode == Cur)
              {
                  Parent->LNode = Child;
                  Child->LNode = Left_Temp;
              }
              Key_return = Cur->key;
              free(Cur);
              return Key_return;
          }
          while (Cur2->LNode != NULL)//오른쪽 한칸 이동후 왼쪽에 노드가 있을 때
          {
              Parent = Cur2;
              Cur2 = Cur2->LNode;
          }
          Parent->LNode = NULL;
          Cur->key = Cur2->key;
          free(Cur2);
      }
      return 0;
  }

  삭제하는 연산입니다. 자식의 개수에 따라서 3가지로 나누기 때문에 소스가 좀 길어졌습니다.