[DS] 9. 이진 탐색 트리

이진 탐색 트리의 개념과 성질, 탐색 / 삽입 / 삭제 연산, 구현 등

Posted Aug 28, 2026

By SDTR

20 min read

[DS] 9. 이진 탐색 트리

탐색(Search)?

레코드의 집합에서 특정한 레코드를 찾아내는 작업.

탐색은 여러 데이터 중 주어진 조건에 맞는 데이터를 찾는 작업이다.

용어	설명
테이블(Table)	여러 레코드로 구성된 집합.
레코드(Record)	하나의 대상을 표현하는 관련 데이터들의 집합.
키(Key)	각각의 레코드를 식별하기 위해 사용하는 필드.
필드(Field)	레코드를 구성하는 각각의 데이터 항목.

예시로 학생들의 정보가 담긴 테이블에서 특정 학생을 탐색한다고 가정했을 때, 학생들의 학번과 같이 중복되지 않는 고유 필드값이 키가 될 수 있다.

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

이진트리의 각 노드를, 키의 대소 관계에 따라 좌/우를 나눠 배치한 탐색 자료구조.

이진 탐색 트리는 효율적인 탐색을 위해 다음 특성을 가진다.

모든 노드는 유일한 키를 가진다.
왼쪽 서브트리의 모든 키는 현재 노드의 키보다 작다.
오른쪽 서브트리의 모든 키는 현재 노드의 키보다 크다.
왼쪽과 오른쪽 서브트리도 각각 이진 탐색 트리이다.

이 글에서는 모든 키가 유일하며, 중복된 키의 삽입은 허용하지 않는다고 가정한다.

이진 탐색 트리의 특성 상, 중위 순회 시 모든 키를 오름차순으로 탐색할 수 있다.

추상 자료형

데이터 : 이진 탐색 트리의 특성을 만족하는 이진트리.

연산 :

함수	설명
`search(key)`	주어진 키를 가진 노드를 탐색한다.
`insert(value)`	키의 대소 관계에 맞는 위치에 새로운 노드를 삽입한다.
`remove(key)`	주어진 키를 가진 노드를 삭제한다.

탐색 연산

탐색은 루트 노드에서 시작한다.

탐색하려는 키와 현재 노드의 키를 비교하여 탐색 키가 작다면 왼쪽, 크다면 오른쪽 서브트리로 이동한다.

두 키가 같은 경우 해당 노드를 반환하고, 자식 노드가 없는 위치까지 내려갔다면 탐색에 실패한다.

아래는 특정 노드를 인자로 받아, 해당하는 서브트리에서의 특정 키를 갖는 노드를 반환하는 순환 탐색 함수이다.

  
BinaryNode* searchRecur(BinaryNode* node, const T& key)
{
  if (node == nullptr) return nullptr;
  const T& curKey = node->getData();
  
  if (curKey == key)  // 현재 노드가 해당 key를 가질 때.
    return node;
  if (curKey > key)   // 현재 노드보다 key가 더 작을 때. 왼쪽으로.
    return searchRecur(node->getLeft(), key);
  if (curKey < key)   // 현재 노드보다 key가 더 클 때. 오른쪽으로.
    return searchRecur(node->getRight(), key);

  return nullptr;
}

한 번의 비교마다 왼쪽 또는 오른쪽 서브트리 중 하나만 탐색하기에, 탐색에 필요한 비교 횟수는 트리의 높이에 비례한다.

삽입 연산

삽입할 위치를 찾는 과정은 탐색 연산과 동일하다. 당연하게도, 삽입 전에 삽입할 위치를 우선 탐색해야 하기에.

기준 노드로부터 키를 비교하며 왼쪽 또는 오른쪽으로 이동하고, nullptr인 링크를 발견하면 해당 위치에 새로운 노드를 연결한다.

