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

 

정의

In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree. A binary tree is a type of data structure for storing data such as numbers in an organized way. Binary search trees allow binary search for fast lookup, addition and removal of data items, and can be used to implement dynamic sets and lookup tables. The order of nodes in a BST means that each comparison skips about half of the remaining tree, so the whole lookup takes time proportional to the binary logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash tables. Several variants of the binary search tree have been studied.

-wikipedia

 

 

이진 탐색 트리(Binary Search tree)는 이진 트리이면서, 다음과 같은 조건을 만족한다.

• 각 노드에 값이 있다
• 값들은 전순서가 있다
• 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다
• 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다
• 좌위 하위 트리는 각각이 다시 이진 탐색 트리이다

 

기존 이진 탐색 알고리즘은 탐색에는 O(logn)이라는 준수한 시간 복잡도를 가지고 있지만, 배열로 이루어져 있을 경우 삽입과 삭제 연산에서 시간 복잡도가 O(n)이라 비효율적인 면이 있다. 이것이 개선되어 삽입, 삭제 과정도 더 적은 시간 복잡도 안에 끝낼수 있도록 고안된 것이 이진 탐색 트리이다.(물론 이 과정들은 경사진 이진 탐색 트리에서 최대 O(n)의 시간 복잡도를 가진다. 이를 방지하기 위해 스스로 균형을 잡는 AVL트리 등이 있다) 완전 이진 트리가 아닐 수 있기 때문에 연결 리스트 등으로 구현하곤 한다.

 

순회

이진 탐색 트리를 중위(inorder)순회 하면 정렬된 값들을 얻을 수 있다.

 

 

이 이진 탐색 트리를 중위 순회 하면 1 2 4 6 8 9 를 얻을 수 있다.

 

주요 함수

탐색(Search)

 

 

먼저 위와 같이 생긴 이진 탐색 트리가 있다고 가정하고, 여기서 4를 탐색한다.

 

 

 

루트 노드부터 시작하여 찾는 수 4가 해당 노드의 값보다 작다면 왼쪽으로, 크다면 오른쪽으로 이동하여 값을 찾는다.

만약 잎새 노드에까지 도달했는데 해당 수를 찾지 못했다면 트리에 존재하지 않는 수 이다.

 

시간 복잡도는 이진 탐색 트리가 얼마나 균형이 잘 잡혔는지에 따라 다르다. 최악의 경우로 잎새 노드까지 탐색할 경우 O(h)의 시간이 소요된다.

삽입(Insert)

 

 

 

여기에서 5를 삽입한다고 하면

 

 

 

이렇게 탐색과정처럼 루트노드부터 값을 비교하면서 잎새 노드까지 내려간다. 이후 잎새 노드와 비교해서 맞는 자리에 노드를 추가해 주기만 하면 된다.

 

시간 복잡도는 탐색 과정과 같다고 볼 수 있다. 삽입 과정에서 더 추가되는 복잡도는 O(1)으로 매우 미미하기 때문이다.

 

삭제(Delete)

 

삭제 과정이 조금 복잡할 수 있다. 그냥 삭제했다간 이진 탐색 트리의 속성이 깨질 수도 있기 때문이다.

 

 

 

여기서 삭제를 할 때, 3가지 경우가 있다.

• 삭제할 노드의 자식 노드가 없는 경우(잎새 노드를 삭제할 경우)
• 삭제할 노드의 자식 노드가 하나 있을 경우
• 삭제할 노드의 자식 노드가 둘 있을 경우

 

먼저 첫번째 경우, 삭제할 노드가 잎새 노드일 때를 가정하여 1을 삭제한다고 하면,

 

 

 

그냥 삭제하면 된다. 잎새 노드일 경우 특별한 것은 없다.

 

두번째 경우, 삭제할 노드의 자식 노드가 하나 있을 때를 가정하여 9를 삭제한다고 하면,

 

 

 

해당 노드를 삭제한 후 유일한 자식 노드를 가져와서 그 자리를 주면 된다. 하위 트리는 어짜피 이진 탐색 트리이기 때문에 그냥 갖다 붙여도 된다.

 

마지막으로 삭제할 노드의 자식 노드가 둘 있을 경우에는, 대칭적인 두 가지 방법이 있다.

 

 

 

이렇게 생긴 이진 탐색 트리에서 2를 삭제한다고 하면, 2에는 두 자식이 있다.

 

이때 2의 왼쪽 서브트리의 최댓값을 predecessor 라고 하고, 2의 오른쪽 서브트리의 최솟값을 successor라고 한다. 여기서는 각각 1과 3이라고 할 수 있다.

 

predecessor 가져오기

 

그림은 predecessor를 가져오는 과정이다. successor를 가져온다고 해도 과정은 동일하다. 2를 삭제하고 1 대신 3을 가져오면 된다.

 

시간 복잡도는 탐색, 삽입 과정과 같다고 볼 수 있다.

 

구현

C++

#include <iostream>
#include <vector>
using namespace std;

struct Node{
  Node* left;
  Node* right;
  Node* par;
  int value;

  Node(){
    left = NULL;
    right = NULL;
    par = NULL;
  }
};

class BinarySearchTree{
  Node* root;
  int size;

public:
  BinarySearchTree(){
    root = NULL;
    size = 0;
  }

  void insert(int value){
    Node* newNode = new Node();
    newNode->value = value;

    if (root == NULL){
      root = newNode;
    } else {
      Node* cur = root;
      Node* par = NULL;

      while (cur){
        par = cur;
        if (value > cur->value) cur = cur->right;
        else cur = cur->left;
      }

      newNode->par = par;
      if (value > par->value) par->right = newNode;
      else par->left = newNode;
    }

    size++;
  }

  Node* search(int value){
    Node* ptr = root;
    while (ptr){
      if (value > ptr->value) ptr = ptr->right;
      else if (value < ptr->value) ptr = ptr->left;
      else return ptr;
    }

    return NULL;
  }

  int getDepth(int value){
    Node* ptr = root;
    int depth = 0;

    while (ptr){
      if (value > ptr->value) ptr = ptr->right;
      else if (value < ptr->value) ptr = ptr->left;
      else break;
      depth++;
    }

    return depth;
  }

  void del(int value){
    Node* target = search(value);
    Node* par = target->par;
    if (!target->left && !target->right){
      if (target != root){
        par->left == target ? par->left = NULL : par->right = NULL;
      } else {
        root = NULL;
      }
    } else if (!target->left){
      if (target != root){
        par->left == target ? par->left = target->right : par->right = target->right;

        target->right->par = par;
      } else {
        root = root->right;
      }
    } else if (!target->right){
      if (target != root){
        par->left == target ? par->left = target->left : par->right = target->left;

        target->left->par = par;
      } else {
        root = root->left;
      }
    } else {
      Node* ptr = target->right;
      while(ptr->left) ptr = ptr->left;
      del(ptr->value);
      size++;
      target->value = ptr->value;
    }
    size--;
  }

  void inOrder(Node* node,vector<int>* v){
    if (node->left) inOrder(node->left,v);
    v->push_back(node->value);
    if (node->right) inOrder(node->right,v);
  }

  Node* getRoot() { return this->root; }
  int getSize() {return size;}
};