C++ 이진 탐색 트리로 배열의 최댓값 찾기 – O(log n) 구현 방법

이 글에서는 C++를 사용해 이진 탐색 트리(Binary Search Tree)를 활용하여 배열(데이터 집합)에서 최댓값을 찾는 방법을 소개합니다. 이진 탐색 트리에서는 항상 가장 오른쪽 끝에 있는 노드가 최댓값을 가지므로, 루트에서 오른쪽 자식 노드만 따라 이동하면 최댓값을 빠르게 찾을 수 있습니다. 균형 잡힌 트리를 기준으로 할 때 이 프로그램의 시간 복잡도는 O(log n)입니다.

동작 원리

이진 탐색 트리는 다음과 같은 규칙을 따릅니다.

• 부모 노드보다 작은 값은 왼쪽 서브트리에 위치합니다.
• 부모 노드보다 큰 값은 오른쪽 서브트리에 위치합니다.

따라서 트리에서 가장 오른쪽 끝에 있는 노드가 곧 전체 데이터 중 최댓값이 됩니다. 루트에서 시작해 오른쪽 자식이 더 이상 없을 때까지 계속 오른쪽으로 이동한 뒤, 마지막 노드의 데이터를 최댓값으로 출력하고 해당 노드의 깊이(depth)를 함께 출력하면 됩니다.

알고리즘

시작
   주어진 데이터 요소들을 이용해 이진 탐색 트리를 구성한다.
   루트 포인터를 가장 오른쪽에 있는 자식 노드까지 순회한다.
   해당 노드의 데이터 부분을 주어진 데이터 집합의 최댓값으로 출력한다.
   최댓값 데이터의 깊이(depth)를 출력한다.
종료

예제 코드

#include<iostream>
using namespace std;
struct node {
    int d;
    node *left;
    node *right;
};
node* CreateNode(int d) {
    node *newnode = new node;
    newnode->d = d;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}
node* InsertIntoTree(node* root, int d) {
    node *temp = CreateNode(d);
    node *t = new node;
    t = root;
    if(root == NULL)
      root = temp;
   else {
      while(t != NULL){
         if(t->d < d ) {
            if(t->right == NULL) {
               t->right = temp;
                break;
             }
             t = t->right;
          }
          else if(t->d > d) {
             if(t->left == NULL) {
                t->left = temp;
                break;
             }
             t = t->left;
          }
      }
   }
   return root;
}
int main() {
   int n, i, a[10] = {86, 63, 95, 6, 7, 67, 52, 26, 45, 98};
   node *root = new node;
   root = NULL;
   cout<<"\nData set:\n";
   for(i = 0; i < 10; i++) {
      cout<<a[i]<<" ";
      root = InsertIntoTree(root, a[i]);
   }
   cout<<"\n\nThe maximum element of the given data set is\n ";
   i = 0;
   while(root->right != NULL) {
      i++;
      root = root->right;
   }
   cout<<root->d<<"\n"<<"data found at "<<i<<" depth from the root.";
   return 0;
}

코드 설명

• CreateNode(): 새로운 노드를 동적으로 생성하고, 데이터 값과 좌우 자식 포인터(NULL)를 초기화합니다.
• InsertIntoTree(): BST의 규칙에 따라 값을 삽입합니다. 현재 노드보다 값이 크면 오른쪽으로, 작으면 왼쪽으로 이동하며 비어 있는 자리를 찾아 노드를 연결합니다.
• main(): 배열의 모든 요소를 트리에 삽입한 뒤, root->right가 NULL이 될 때까지 오른쪽으로 이동하면서 깊이를 카운트하고, 마지막 노드의 값을 최댓값으로 출력합니다.

실행 결과

Data set:
86 63 95 6 7 67 52 26 45 98

The maximum element of the given data set is
98
data found at 2 depth from the root.

위 실행 결과에서 최댓값은 98이며, 이 값은 루트에서 깊이 2에 해당하는 노드에서 발견됩니다.

참고: 시간 복잡도 O(log n)는 트리가 균형 잡혀 있을 때의 평균적인 경우입니다. 만약 데이터가 이미 정렬된 순서로 삽입되어 트리가 한쪽으로 치우친 편향 트리가 되면, 최악의 경우 시간 복잡도는 O(n)까지 증가할 수 있습니다.