C++로 구현하는 리프 노드가 원형 이중 연결 리스트로 연결된 특수 이진 트리의 높이 계산

리프 노드들이 서로 연결되어 원형 이중 연결 리스트(circular doubly linked list)를 형성하는 특수한 형태의 이진 트리가 있다고 가정해 보겠습니다. 이때 트리의 높이(height)를 구하는 것이 우리의 목표입니다.

이러한 트리에서는 가장 왼쪽에 있는 리프 노드의 left 포인터가 원형 이중 연결 리스트의 prev(이전) 포인터 역할을 하고, right 포인터가 next(다음) 포인터 역할을 합니다.

접근 방법

높이를 계산하는 전략은 일반적인 이진 탐색 트리와 크게 다르지 않습니다. 각 노드에 대해 재귀적으로 왼쪽 서브트리와 오른쪽 서브트리의 높이를 구하고, 노드의 높이는 두 자식 중 더 큰 값에 1을 더한 값으로 설정합니다.

다만 여기서 주의할 점은 리프 노드가 원형 이중 연결 리스트의 일부라는 것입니다. 따라서 어떤 노드가 리프 노드인지 판별하려면 다음 조건을 확인해야 합니다.

• 노드의 left->right가 자기 자신을 가리키는지
• 노드의 right->left가 자기 자신을 가리키는지

두 조건이 모두 참이라면 해당 노드는 실제 자식이 없는 리프 노드이며, 단순히 left나 right가 NULL인지만 검사하는 방식과는 다르게 처리해야 합니다.

C++ 구현 예제

#include<iostream>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
};

// 리프 노드 판별 함수
bool isLeafNode(Node* node) {
    return node->left && node->left->right == node
        && node->right && node->right->left == node;
}

// 트리의 높이를 재귀적으로 계산
int findHeight(Node* node) {
    if (node == NULL)
        return 0;
    if (isLeafNode(node))
        return 1;
    return 1 + max(findHeight(node->left), findHeight(node->right));
}

// 새 노드 생성 헬퍼 함수
Node* getNode(int data) {
    Node* node = new Node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    // 트리 구성
    Node* root = getNode(1);
    root->left = getNode(2);
    root->right = getNode(3);
    root->left->left = getNode(4);
    root->left->right = getNode(5);
    root->left->left->left = getNode(6);

    // 리프 노드들을 원형 이중 연결 리스트로 연결
    Node *L1 = root->left->left->left;
    Node *L2 = root->left->right;
    Node *L3 = root->right;

    L1->right = L2, L2->right = L3, L3->right = L1;  // next 포인터
    L3->left = L2, L2->left = L1, L1->left = L3;     // prev 포인터

    cout << "Height of tree is: " << findHeight(root);
}

실행 결과

Height of tree is: 4

동작 설명

위 예제에서 트리의 구조는 다음과 같습니다.

• 루트 노드 1의 왼쪽 자식은 2, 오른쪽 자식은 3입니다.
• 노드 2의 왼쪽 자식은 4, 오른쪽 자식은 5입니다.
• 노드 4의 왼쪽 자식은 6입니다.

여기서 리프 노드는 6(L1), 5(L2), 3(L3)이며, 이 세 노드가 원형 이중 연결 리스트로 연결됩니다. 만약 일반적인 방식처럼 left나 right가 NULL인지만으로 리프를 판단했다면, 연결 리스트 포인터 때문에 잘못된 경로를 탐색하게 됩니다.

isLeafNode() 함수가 left->right == node와 right->left == node 조건을 검사하기 때문에, 연결 리스트로 연결된 노드들을 정확히 리프로 인식하고 재귀 탐색이 올바르게 종료됩니다. 그 결과 트리의 높이는 4(경로: 1 → 2 → 4 → 6)로 출력됩니다.

시간 복잡도

모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(N), 재귀 호출 스택으로 인한 공간 복잡도는 트리의 높이에 비례하여 최악의 경우 O(N)입니다.