이진 탐색 트리

오늘은 이진 탐색 트리(Binary Search Tree)의 구조와 검색, 삽입, 삭제 동작을 예시 트리와 함께 정리하도록 하겠습니다.

이진 탐색 트리의 특징

이진 탐색 트리에서 각 노드는 값을 하나씩 가지며, 왼쪽 자식 노드의 값은 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값은 부모 노드의 값보다 큽니다. 예시 트리는 아래와 같습니다.

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

각 노드의 값은 트리 안에서 노드를 찾을 때 비교하는 기준이 됩니다. 위 트리는 다음과 같이 나눌 수 있습니다.

• 루트 노드: 값 8
• 왼쪽 서브트리: 값 3, 1, 6, 4, 7
• 오른쪽 서브트리: 값 10, 14, 13

검색, 삽입, 삭제

위 트리를 기준으로 각 작업이 어떻게 진행되는지 정리하면 아래와 같습니다.

1. 검색: 값 7을 검색하는 경우입니다. 루트 노드에서 시작합니다. 루트 노드의 값은 8이고 7은 8보다 작으므로 왼쪽 자식인 3 노드로 이동합니다. 7은 3보다 크므로 오른쪽 자식인 6 노드로 이동하고, 7은 6보다 크므로 다시 오른쪽으로 이동해 7을 찾게 됩니다.
2. 삽입: 값 5를 삽입하는 경우입니다. 루트 노드에서 시작합니다. 5는 8보다 작으므로 왼쪽의 3 노드로 이동하고, 3보다 크므로 오른쪽의 6 노드로 이동합니다. 5는 6보다 작으므로 왼쪽의 4 노드로 이동하고, 4보다 크므로 4 노드의 오른쪽 자식으로 삽입합니다.
3. 삭제: 값 3을 삭제하는 경우입니다. 먼저 삭제할 노드를 찾습니다. 3은 루트 노드의 왼쪽 서브트리에 있습니다. 3 노드는 자식 노드가 두 개(1, 6)이므로, 오른쪽 서브트리에서 가장 작은 값인 4를 3 자리로 옮기고 원래 4 노드를 삭제합니다. 4 노드는 자식이 없으므로 그대로 떼어 내면 됩니다. 삭제할 노드의 자식이 하나뿐이라면 그 자식 노드를 부모 노드에 바로 연결하고, 자식이 없다면 노드만 삭제합니다.

이렇게 이진 탐색 트리는 값을 비교하며 한쪽 서브트리로만 내려가기 때문에 검색, 삽입, 삭제를 효율적으로 수행할 수 있는 자료 구조입니다. 다만 값이 정렬된 순서로 들어오면 트리가 한쪽으로 치우쳐 효율이 떨어지므로, 균형을 유지하는 트리 구조를 사용하는 것이 중요합니다. 균형을 유지하는 트리의 예로 데이터베이스 인덱스에서 사용하는 B-tree가 있습니다.

마무리

오늘은 이진 탐색 트리의 구조와 검색, 삽입, 삭제 동작에 대해 정리하였습니다.