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

O(1) 공간 복잡도로 주어진 범위 내 BST 키 출력하기 (C++)

문제 개요

이 문제에서는 두 값 k1과 k2(k1 < k2)와 이진 탐색 트리(BST)의 루트 노드가 주어집니다. 우리의 과제는 주어진 범위 내에 있는 BST의 키를 모두 출력하는 프로그램을 작성하는 것입니다.

문제 설명: 트리의 키 중 n1부터 n2 사이에 속하는 모든 값을 오름차순으로 출력해야 합니다.

예제를 통해 문제를 이해해 보겠습니다.

입력: 아래와 같은 이진 탐색 트리가 주어지고,

k1 = 4, k2 = 12

출력: 6, 7, 9

해결 접근 방법

가장 단순한 방법은 중위 순회(inorder traversal)를 이용하는 것입니다. 하지만 일반적인 중위 순회는 재귀 호출 또는 스택을 사용하기 때문에 공간 복잡도가 O(n)이 됩니다. 이번 문제는 O(1) 공간 복잡도로 해결해야 하므로, 특별한 순회 기법이 필요합니다.

그 해답이 바로 모리스 순회(Morris Traversal)입니다. 이 기법은 스레드 이진 트리(threaded binary tree)에 기반을 두며, 스택이나 큐 없이 기존의 NULL 포인터를 임시 경로 정보로 활용하기 때문에 추가 메모리 사용량을 O(1)까지 줄일 수 있습니다.

모리스 순회의 동작 원리

  • 현재 노드의 왼쪽 자식이 없으면 현재 노드를 처리(범위 검사 후 출력)하고 오른쪽 자식으로 이동합니다.
  • 왼쪽 자식이 있으면 왼쪽 서브트리에서 가장 오른쪽에 있는 노드, 즉 중위 선행자(inorder predecessor)를 찾습니다.
  • 중위 선행자의 오른쪽 포인터가 NULL이라면 이를 현재 노드에 연결(스레드 생성)한 뒤 왼쪽 자식으로 이동합니다.
  • 이미 스레드가 존재한다면 이를 제거하여 트리 구조를 복원하고, 현재 노드를 처리한 후 오른쪽 자식으로 이동합니다.

이렇게 하면 트리를 재귀나 스택 없이도 중위 순회 순서대로 방문할 수 있으며, 방문 시점에 값이 k1 이상 k2 이하인지 검사하여 조건에 맞는 키만 출력하면 됩니다.

C++ 구현 코드

#include <iostream>
using namespace std;

struct node {
    int data;
    struct node *left, *right;
};

node* insertNode(int data) {
    node* temp = new node;
    temp->data = data;
    temp->right = temp->left = NULL;
    return temp;
}

void RangeTraversal(node* root, int k1, int k2) {
    if (!root)
        return;

    node* nodeTraversal = root;

    while (nodeTraversal) {
        // 왼쪽 자식이 없는 경우: 현재 노드 처리 후 오른쪽으로 이동
        if (nodeTraversal->left == NULL) {
            if (nodeTraversal->data <= k2 && nodeTraversal->data >= k1)
                cout << nodeTraversal->data << " ";
            nodeTraversal = nodeTraversal->right;
        }
        else {
            // 왼쪽 서브트리의 중위 선행자 찾기
            node* prevNode = nodeTraversal->left;
            while (prevNode->right != NULL && prevNode->right != nodeTraversal)
                prevNode = prevNode->right;

            if (prevNode->right == NULL) {
                // 스레드 생성 후 왼쪽 자식으로 이동
                prevNode->right = nodeTraversal;
                nodeTraversal = nodeTraversal->left;
            }
            else {
                // 스레드 제거 후 현재 노드 처리
                prevNode->right = NULL;
                if (nodeTraversal->data <= k2 && nodeTraversal->data >= k1)
                    cout << nodeTraversal->data << " ";
                nodeTraversal = nodeTraversal->right;
            }
        }
    }
}

int main() {
    node* root = insertNode(6);
    root->left = insertNode(3);
    root->right = insertNode(2);
    root->left->left = insertNode(1);
    root->left->right = insertNode(7);
    root->right->right = insertNode(9);

    cout << "All BST keys in the given range are \t";
    RangeTraversal(root, 4, 10);

    return 0;
}

실행 결과

All BST keys in the given range are 7 6 9

복잡도 분석

  • 시간 복잡도: O(n) — 각 노드를 최대 상수 번 방문합니다.
  • 공간 복잡도: O(1) — 스택이나 큐 등 추가 자료구조를 사용하지 않고, 트리의 NULL 포인터만 임시로 활용합니다.

모리스 순회를 활용하면 재귀 호출로 인한 스택 오버플로우 걱정 없이 대용량 트리에서도 효율적으로 범위 내 키를 조회할 수 있습니다.