[자료 구조] Binary Search Tree(BST)

트리(tree)란 노드(데이터)를 거꾸로 뒤집힌 나무의 모양처럼 저장한 비선형 계층적 자료구조이다.

트리는 다음과 같은 특징을 가지고 있습니다.

• 하나의 루트 노드와 0개 이상의 하위 트리로 구성되어 있습니다.
• 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조입니다.
• 트리내에 또 다른 트리가 있는 재귀적 자료구조입니다.
• 단순 순환(Loop)을 갖지 않고, 연결된 무방향 그래프 구조입니다.
• 노드 간에 부모 자식 관계를 갖고 있는 계층형 자료구조이며 모든 자식 노드는 하나의 부모 노드만 갖습니다.
• 노드가 n개인 트리는 항상 n-1개의 간선(edge)을 가집니다.

트리 자료구조에서 사용하는 기본 용어, 특징, 종류는 아래 링크에 상세히 나와있다.

[자료구조] 트리(Tree)

트리 중 각 노드의 차수(자식 노드)가 2 이하인 트리를 이진 트리(binary tree)라고 하며, 이 중 노드가 순서대로 정렬되어 있는 자료 구조 형태를 이진 탐색 트리(binary search tree)라고 한다.

이진 트리의 분류 및 특성에 대한 자세한 내용은 아래 링크에서 확인할 수 있다.
[자료구조] 이진 트리(Binary tree) 알아보기

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

이진 탐색 트리는 이진 탐색(binary search)의 효율적인 탐색 방식을 사용하면서, 연결 리스트(linked list)로 삽입, 삭제를 용이하게 만든 자료 구조이다.

예컨대 이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(logn)으로 빠르지만 자료 입력, 삭제가 불가능합니다. 연결리스트의 경우 자료 입력, 삭제에 필요한 계산복잡성은 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 계산복잡성이 발생합니다. 두 마리 토끼를 잡아보자는 것이 이진탐색트리의 목적입니다.

이진 탐색 트리의 속성은 다음과 같다.

• 각 노드의 왼쪽 서브 트리에는 해당 노드보다 작은 값(키)을 가진 노드만 포함된다.
• 각 노드의 오른쪽 서브 트리에는 해당 노드보다 큰 값(키)을 가진 노드만 포함된다.
• 모든 서브 트리 또한 이진 탐색 트리이다.
• 중복된 값(키)를 허용하지 않는다.

이진 탐색 트리의 특성

Inorder traversal로 정렬할 수 있다.
Inorder traversal이란 left-root-right 순서로 순회하는 것을 말하며, 위 이진 탐색 트리에서 1->3->4->6->7->8->10->13->14 순으로 순회한다.

Depth First Traversals (DFS algorithm으로 구현)

• Inorder traversal(Left-Root-Right): 1->3->4->6->7->8->10->13->14
• Preorder traversal(Root-Left-Right): 8->3->1->6->4->7->10->14->13
• Postorder traversal(Left-Right-Root): 1->4->7->6->3->13->14->10->8

Breath First or Level Order Traversal: 8->3->10->1->6->14->4->7->13

탐색에 대한 시간복잡도는 균형 상태일 때 O(logN), 불균형 상태일 때 최대 O(N)이다.

• (최소 높이가 1인 경우) 이진 트리에서 노드가 N개 있을 때 트리의 높이 h는 최소 log(N+1)이다. 트리에서 탐색의 시간 복잡도는 O(h)이며, 트리가 균형 상태일 때 최소 높이를 가지기 때문에 시간 복잡도가 O(logN)이 되고, skewed tree의 경우 h=N이 되어 시간 복잡도가 O(N)으로 최대가 된다.

탐색

이진 탐색 트리에서의 탐색 과정은 아래와 같다.

1. 루트에서 탐색을 시작한다. 검색값이 루트보다 작으면 왼쪽 서브 트리, 크면 오른쪽 서브 트리로 이동한다.
2. 해당 서브 트리에서 1번 탐색 과정을 진행한다.
3. 일치하는 값을 찾을 때까지 반복하며, 검색값이 없다면 null을 반환한다.

이진 탐색 트리의 높이가 h일 때, 탐색의 시간 복잡도는 O(h)이다.

삽입

이진 탐색 트리에서의 삽입 과정은 아래와 같다.

1. 루트 노드의 값과 삽입 값을 비교한다. 삽입 값이 루트 노드의 값보다 작으면 왼쪽 서브 트리, 크면 오른쪽 서브 트리로 이동한다.
2. 리프 노드에 도달할 때까지 반복하며, 리프 노드에 도달한 후 해당 노드의 값보다 작으면 왼쪽 자식 노드에, 크면 오른쪽 자식 노드에 삽입한다.

이진 탐색 트리의 높이가 h일 때, 삽입의 시간 복잡도는 O(h)이다.

삭제

이진 탐색 트리에서 삭제를 자칫 잘못 했다가 이진 탐색 트리의 속성을 깰 수 있기 때문에, 세 가지 상황으로 분류하여 각기 다른 과정으로 진행해야 한다.

case 1. 삭제할 노드가 리프노드인 경우
해당 노드를 그냥 삭제하면 된다.

case 2. 삭제할 노드에 자식이 하나 있는 경우
해당 노드를 삭제하고 그 노드의 부모 노드와 자식 노드를 연결하면 된다.

case 3. 삭제할 노드에 자식이 둘 있는 경우
이 경우에는 successor 노드를 찾는 과정이 필요하다. successor 노드란 삭제할 노드의 오른쪽 서브 트리의 최솟값, 즉 inorder traversal에서 삭제할 노드 바로 다음 노드를 의미한다.

삭제 과정은 아래와 같다.

1. 삭제할 노드와 그 노드의 오른쪽 서브 트리를 찾는다.
2. successor 노드를 찾는다.
3. 삭제할 노드와 successor 노드의 자리를 바꾼다. (또는, 삭제할 노드에 successor 노드를 복사해도 된다.)
4. 기존 successor 자리에 있는 노드를 삭제한다.

이진 탐색 트리의 높이가 h일 때, 삭제의 시간 복잡도는 O(h)이다.

추가로 공부해야 할 내용

1. AVL tree
   AVL 트리(Tree)

2. m-way search tree

참고 링크

이진탐색트리(Binary Search Tree)
Tree Traversals (Inorder, Preorder and Postorder)
[자료구조] 이진 탐색 트리(BST, Binary Search Tree)