이미 같은 키가 존재한다면 새로운 노드를 삽입하지 않고 false를 반환한다.

  
bool insertRecur(BinaryNode* parent, BinaryNode* node)
{
  if (!parent || !node) return false;
  const T& curKey = parent->getData();
  const T& key    = node->getData();

  if (curKey == key)   // 이미 해당하는 key가 들어있을 때, 삽입 실패.
    return false;
  if (curKey > key)    // key가 더 작음. -> Left가 비면 삽입, 찼으면 Left에서 재탐색
    if (!root->getLeft())  { parent->setLeft(node);  return true; }
    else                   { insertRecur(r->getLeft(), node); }
  if (curKey < key)    // key가 더 큼. -> Right가 비면 삽입, 찼으면 Right에서 재탐색
    if (!root->getRight()) { parent->setRight(node); return true; }
    else                   { insertRecur(r->getRight(), node); }
}

삭제 연산

노드를 삭제할 때는 해당 노드가 가진 자식의 수에 따라 처리 방법이 달라진다.

경우	처리 방법
자식이 없음	노드를 삭제하고 부모의 링크를 `nullptr`로 변경.
자식이 1개	삭제할 노드의 위치에, 그 노드의 자식을 할당.
자식이 2개	중위 선행자 또는 중위 후속자를 이용해 가장 유사한 값을 찾은 뒤, 해당 값을 할당.

단말 노드 삭제

Image Video

bstdeletioncase1-manimce-v0-21-0 — 자식 노드가 없는 단말 노드를 삭제하는 경우

자식 노드가 없는 단말 노드를 삭제하는 경우

단말 노드는 연결된 자식이 없으므로 해당 노드를 바로 삭제할 수 있다. 가장 간단하다.

삭제 이후 빈 자리를 nullptr로 채워주기만 하면 된다.

  
// void remove(BinaryNode* parent, BinaryNode* node) ...
// case 1 : 자식 노드가 없는 단말 노드의 삭제

if (node->isLeaf())   // 단말 노드라면
{ 
  if (!parent)        //  부모가 없다면, 즉 root 노드라면
    root = nullptr;   //   root 노드만 제거
  else                //  부모가 있다면
  {                   //   삭제 후에 빌 자리를, nullptr로 갱신
    if      (parent->getLeft()  == node)
      parent->setLeft(nullptr);
    else if (parent->getRight() == node)
      parent->setRight(nullptr);
    else return;
  }
}
/* case 2... */
/* case 3... */
delete node;
  

자식이 하나인 노드 삭제

Image Video

하나의 자식 노드를 가진 노드를 삭제하는 경우

하나의 자식 노드를 가진 노드를 삭제하는 경우

삭제할 노드의 자식을, 삭제할 노드의 위치로 할당한다. 이 또한 크게 어렵지 않다.

삭제 이전에 자식의 정보를 임시로 저장해두고, 부모를 삭제한 뒤, 새 부모와 자식의 포인터 정보를 갱신해주면 된다.

  
// void remove(BinaryNode* parent, BinaryNode* node) ...
/* case 1... */
// case 2 : 자식 노드가 하나인 노드의 삭제

else if (!node->getLeft || !node->getRight) // 자식이 하나라면
{
  BinaryNode* child = nullptr; // 자식의 정보 임시저장
  child = !node->getLeft() ? node->getLeft() : node->getRight();

  if (node == root)            // 삭제 노드가 root 노드라면, 
    root = child;              //  root를 child로.
  
  else                         // 삭제 노드가 root 노드가 아니라면,
  {                            //  삭제 후에 빌 자리를, 하나뿐인 자식 노드로 갱신
    if      (parent->getLeft()  == node)
      parent->setLeft(child);
    else if (parent->getRight() == node)
      parent->setRight(child);
    else return;
  }
}
/* case 3... */
delete node;
  

자식이 둘인 노드 삭제

Image Video

두 개의 자식 노드를 가진 노드를 삭제하는 경우
(아래 코드에서는 값만을 할당 후 후속자를 삭제함에 유의)

삭제할 노드의 키와 가장 유사한 키를 가진 노드를 찾은 뒤, 해당 노드로 할당한다. 가장 신경써야 할 게 많다.

