주니어 백엔드 개발자 인터뷰

# 이진 탐색 트리 (BST)

정의

이진 탐색 트리는 노드의 오른쪽 하위 트리에는 '노드 값보다 큰 값'이 있는 노드만 포함되고, 왼쪽 하위 트리에는 '노드 값보다 작은 값'이 들어 있는 트리를 말합니다.

image

  • 왼쪽 및 오른쪽 서브 트리도 해당 특성을 가집니다.
  • 탐색의 시간 복잡도는 O(logN)이며, 최악의 경우 편향 트리가 되어 O(N)이 될 수도 있습니다.
  • 이진 탐색 트리의 순회는 중위 순회(in order) 방식입니다.(왼쪽 - 루트 - 오른쪽)
  • 값은 키값을 갖는 노드는 없습니다.
    • 검색을 목적으로 하는 자료구조이기에, 중복이 많은 경우에 이 트리를 사용하도록 하여 검색 속도를 느리게 할 필요가 없습니다.
    • 트리에 삽입하는 것보다 노드에 count를 가지게 하여 처리하는 것이 훨씬 효율적입니다.

# Successor와 Predecessor

# Successor

  • 임의의 루트노드 x가 존재할 때 x보다 큰 값으로 이루어진 서브트리의 값 중 가장 작은 키 값을 의미합니다.
  • right subtree의 최소값입니다.

# Predecessor

  • 임의의 루트노드 x가 존재할 때 x보다 작은 값으로 이루어진 서브트리의 값 중 가장 큰 키 값을 의미합니다.
  • left subtree의 최대값입니다.

# BST 생성하기

50, 15, 62, 80, 7, 54, 11의 순서대로 BST를 생성해보자.

image

  • 첫번째 요소를 트리의 루트로 트리에 삽입합니다.
  • 다음 요소를 읽고 루트 노드 요소보다 작 으면 왼쪽 하위 트리의 루트로 삽입합니다.
  • 그렇지 않으면 오른쪽 하위 트리의 오른쪽 루트로 삽입합니다.
구현하기 
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;
}

# BST에서 탐색하기

아래의 트리에서 60이라는 요소를 찾아봅시다.

image

  • 루트에서 시작합니다.
  • 검색 값을 루트와 비교합니다. 루트보다 작으면 왼쪽에 대해 재귀하고 크다면 오른쪽으로 재귀합니다.
  • 일치하는 값을 찾을 때까지 절차를 반복합니다.
  • 검색 값이 없으면 null을 반환합니다.
구현하기 
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)
}

# BST에 요소를 삽입하기

아래의 트리에 10이라는 요소를 삽입해봅시다.

image

  • Root에서 시작합니다.
  • 삽입 값을 루트와 비교합니다. 루트보다 작으면 왼쪽으로 재귀하고 크다면 오른쪽으로 재귀합니다.
  • 리프 노드에 도달한 후 노드보다 크다면 오른쪽에 작다면 왼쪽에 삽입합니다.
구현하기 
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;
}

# BST의 값을 삭제하기

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

아래의 트리에 1이라는 요소를 삭제해봅시다.

image

  • 그냥 단순히 말단 노드만 지우면 되기에 간편합니다.

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

아래의 트리에서 30이라는 요소를 삭제해봅시다.

image

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

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

아래의 트리에서 50이라는 요소를 삭제해봅시다.

image

구현하기 
// 노드의 최소값을 가져오는 함수
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;
}
  • 삭제할 노드를 찾습니다.
  • 삭제할 노드의 successor 노드를 찾습니다.
  • 삭제할 노드와 successor 노드의 값을 바꿉니다.
  • successor 노드를 삭제합니다.

주의

편향된 트리는 시간 복잡도가 O(N) 이므로 트리를 사용할 이유가 존재하지 않게 됩니다.
이를 바로 잡도록 도와주고 개선된 트리는 AVL Tree, RedBlack Tree가 있습니다.

# 참고자료

← AVL 트리 →