[자료구조] BST(Binary Search Tree) 이진 탐색 트리 - CS면접 대비

이번 글에서는 탐색, 삽입, 삭제 연산에서 탁월한 성능을 보이는 BST(Binary Search Tree)에 관한 내용을 정리해보고자 한다. 1부터 100까지의 수 중 임의의 수 하나를 맞히는 게임을 한다고 가정해보자. 직관적으로 생각했을 때 가운데 값인 50을 가장 먼저 말하고 맞히려는 수가 그보다 큰 경우 75를 작은 경우 25를 외치는 식으로 답을 찾는 게 가장 효율적인 방법일 것이다. 이진 탐색 트리는 이와 유사한 방식으로 자료 탐색이 가능한 이진 트리 자료구조라고 할 수 있다.

---

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

---

[1] 이진 탐색 트리(BST)의 정의

이진 탐색 트리(BST)는 이진 트리로서 공백일 수 있으며, 만약 공백이 아니라면 다음 성질을 만족한다.

• 모든 원소는 키를 가지며, 어떤 두 원소도 동일한 키를 갖지 않는다.(즉, 모든 키는 상이하다)
• 왼쪽 서브트리에 있는 키들은 그 루트의 키보다 작다
• 오른쪽 서브트리에 있는 키들은 그 루트의 키보다 크다
• 왼쪽과 오른쪽 서브트리도 모두 이진 탐색 트리이다.

이진 탐색 트리 예시

---

[2] 이진 탐색 트리(BST)의 탐색 : O(h)  * h : height(트리의 높이)

1. 루트가 Null 이면 찾는 값이 존재하지 않음
2. 찾고자 하는 Key 값이 루트의 Key 와 같다면 탐색 종료
3. 찾고자 하는 Key 값이 루트의 Key 보다 작은 경우 왼쪽 서브트리 탐색
4. 찾고자 하는 Key 값이 루트의 Key 보다 작은 경우 오른쪽 서브트리 탐색

BST 탐색은 Recursion과 Iterate로 모두 구현 가능하며, 트리의 높이가 h라고 했을 때, 시간복잡도는 O(h)로 같고 Recursion의 경우 O(h) 스택공간을 추가적으로 사용한다.

 

---

[3] 이진 탐색 트리(BST)의 삽입 : O(h)

1. modifiedSearch()를 이용, 만약 트리가 공백이거나 삽입하려는 키 k가 존재하면 NULL을 반환하고, 그렇지 안다면 마지막으로 검사한 노드에 대한 포인터를 반환한다.
2. 새로 삽입하려는 k가 반환된 포인터의 key값 보다 작은 경우 이 노드의 leftChild로 삽입하고,
3. 큰 경우 이 노드의 rightChild로 삽입한다.

위와 같이 삽입 연산을 수행할 때, 삽입할 위치를 탐색하는데 필요한 시간은 O(h)이고, 나머지 부분은 O(1) 시간을 필요로 한다. 따라서 BST 삽입 연산에 필요한 전체 시간은 O(h) 이다.

---

[4] 이진 탐색 트리(BST)의 삭제 : O(h)

1) 삭제하려는 노드가 리프에 위치한 경우

• 해당 노드 부모의 자식 필드(왼쪽 혹은 오른쪽)를 NULL로 만들고 노드를 반환

2) 리프에 위치하지 않은 경우

• 해당 노드가 하나의 자식만 가지고 있는 경우
  1. 해당 노드를 반환한다.
  2. 해당 노드의 자식 노드를 반환된 노드 자리에 위치시킨다. (삭제된 노드의 부모 노드의 자식 포인터가 삭제된 노드의 자식 노드를 가리키도록 변경해준다.)
• 해당 노드가 두 개의 자식을 가진 경우
  1. 해당 노드를 반환한다.
  2. 왼쪽 서브 트리에서 가장 큰 원소이거나 오른쪽 트리에서 가장 작은 원소로 대체한다. 이 때 대체되는 노드는 항상 차수가 1이거나 0이므로 대체는 간단하다. 구체적으로, 왼쪽에서 제일 큰 값으로 대체하는 경우 해당 노드는 자식이 없거나 왼쪽 자식만을 가지고, 오른쪽 서브 트리에서 제일 작은 값으로 대체하는 경우 해당 노드는 자식이 없거나 오른쪽 자식만 가진다. 따라서, 자식이 없는 경우 리프에서의 삭제와 마찬가지로 대체만 해주면 되고, 자식이 하나 있는 경우 해당 노드의 부모 노드 자식 포인터 값만 대체 노드의 자식 노드로 바꿔주면 된다.

이진 탐색 트리의 삭제 연산

 

---

[5] 이진 탐색 트리(BST)의 높이 문제와 Balanced Search Tree

 

n개의 원소를 가진 BST의 높이는 최대 n만큼 커질 수 있다. 예를 들어, 공백인 초기 BST에 정렬된 수 1,2,3,...,n을 차례로 삽입하는 경우를 생각해보자. 아래 그림과 같은 BST가 만들어질 것이다. 그러나 삽입 삭제가 무작위로 이루어 질 때 평균적인 BST의 높이는 O(log N)이 된다.

편향된 이진 탐색 트리의 모습

 

최악의 경우에도 높이가 O(log N)이 되는 탐색 트리를 균형 탐색 트리(Balanced Search Tree)라 한다. 이들 중 탐색, 삽입, 삭제를 O(h) 시간에 할 수 있는 것들도 있으며, 가장 널리 알려진 균형 탐색 트리로는 AVL, red-black, 2-3, 2-3-4, B-트리, B+-트리 등이 있다.