C++로 이해하는 연속 트리(Continuous Tree) 개념과 판별 알고리즘

연속 트리란 무엇인가?

연속 트리(Continuous Tree)는 루트 노드에서 리프 노드로 이어지는 모든 경로에서, 부모 노드와 그 직계 자식 노드들 사이의 값(가중치) 차이의 절댓값이 항상 1이 되는 트리를 의미합니다.

루트에서 리프까지의 경로에 있는 임의의 노드를 골랐을 때 다음 조건이 반드시 성립해야 합니다.

• |부모 노드의 값 − 왼쪽 자식 노드의 값| = 1
• |부모 노드의 값 − 오른쪽 자식 노드의 값| = 1

예제로 이해하기

아래 트리는 모든 부모 노드와 자식 노드 사이의 절댓값 차이가 항상 1이므로 연속 트리에 해당합니다.

반면 아래 트리는 어떤 경로에서 부모 노드와 자식 노드의 값 차이가 1이 아니므로 연속 트리의 조건을 만족하지 못합니다.

트리가 연속적인지 확인하는 알고리즘

재귀적 접근을 사용하면 트리가 연속 트리인지 효율적으로 판별할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.

• 루트가 NULL이면 1을 반환합니다.
• 현재 노드가 리프 노드라면 1을 반환합니다. 리프 노드에 도달했다는 것은 지금까지의 경로가 연속 조건을 만족했다는 의미이기 때문입니다.
• 왼쪽 서브트리가 비어 있다면 현재 노드와 오른쪽 자식의 값 차이(절댓값)를 검사하고, 오른쪽 서브트리에 대해 재귀적으로 계속 진행합니다.
• 오른쪽 서브트리가 비어 있다면 현재 노드와 왼쪽 자식의 값 차이(절댓값)를 검사하고, 왼쪽 서브트리에 대해 재귀적으로 계속 진행합니다.
• 두 자식이 모두 존재한다면 왼쪽·오른쪽 자식 각각과의 절댓값 차이를 계산하고, 양쪽 서브트리에 대해 재귀적으로 탐색을 이어갑니다.

의사 코드(Pseudocode)

// 트리가 연속적인지 확인하는 함수
struct btreeNode{
    int data;
    btreeNode* left, * right;
};
int isContinuous(btreeNode *root){
    // 노드가 NULL이면 1 반환 (종료 조건)
    if (root == NULL)
        return 1;
    // 리프 노드에 도달했다면 해당 경로는 연속 조건을 만족한 것
    if (root->left == NULL && root->right == NULL)
        return 1;
    // 왼쪽 자식이 없는 경우
    if (root->left == NULL)
        return (abs(root->data - root->right->data) == 1) && isContinuous(root->right);
    // 오른쪽 자식이 없는 경우
    if (root->right == NULL)
        return (abs(root->data - root->left->data) == 1) && isContinuous(root->left);
    // 두 자식이 모두 있는 경우 절댓값 차이를 계산
    return abs(root->data - root->left->data)==1 && abs(root->data - root->right->data)==1 &&
        isContinuous(root->left) && isContinuous(root->right);
}