[자료구조] 이진 탐색 트리 (BST, Binary Search Tree)

목차

이진 탐색 트리 (BST, Binary Search Tree)

---

이진 탐색 트리란 정렬된 이진트리로써 다음과 같은 속성을 가지고 있습니다.

• 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가있는 노드 만 포함됩니다
• 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가있는 노드 만 포함됩니다.
• 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리 여야합니다.
• 중복된 키를 허용하지 않습니다.

이진 탐색 트리 (BST, Binary Search Tree)

이러한 이진 탐색 트리의 특성 때문에 효율적인 검색이 가능합니다.

 

생성 예시

50, 15, 62, 80, 7, 54, 11

주어진 요소를 사용하여 BST를 생성하는 과정은 다음과 같습니다.

1. 50을 트리의 루트로 트리에 삽입합니다.
2. 다음 요소를 읽고 루트 노드 요소보다 작 으면 왼쪽 하위 트리의 루트로 삽입합니다.
3. 그렇지 않으면 오른쪽 하위 트리의 오른쪽 루트로 삽입합니다.

BST 삽입 과정

이진 탐색 트리의 특징

---

1. BST의 Inorder Traversal을 수행하여 모든 키를 정렬된 순서로 가져올 수 있습니다.

위 트리에 inorder traversal 결과는 다음과 같습니다.

7, 11, 15, 50, 54, 62, 80

 

2. BST의 검색에 대한 시간복잡도는 균형 상태이면 O(logN)의 시간이 걸리고 불균형 상태라면 최대 O(N) 시간이 걸립니다.

이진트리의 연산

---

검색 (Search)

이진 탐색 트리에서 특정 요소의 위치를 찾습니다.

 

검색 과정은 다음과 같습니다.

1. 루트에서 시작합니다.
2. 검색 값을 루트와 비교합니다. 루트보다 작으면 왼쪽에 대해 재귀하고 크다면 오른쪽으로 재귀합니다.
3. 일치하는 값을 찾을 때까지 절차를 반복합니다.
4. 검색 값이 없으면 null을 반환합니다.

key=60을 찾는 과정

BST Search

구현

struct node* search (struct node* root, int key)
{
// root값이 null이거나 key값과 같다면 종료한다.
  if (root == NULL || root->data == key)
    return root;

// key가 root->data 보다 작으면 왼쪽 서브트리로 재귀한다.
  if (root->data > key)
    return search(root->left, key)

// key가 root->data 보다 크면 오른쪽 서브트리로 재귀한다. 
  return search(root->left, key)
}

삽입 (insert)

이진 검색트리에 데이터를 삽입하는 작업을 합니다. (중복은 형용하지 않습니다.)

새 키는 항상 리프 노드에 삽입됩니다.

 

삽입 과정은 다음과 같습니다.

1. Root에서 시작합니다.
2. 삽입 값을 루트와 비교합니다. 루트보다 작으면 왼쪽으로 재귀하고 크다면 오른쪽으로 재귀합니다.
3. 리프 노드에 도달한 후 노드보다 크다면 오른쪽에 작다면 왼쪽에 삽입합니다.

BST insert

구현

struct node {
  int data;
  struct node *left, *right;
};

// 새로운 BST node 생성
struct node* newNode (int key) {
  struct node* temp = (struct *node)malloc(sizeof(struct node));
  temp->data = key;
  temp->left = NULL;
  temp->right = NULL;
  return temp;
}

struct node* insert(struct node *root, int key) {
  // 트리가 비어있다면 새로운 노드를 만든다.
  if (root == NULL)
    return newNode(key);

  // 루트값보다 크면 오른쪽으로 재귀하고, 작다면 왼쪽으로 재귀한다.
  if (key > root->data)
    root->right = insert(root->right, key);
  else if (key < root->data)
    root->left = insert(root->left, key); 
  // 같은 값을 가지고 있는 경우 삽입을 하지 않는다.(중복 불가)
  return root;
}

삭제 (Delete)

이진 검색 트리에서 특정 노드를 삭제합니다. 이진 검색 트리에서 노드를 삭제하는 세 가지 상황이 있습니다.

 

1. 삭제할 노드가 리프노드인 경우

이 경우 노드를 삭제하기만 하면 됩니다.

삭제할 노드가 리프노드인 경우

2. 삭제할 노드에 자식이 하나만 있는 경우

노드를 삭제하고 자식 노드를 삭제된 노드의 부모에 직접 연결합니다.

삭제할 노드에 자식이 하나만 있는 경우

3. 삭제할 노드에 자식이 둘 있는 경우

자식이 둘 있는 경우 successor 노드를 찾는 과정이 추가됩니다.

 

surrcessor 노드란

• right subtree에 최소값
• 즉, inorder 순회에서 다음 노드를 말합니다.

삭제 과정은 다음과 같습니다.

1. 삭제할 노드를 찾습니다.
2. 삭제할 노드의 successor 노드를 찾습니다.
3. 삭제할 노드와 successor 노드의 값을 바꿉니다.
4. successor 노드를 삭제합니다.

삭제할 노드에 자식이 둘 있는 경우

구현

struct node {
  int data;
  struct node *left, *right;
};

// 노드의 최소값을 가져오는 함수
struct node* minValueNode (struct node* node){
  struct node* current = node;
  
  while(current && current->left != NULL)
    current = current->left;

  return current;
}

struct node* deleteNode (struct node* root, int key) {
// base case  
  if(root == NULL)
    return root;
// 삭제할 노드를 찾는다.    
  if (key < root->data)
    root->left = deleteNode(root->left,key);

  else if (key > root->data)
    root->right = deleteNode(root->right, key);

// 삭제할 노드를 찾은 경우
  else {
    struct node* temp;
// 노드에 자식이 하나 이거나 없는 경우
    if (root->left == NULL) {
      temp = root->right;
      free(root);
      return temp;
    }
    else if (root->right == NULL) {
      temp = root->left;
      free(root);
      return temp;
    }

// 노드에 자식이 둘 있는 경우
// successor 노드를 찾는다.
    temp = minValueNode(root->right);
// successor 노드 키와 삭제할 노드 키를 바꾼다.
    root->key = temp->key;
// 노드를 삭제한다.
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}