10. 입력 순서에 기대지 않고 트리를 만든다
해설글
작성 · 3분 읽기 · 조회수 —수정
기초 개념과 예제를 보강하고 시리즈 흐름을 연결
노드 관계를 실제 트리로 바꾸는 문제
입력의 한 행이 (현재 ID, 왼쪽 자식 ID, 오른쪽 자식 ID)라고 하자. (1,2,3), (2,4,0), (4,0,0), (3,0,0)은 1이 root이고 왼쪽에 2, 오른쪽에 3, 2의 왼쪽에 4가 있다는 뜻이다. 0은 해당 자식이 없다는 표시다.
ID는 입력에서 노드를 구별하는 번호이고, 포인터는 프로그램 메모리에서 실제 노드의 주소다. 트리를 만들려면 숫자 ID 관계를 node->left, node->right 포인터 관계로 바꿔야 한다. 원하는 결과는 입력 행의 배치가 달라도 같은 ID 관계라면 같은 트리를 얻는 것이다.
이때 모든 입력이 자동으로 트리가 되는 것은 아니다. 자식 ID가 실제로 존재해야 하고, ID는 중복되지 않아야 하며, root는 하나여야 한다. 한 노드로 돌아오는 사이클이나 여러 부모가 같은 자식을 소유하는 관계도 거부해야 한다.
자식 번호를 읽고도 번호를 찾지 않는 코드
이진트리 구현 노트는 구조체 선언과 “이진트리를 구현하자”라는 짧은 목표만 남아 있다. 구체적인 사고 과정은 충분하지 않아, 이 글은 저장소의 동적 생성 코드가 성립하는 입력 조건을 이번에 분석한 내용이다.
원본의 main은 입력 행을 먼저 triples 배열에 모두 저장하고, BuildTree는 전역 curIndex를 늘리며 그 배열의 행을 재귀적으로 소비한다. 각 행에는 현재 노드 번호 x, 왼쪽 자식 번호 yl, 오른쪽 자식 번호 zr가 있지만, yl과 zr 값으로 해당 노드를 검색하지 않는다.
if (yl != 0) {
curIndex++;
node->left = BuildTree();
}
if (zr != 0) {
curIndex++;
node->right = BuildTree();
}
자식이 존재한다는 표시만 확인하고 바로 다음 입력 행을 자식으로 소비한다. 이 방식이 맞으려면 행들이 root-left-right 전위 순서로 놓여 있어야 한다. yl과 zr은 실제 연결에 쓰이는 ID라기보다 자식 존재 여부가 된다.
입력 스트림을 재귀로 소비하기
다음 순서라면 원본 방식이 자연스럽다.
1 2 3
2 4 0
4 0 0
3 0 0
1을 만들고 왼쪽이 있으므로 다음 행 2로 내려간다. 2의 왼쪽이 있으므로 다음 행 4로 내려간다. 4를 마치고 복귀한 뒤 2, 다시 1의 오른쪽 3을 소비한다. 트리의 전위 순회와 입력 순서가 같기 때문에 별도 검색이 필요 없다.
하지만 행을 다음처럼 섞으면 자식 ID가 써 있어도 원본은 첫 행의 3을 루트로 만든 뒤 곧바로 복귀한다.
3 0 0
1 2 3
2 4 0
4 0 0
3은 자식이 없는 노드이므로 이미 입력받은 나머지 1, 2, 4 행은 트리 생성에 사용되지 않는다. 이것이 원래 과제에서 오류인지는 입력 명세에 달려 있다. 전위 순서가 보장된 문제라면 간결하고 올바른 파서다. 범용적인 (id,left_id,right_id) 목록을 받는 코드로 소개하려면 입력 순서 의존성을 제거해야 한다.
ID와 포인터를 두 단계로 연결하기
이번에 만든 순서 독립 트리 생성 코드는 먼저 모든 행을 노드 배열로 만든다. 그다음 각 left_id, right_id에 해당하는 노드를 찾아 포인터를 연결한다.
node->left = node->left_id ? find(nodes, n, node->left_id) : NULL;
node->right = node->right_id ? find(nodes, n, node->right_id) : NULL;
행 순서를 3,1,2,4로 섞어 실행해도 결과는 ID 관계를 따른다.
shuffled preorder: 1 2 4 3
invalid rejected: missing=1 duplicate=1 cycle=1 multiple_roots=1
이 예제는 ID가 유일하고, 모든 자식 ID가 존재하고, 한 노드가 둘 이상의 부모를 갖지 않으며, 루트가 정확히 하나이고, 그 루트에서 모든 노드에 순환 없이 도달한다는 계약까지 검사한다. 빠진 자식, 중복 ID, 사이클, 복수 루트를 각각 거부했다. 현재 예제의 ID 탐색은 매 연결마다 선형 탐색하므로 $O(n^2)$이다. 큰 입력에서는 ID를 인덱스로 직접 쓰거나 hash map을 두어 $O(n)$에 가깝게 줄일 수 있다.
경로 질의의 전제도 드러내기
원본의 PrintPath는 L이면 왼쪽, R이면 오른쪽으로 이동하며 값을 출력한다. 코드 주석에는 “유효하지 않은 경로는 입력으로 주어지지 않는다고 가정”한다고 적혀 있다. 이 전제가 없다면 NULL로 이동한 뒤 cur->data를 읽어 segmentation fault가 날 수 있다.
범용 함수라면 이동 전에 다음 포인터가 NULL인지, 문자가 L/R인지 검사하고 성공 여부를 반환해야 한다. 과제에서 보장하는 입력과 재사용 가능한 함수의 방어 범위는 다르다.
이미 만들어진 트리를 방문하는 법에서 출발해, 이번에는 그 트리가 어떤 입력 계약 위에서 만들어졌는지를 확인했다. 재귀가 틀린 것이 아니라, 재귀가 소비하는 입력 순서가 함수의 일부였다는 점이 핵심이다.