C# 코딩테스트 강좌, 트리의 부모 찾기

문제 설명

이 문제의 목표는 주어진 이진 트리에서 특정 노드의 부모 노드를 찾는 것입니다.
이진 트리는 각 노드가 최대 두 개의 자식을 가질 수 있는 계층적 데이터 구조입니다.
우리의 목표는 입력된 노드를 기반으로 그 노드의 부모를 올바르게 찾는 프로그램을 작성하는 것입니다.

문제 입력

    트리는 배열로 주어지며, 각 원소는 트리의 노드입니다. 
    배열의 인덱스는 노드의 위치를 나타내며, 인덱스 0은 루트 노드입니다. 
    예를 들어, 배열 [3, 5, 1, 6, 2, 0, 8]일 경우,
    3은 루트 노드,
    5는 노드 3의 왼쪽 자식,
    1은 노드 3의 오른쪽 자식,
    6은 노드 5의 왼쪽 자식, 
    2는 노드 5의 오른쪽 자식,
    0은 노드 1의 왼쪽 자식,
    8은 노드 1의 오른쪽 자식입니다.
    

문제 출력

    특정 노드에 대한 부모 노드의 값을 출력합니다. 
    만약 부모 노드가 없다면(-1) 출력합니다.
    

예시

입력

    트리: [3, 5, 1, 6, 2, 0, 8]
    노드: 6
    

출력

    5
    

입력

    트리: [3, 5, 1, 6, 2, 0, 8]
    노드: 3
    

출력

    -1
    

풀이 접근법

이 문제를 해결하기 위해서는 트리의 구조를 이해하고 각 노드의 부모를 찾는 방법을 알아야 합니다.
이진 트리에서 각 노드의 부모 노드는 자식 노드의 인덱스와 수학적인 연산을 통해 찾을 수 있습니다.

부모 노드 찾기

주어진 인덱스에 대해 그 부모 노드의 인덱스는 다음과 같이 계산할 수 있습니다:

• 부모 노드의 인덱스: parentIndex = (childIndex - 1) / 2

– 여기서 childIndex는 찾고자 하는 노드의 인덱스입니다.
– 만약 childIndex가 0일 경우, 이는 루트 노드이므로 부모 노드가 존재하지 않습니다.

구현

이제 위의 접근 방식을 바탕으로 C# 코드를 작성해 보겠습니다.

public class TreeNodeSearcher 
{
    public static int FindParent(int[] tree, int childIndex) 
    {
        // 입력된 childIndex가 유효한지 체크
        if (childIndex < 0 || childIndex >= tree.Length) 
        {
            throw new ArgumentOutOfRangeException("Child index is out of the range of the tree array.");
        }
        
        // 루트 노드의 경우 부모가 없음
        if (childIndex == 0) 
        {
            return -1; // 부모가 없음
        }

        // 부모 인덱스 계산
        int parentIndex = (childIndex - 1) / 2;
        return tree[parentIndex];
    }
}
    

테스트

위의 메소드를 유효하게 테스트하기 위해 몇 가지 케이스를 만들어 보겠습니다.

public class Program 
{
    public static void Main() 
    {
        int[] tree = {3, 5, 1, 6, 2, 0, 8};

        Console.WriteLine(TreeNodeSearcher.FindParent(tree, 3)); // 출력: 5
        Console.WriteLine(TreeNodeSearcher.FindParent(tree, 0)); // 출력: -1
        Console.WriteLine(TreeNodeSearcher.FindParent(tree, 5)); // 출력: 1
        Console.WriteLine(TreeNodeSearcher.FindParent(tree, 1)); // 출력: 3
    }
}
    

결론

우리는 주어진 이진 트리에서 특정 노드의 부모 노드를 찾기 위한 알고리즘을 성공적으로 구현했습니다.
이 알고리즘은 시간 복잡도 O(1)로 매우 효율적입니다.
트리의 구조를 이해하고 활용하는 것이 중요하며, 이러한 기초적인 개념은 더 복잡한 데이터 구조를 다룰 때에도 유용하게 적용될 수 있습니다.

추가 학습

트리에 대한 이해를 깊이 하기 위해 이진 검색 트리, AVL 트리, 힙과 같은 고급 주제도 다루어 볼 것을 권장합니다.
이러한 자료구조는 다양한 알고리즘 문제를 해결하는 데 큰 도움이 될 것입니다.