Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 이진 탐색 트리(BST)의 중위 후속자(Inorder Successor) 찾기

이진 탐색 트리(BST)와 특정 노드 p가 주어졌을 때, 해당 노드의 중위 후속자(Inorder Successor)를 찾아야 합니다.

중위 후속자란 노드 p보다 키 값이 큰 노드들 중에서 가장 작은 값을 가지는 노드를 의미합니다. 즉, 중위 순회(In-order Traversal) 기준으로 p 바로 다음에 방문하게 되는 노드입니다.

문제 이해하기

예를 들어 다음과 같은 이진 탐색 트리가 있다고 가정해 보겠습니다.

C++로 이진 탐색 트리(BST)의 중위 후속자(Inorder Successor) 찾기

이때 p = 1이라면, 1보다 큰 값 중 가장 작은 값은 2이므로 출력 결과는 2가 됩니다.

해결 접근 방법

BST의 핵심 속성(왼쪽 자식 < 루트 < 오른쪽 자식)을 활용하면 재귀적으로 간단하게 해결할 수 있습니다. 알고리즘의 동작 과정은 다음과 같습니다.

  • 루트(root)와 노드 p를 인자로 받는 재귀 함수 inorderSuccessor()를 정의합니다.
  • 루트가 null이면 null을 반환합니다.
  • 루트의 값이 p의 값보다 작거나 같으면, 후속자는 반드시 오른쪽 서브트리에 존재하므로 오른쪽 서브트리를 대상으로 재귀 호출합니다.
  • 그렇지 않다면(루트의 값이 p보다 크면), 현재 루트가 후속자의 후보가 됩니다. 왼쪽 서브트리에서 더 나은 후보를 찾고, 없다면 현재 루트를 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
class Solution {
   public:
   TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
      if(!root) return NULL;
         if(root->val <= p->val){
            return inorderSuccessor(root->right, p);
         }else{
            TreeNode* option = inorderSuccessor(root->left, p);
            return !option ? root : option;
      }
   }
};
main(){
   TreeNode *root = new TreeNode(2);
   root->left = new TreeNode(1);
   root->right = new TreeNode(3);
   TreeNode *p = root->left;
   Solution ob;
   cout << (ob.inorderSuccessor(root, p))->val;
}

입력

TreeNode *root = new TreeNode(2);
root->left = new TreeNode(1);
root->right = new TreeNode(3);
1

출력

2

동작 원리 상세 설명

위 코드의 실행 흐름을 살펴보면 다음과 같습니다.

  1. 루트 노드의 값(2)이 p의 값(1)보다 크므로, 현재 루트는 후속자 후보가 됩니다.
  2. 왼쪽 서브트리에서 재귀 호출을 진행하면, 노드 1의 값이 p와 같으므로 오른쪽 서브트리를 탐색하지만 해당 서브트리가 없어 null을 반환합니다.
  3. 결국 후보였던 루트 노드 2가 최종 결과로 반환됩니다.

이 알고리즘의 시간 복잡도는 트리의 높이에 비례하여 평균 O(log N), 최악의 경우(트리가 한쪽으로 치우친 경우) O(N)입니다. 공간 복잡도 역시 재귀 호출 스택으로 인해 O(log N) ~ O(N)입니다.