개념
주어진 이진 탐색 트리(Binary Search Tree, BST)에서 중앙값(median)을 구하는 것이 우리의 과제입니다.
노드의 개수에 따라 중앙값은 다음과 같이 정의됩니다.
노드 수가 짝수일 때: 중앙값 = ((n/2번째 노드 + (n+1)/2번째 노드) / 2
노드 수가 홀수일 때: 중앙값 = (n+1)/2번째 노드
먼저 노드 수가 홀수인 BST의 예를 살펴보겠습니다.
7
/ \
4 9
/ \ / \
2 5 8 10
이 BST의 중위 순회(inorder) 결과는 2, 4, 5, 7, 8, 9, 10이며, 따라서 중앙값은 7입니다.
다음은 노드 수가 짝수인 BST의 예입니다.
7
/ \
4 9
/ \ /
2 5 8
중위 순회 결과는 2, 4, 5, 7, 8, 9이므로, 중앙값은 (5 + 7) / 2 = 6입니다.
접근 방법
BST의 중위 순회 결과는 항상 오름차순으로 정렬되어 있다는 성질을 활용하면, 중위 순회를 수행한 뒤 그 결과에서 중앙값을 찾으면 됩니다. 여기서 핵심 아이디어는 "O(1) 추가 공간으로 BST에서 k번째 작은 원소 찾기" 기법에 기반합니다.
추가 공간 사용이 허용된다면 문제는 매우 간단하지만, 재귀 호출이나 스택을 이용한 중위 순회 역시 공간을 소모하기 때문에 이 문제의 제약 조건에서는 사용할 수 없습니다.
따라서 해결책은 모리스 중위 순회(Morris Inorder Traversal)를 수행하는 것입니다. 모리스 순회는 스레드화(threading) 기법을 통해 임시 링크를 만들고 복원하므로 어떠한 추가 공간도 필요로 하지 않습니다.
모리스 중위 순회의 동작 방식은 다음과 같습니다.
- current를 루트 노드로 초기화합니다.
- current가 NULL이 아닌 동안 반복합니다.
- current에 왼쪽 자식이 없다면:
- current의 데이터를 방문(출력)합니다.
- 오른쪽으로 이동합니다. 즉, current = current->right
- current에 왼쪽 자식이 있다면:
- current의 왼쪽 서브트리에서 가장 오른쪽에 있는 노드(중위 선행자)를 찾아, 그 노드의 오른쪽 자식을 current로 연결합니다.
- 왼쪽 자식으로 이동합니다. 즉, current = current->left
- current에 왼쪽 자식이 없다면:
전체 구현 전략은 다음 두 단계로 요약할 수 있습니다.
- 1단계: 모리스 중위 순회를 이용해 주어진 BST의 전체 노드 개수를 셉니다.
- 2단계: 노드 개수를 세면서 모리스 중위 순회를 한 번 더 수행하고, 방문한 노드의 개수가 중앙값 위치와 일치하는지 확인합니다.
노드 수가 짝수인 경우를 처리하기 위해 직전에 방문한 노드(previous node)를 가리키는 추가 포인터 하나를 함께 사용합니다.
예제 코드
/* C++ program to find the median of BST in O(n) time and O(1)
space*/
#include<bits/stdc++.h>
using namespace std;
/* Implements a binary search tree Node1 which has data, pointer
to left child and a pointer to right child */
struct Node1{
int data1;
struct Node1* left1, *right1;
};
//Shows a utility function to create a new BST node
struct Node1 *newNode(int item1){
struct Node1 *temp1 = new Node1;
temp1->data1 = item1;
temp1->left1 = temp1->right1 = NULL;
return temp1;
}
/* Shows a utility function to insert a new node with
given key in BST */
struct Node1* insert(struct Node1* node1, int key1){
/* It has been seen that if the tree is empty, return a new node
*/
if (node1 == NULL) return newNode(key1);
/* Else, recur down the tree */
if (key1 < node1->data1)
node1->left1 = insert(node1->left1, key1);
else if (key1 > node1->data1)
node1->right1 = insert(node1->right1, key1);
/* return the (unchanged) node pointer */
return node1;
}
/* Shows function to count nodes in a binary search tree
using Morris Inorder traversal*/
int counNodes(struct Node1 *root1){
struct Node1 *current1, *pre1;
// Used to initialise count of nodes as 0
int count1 = 0;
if (root1 == NULL)
return count1;
current1 = root1;
while (current1 != NULL){
if (current1->left1 == NULL){
// Now count node if its left is NULL
count1++;
// Go to its right
current1 = current1->right1;
} else {
/* Determine the inorder predecessor of current */
pre1 = current1->left1;
while (pre1->right1 != NULL &&
pre1->right1 != current1)
pre1 = pre1->right1;
/* Construct current1 as right child of its inorder predecessor */
if(pre1->right1 == NULL){
pre1->right1 = current1;
current1 = current1->left1;
}
/* we have to revert the changes made in if part to restore the original tree i.e., fix the right child of predecssor */
else {
pre1->right1 = NULL;
// Now increment count if the current
// node is to be visited
count1++;
current1 = current1->right1;
} /* End of if condition pre1->right1 == NULL */
} /* End of if condition current1->left1 == NULL*/
} /* End of while */
return count1;
}
/* Shows function to find median in O(n) time and O(1) space
using Morris Inorder traversal*/
int findMedian(struct Node1 *root1){
if (root1 == NULL)
return 0;
int count1 = counNodes(root1);
int currCount1 = 0;
struct Node1 *current1 = root1, *pre1, *prev1;
while (current1 != NULL){
if (current1->left1 == NULL){
// Now count current node
currCount1++;
// Verify if current node is the median
// Odd case
if (count1 % 2 != 0 && currCount1 == (count1+1)/2)
return prev1->data1;
// Even case
else if (count1 % 2 == 0 && currCount1 == (count1/2)+1)
return (prev1->data1 + current1->data1)/2;
// Now update prev1 for even no. of nodes
prev1 = current1;
//Go to the right
current1 = current1->right1;
} else {
/* determine the inorder predecessor of current1 */
pre1 = current1->left1;
while (pre1->right1 != NULL && pre1->right1 != current1)
pre1 = pre1->right1;
/* Construct current1 as right child of its inorder
predecessor */
if (pre1->right1 == NULL){
pre1->right1 = current1;
current1 = current1->left1;
}
/* We have to revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else {
pre1->right1 = NULL;
prev1 = pre1;
// Now count current node
currCount1++;
// Verify if the current node is the median
if (count1 % 2 != 0 && currCount1 == (count1+1)/2 )
return current1->data1;
else if (count1%2==0 && currCount1 == (count1/2)+1)
return (prev1->data1+current1->data1)/2;
// Now update prev1 node for the case of even
// no. of nodes
prev1 = current1;
current1 = current1->right1;
} /* End of if condition pre1->right1 == NULL */
} /* End of if condition current1->left1 == NULL*/
} /* End of while */
}
/* Driver program to test above functions*/
int main(){
/* Let us create following BST
7
/ \
4 9
/ \ / \
2 5 8 10 */
struct Node1 *root1 = NULL;
root1 = insert(root1, 7);
insert(root1, 4);
insert(root1, 2);
insert(root1, 5);
insert(root1, 9);
insert(root1, 8);
insert(root1, 10);
cout << "\nMedian of BST is(for odd no. of nodes) "<< findMedian(root1) <<endl;
/* Let us create following BST
7
/ \
4 9
/ \ /
2 5 8
*/
struct Node1 *root2 = NULL;
root2 = insert(root2, 7);
insert(root2, 4);
insert(root2, 2);
insert(root2, 5);
insert(root2, 9);
insert(root2, 8);
cout << "\nMedian of BST is(for even no. of nodes) "
<< findMedian(root2);
return 0;
}실행 결과
Median of BST is(for odd no. of nodes) 7
Median of BST is(for even no. of nodes) 6
복잡도 분석
이 알고리즘은 노드 개수를 세는 순회와 중앙값을 찾는 순회, 총 두 번의 모리스 중위 순회를 수행하므로 시간 복잡도는 O(n)입니다. 또한 재귀나 스택 없이 포인터 몇 개(current, pre, prev)만 사용하므로 공간 복잡도는 O(1)입니다. 단, 모리스 순회는 트리의 링크를 일시적으로 변경했다가 복원하는 방식이므로, 순회가 끝나면 원래 트리 구조가 그대로 유지된다는 점을 기억하면 좋습니다.