가장 가까운 키로 교체해야 이진 탐색 트리의 성질이 유지되므로 우선 이 가장 유사한 키를 가진 노드부터 찾아야 하는데, 이는 이진 탐색 트리의 특성에 따라 반드시 증위 선행자 또는 중위 후속자 둘 중 하나가 된다.

구분	위치
중위 선행자	왼쪽 서브트리에서 가장 큰 키를 가진 노드.
중위 후속자	오른쪽 서브트리에서 가장 작은 키를 가진 노드.

이론 상 둘 중 아무거나 선택하여도 상관없다. 아래 코드는 후속자를 기준으로 작성되었다.

  
// void remove(BinaryNode* parent, BinaryNode* node) ...
/* case 1... */
/* case 2... */
// case 3 : 자식 노드가 두 개인 노드의 삭제

else  // 자식이 두 개라면
{
  BinaryNode* targetParent = node;
  BinaryNode* target = node->getRight();

  // 후속자 탐색. 최종적으로 target에는 후속자가 담기게 된다.
  while (!target->getLeft())  
  { 
    targetParent = target;
    target = target->getLeft();
  }
  
  // target을 갱신하기 전, target 노드의 부모 내 자식 정보를 우선 갱신.
  if      (targetParent->getLeft() == target)  // 후속자가 그 부모의 왼쪽 노드라면
    targetParent->setLeft(target->getRight()); //  부모의 그 자리를 후속자의 우측 노드로 채움.
  else if (targetParent->getRight() == target) // 후속자가 그 부모의 오른쪽 노드라면
    targetParent->setRight(target->getRight());//  부모의 그 자리를 후속자의 우측 노드로 채움.

  // target의 값을 삭제 대상 노드에 복사.
  node->setData(target->getData);

  // 삭제 대상을 값을 제공한 노드로 변경.
  // (처음에 지정한 삭제 대상 node가 삭제되는 게 아닌, 해당 node 값만 후속자로 갱신한 뒤 후속자를 제거.)
  node = target;
}

delete node;

여기서, 삭제 대상 node는 실제로 삭제되는 것이 아닌, 후속자로부터 값만 갱신받고 후속자를 제거하는 방식이다. 이 편이 더 간결하기 때문.

물론 후속자 내의 정보와 그 주변 정보들을 모두 갱신한 뒤 삭제 대상 node 자체를 제거해도 되겠으나, 구현은 조금 복잡해질 것이다. 다만 성능에 따라서는 그 편이 더 좋을 수도 있다. 이는 템플릿 변수를 복사하는 비용에 따라 갈릴 것이리라.

이진 탐색 트리의 구현

다음은 탐색, 삽입, 삭제 연산을 포함하는 간단한 이진 탐색 트리의 예제 코드이다.

코드 예제

  
template <typename T>
class BinarySearchTree : public BinaryTree<T>
{
public:
  using Node = BinaryNode<T>;

private:
  Node* searchRecur(Node* node, T key)
  { // 순환 탐색
    if (node == nullptr || key == node->getData())
      return node;

    if (key < node->getData())
      return searchRecur(node->getLeft(), key);

    return searchRecur(node->getRight(), key);
  }

  bool insertRecur(Node* root, Node* node)
  { // 순환 삽입
    if (node->getData() == root->getData())
      return false;

    if (node->getData() < root->getData())
    { // 현재 키보다 작으면 왼쪽 서브트리에 삽입
      if (root->getLeft() == nullptr)
        root->setLeft(node);
      else
        return insertRecur(root->getLeft(), node);
    }
    else
    { // 현재 키보다 크면 오른쪽 서브트리에 삽입
      if (root->getRight() == nullptr)
        root->setRight(node);
      else
        return insertRecur(root->getRight(), node);
    }

    return true;
  }

