이 글에서는 순서 통계(Order Statistic) 알고리즘을 활용하여 주어진 숫자 목록에서 k번째로 큰 값을 찾는 C++ 프로그램을 소개합니다. 이 방법은 이진 탐색 트리(BST)의 각 노드에 순위(rank) 정보를 미리 부여해 두고, 원하는 순위의 원소를 효율적으로 검색하는 방식으로 동작합니다.
알고리즘 개요
1. Insert() — 트리에 노드 삽입
시작
Insert() 함수: 트리에 노드를 삽입합니다.
매개변수:
root(루트), d(삽입할 데이터)
함수 본문:
트리가 완전히 비어 있으면 새 노드를 루트로 삽입합니다.
d == tmp->data이면 해당 노드의 카운트를 증가시킵니다.
d < tmp->data이면 tmp 포인터를 왼쪽 자식으로 이동합니다.
d > tmp->data이면 tmp 포인터를 오른쪽 자식으로 이동합니다.
종료2. AssignRank() — 각 노드에 순위 부여
시작
AssignRank() 함수: 트리의 모든 노드에 순위를 부여합니다.
매개변수:
root(루트)
함수 본문:
루트의 왼쪽 자식이 NULL이 아니면,
왼쪽 자식에게 순위를 부여합니다(중위 순회).
순위 카운트를 증가시킵니다.
루트의 오른쪽 자식이 NULL이 아니면,
오른쪽 자식에게 순위를 부여합니다.
종료3. Select() — k번째 작은 원소 검색
시작
Select() 함수: 트리에 저장된 데이터 중 k번째로 작은 원소를 검색합니다.
매개변수:
root(루트), 찾으려는 순위 k
함수 본문:
현재 노드의 순위가 k와 같으면, main으로 반환하여 결과를 출력합니다.
그렇지 않고 현재 순위가 k보다 크면,
임시 변수를 왼쪽 자식으로 이동합니다.
그 외에는(현재 순위가 k보다 작으면)
임시 변수를 오른쪽 자식으로 이동합니다.
종료C++ 예제 코드
아래 코드는 위 알고리즘을 그대로 구현한 전체 프로그램입니다. 배열 {4, 7, 6, 1, 10, 3, 2, 15, 16, 20}을 이진 탐색 트리로 구성한 뒤, 사용자가 입력한 k에 대해 k번째로 큰 원소를 출력합니다.
#include<iostream>
using namespace std;
static int cnt = 0;
struct nod // 노드 선언
{
int data;
int rank;
nod *l;
nod *r;
};
nod* CreateNod(int d) // 새 노드 생성
{
nod *newnod = new nod;
newnod->data = d;
newnod->rank = 0;
newnod->l = NULL;
newnod->r = NULL;
return newnod;
}
nod* Insert(nod* root, int d) // 노드 삽입 수행
{
nod *tmp = CreateNod(d);
nod *t = new nod;
t = root;
if(root == NULL)
root = tmp;
else {
while(t != NULL) {
if(t->data < d ) {
if(t->r== NULL) {
t->r = tmp;
break;
}
t = t->r;
} else if(t->data > d) {
if(t->l == NULL) {
t->l= tmp;
break;
}
t = t->l;
}
}
}
return root;
}
void AssignRank(nod *root) // 노드에 순위 부여
{
if(root->l!= NULL)
AssignRank(root->l);
root->rank = cnt;
cnt++;
if(root->r != NULL)
AssignRank(root->r);
}
int Select(nod* root, int k) // k번째로 큰 원소 선택
{
if(root->rank == k)
return root->data;
else if(root->rank > k)
return Select(root->l, k);
else
return Select(root->r, k);
}
void display(nod *root) // 트리 출력
{
if(root->l != NULL)
display(root->l);
cout<<"\n data: "<<root->data<<" rank: "<<root->rank;
if(root->r != NULL)
display(root->r);
}
int main() {
char c;
int n, i, k, a[10]={4,7,6,1,10,3,2,15,16,20};
nod *root = new nod;
root = NULL;
for(i = 0; i < 10; i++)
root = Insert(root, a[i]); // insert() 함수 호출
cout<<"Enter the value of k: ";
cin>>k;
AssignRank(root); // AssignRank() 함수 호출
cout<<"\nRank associated to each node:-";
display(root); // display() 함수 호출
cout<<"\n\nThe kth Largest element is: "<<Select(root, 10-k);
return 0;
}실행 결과
Enter the value of k: 7 Rank associated to each node:- data: 1 rank: 0 data: 2 rank: 1 data: 3 rank: 2 data: 4 rank: 3 data: 6 rank: 4 data: 7 rank: 5 data: 10 rank: 6 data: 15 rank: 7 data: 16 rank: 8 data: 20 rank: 9 The kth Largest element is: 4
프로그램 동작 원리
이 프로그램의 핵심은 순위(rank) 개념입니다. AssignRank() 함수가 트리를 중위 순회(in-order traversal)하면서 가장 작은 값부터 0, 1, 2… 순으로 순위를 매깁니다. 따라서 순위 0은 최솟값, 순위 n-1은 최댓값을 의미합니다.
k번째로 큰 원소를 구하려면, 전체 원소 개수가 n일 때 (n - k)번째로 작은 원소를 찾으면 됩니다. 예제에서는 총 10개의 원소가 있으므로 Select(root, 10-k)를 호출합니다. k=7을 입력하면 7번째로 큰 값은 4번째로 작은 값과 같으며, 실행 결과에서 확인할 수 있듯이 그 값은 4입니다.
이처럼 순서 통계 알고리즘을 사용하면 정렬 없이도 트리 탐색만으로 특정 순위의 원소를 O(h)(h는 트리의 높이) 시간 안에 찾을 수 있어, 반복적인 순위 조회가 필요한 상황에서 효율적입니다.