  void remove(Node* parent, Node* node)
  { // 노드 삭제
    if (node->isLeaf())
    { // 단말 노드인 경우
      if (parent == nullptr)
        this->root = nullptr;
      else if (parent->getLeft() == node)
        parent->setLeft(nullptr);
      else
        parent->setRight(nullptr);
    }
    else if (node->getLeft() == nullptr ||
             node->getRight() == nullptr)
    { // 자식이 하나인 경우
      Node* child = node->getLeft() != nullptr
        ? node->getLeft()
        : node->getRight();

      if (parent == nullptr)
        this->root = child;
      else if (parent->getLeft() == node)
        parent->setLeft(child);
      else
        parent->setRight(child);
    }
    else
    { // 자식이 둘인 경우
      Node* targetParent = node;
      Node* target = node->getRight();

      // 오른쪽 서브트리에서 가장 작은 후속자 탐색
      while (target->getLeft() != nullptr)
      {
        targetParent = target;
        target = target->getLeft();
      }

      // 후속자의 부모와 후속자의 오른쪽 자식 연결
      if (targetParent->getLeft() == target)
        targetParent->setLeft(target->getRight());
      else
        targetParent->setRight(target->getRight());

      // 후속자의 값을 삭제 대상 노드에 복사
      node->setData(target->getData());

      // 실제 삭제 대상은 후속자 노드
      node = target;
    }

    delete node;
  }

public:
  Node* search(T key)
  { // 키 탐색
    return searchRecur(this->root, key);
  }

  bool insert(Node* node)
  { // 노드 삽입
    if (node == nullptr)
      return false;

    if (this->isEmpty())
    {
      this->root = node;
      return true;
    }

    if (insertRecur(this->root, node))
      return true;

    delete node;
    return false;
  }

  bool remove(T key)
  { // 키 삭제
    Node* parent = nullptr;
    Node* node = this->root;

    // 삭제 대상과 부모 노드 탐색
    while (node != nullptr &&
           node->getData() != key)
    {
      parent = node;

      if (key < node->getData())
        node = node->getLeft();
      else
        node = node->getRight();
    }

    if (node == nullptr)
      return false;

    remove(parent, node);
    return true;
  }
};

성능

이진 탐색 트리의 탐색, 삽입, 삭제 연산은 모두 루트에서 시작하여 하나의 경로를 따라 이동한다. 때문에 각 연산의 시간복잡도는 트리의 높이 $h$에 비례한, $O(h)$의 시간복잡도를 가진다.

트리가 균형에 가깝다면 높이는 약 $\log_2 n$이므로 각 연산의 시간복잡도는 $O(\log n)$이나, 트리가 한쪽으로 치우치면 높이가 $n$에 가까워진다.

극단적으로 쏠린 형태의 트리. 이 상태로는 연결 리스트랑 다를게 없다

이 경우 이진 탐색 트리는 연결 리스트와 유사한 구조가 되며, 시간복잡도도 연결 리스트의 선형 탐색과 유사하게 $O(n)$까지 저하된다.

경우	트리 높이	탐색·삽입·삭제
균형에 가까운 경우	$O(\log n)$	$O(\log n)$
한쪽으로 치우친 경우	$O(n)$	$O(n)$

이를 방지하고 일정한 성능을 유지하려면, AVL 트리나 레드-블랙 트리와 같은 방식을 사용할 수 있다.

이진 탐색 트리의 응용

영어 사전

영어 사전의 각 레코드는 영어 단어를 키로 사용하고, 해당 단어의 뜻과 같은 정보를 데이터로 저장할 수 있다.

문자열은 사전 순서로 대소 관계를 비교할 수 있으므로, 이진 탐색 트리를 통해 저장하기 적절하다.

키	데이터
`data`	자료
`list`	리스트
`stack`	스택
`acorn`	도토리
…	…

Computer Science, Data Structure

This post is licensed under CC BY 4.0 by the author.

[DS] 9. 이진 탐색 트리

탐색(Search)?

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

추상 자료형

탐색 연산

삽입 연산

삭제 연산

단말 노드 삭제

자식이 하나인 노드 삭제

자식이 둘인 노드 삭제

이진 탐색 트리의 구현

성능

이진 탐색 트리의 응용

영어 사전

댓글

Trending Tags