왼쪽 자식-오른쪽 형제 표현이란?
왼쪽 자식-오른쪽 형제(Left-Child Right-Sibling) 표현은 N진 트리(n-ary tree)를 나타내는 또 다른 방식입니다. 일반적인 표현에서는 모든 자식 노드에 대해 각각 포인터를 유지해야 했지만, 이 방식에서는 노드가 단 두 개의 포인터만 가집니다.
- 첫 번째 포인터: 해당 노드의 첫 번째 자식을 가리킵니다.
- 두 번째 포인터: 바로 다음에 오는 형제(sibling) 노드를 가리킵니다.
이러한 변환은 노드가 가질 자식의 수를 미리 알아야 할 필요성을 없애주며, 노드당 포인터 수를 최대 2개로 제한하기 때문에 코드 작성이 훨씬 간단해집니다.
기본 규칙
- 각 노드에서는 같은 부모를 가진 자식들을 왼쪽에서 오른쪽 순서로 연결합니다.
- 부모 노드는 첫 번째 자식과만 연결되며, 나머지 자식들은 형제 포인터를 통해 접근합니다.
예시
다음은 왼쪽 자식-오른쪽 형제 방식으로 표현한 트리 구조입니다.
10 | 2 -> 3 -> 4 -> 5 | | 6 7 -> 8 -> 9
위 예시에서 노드 10은 첫 번째 자식인 2만 직접 가리키고, 3·4·5는 2의 형제로 연결됩니다. 마찬가지로 노드 2는 자식 6을, 노드 5는 자식 7을 가리키며, 8과 9는 7의 형제로 연결됩니다.
장점
- 노드당 필요한 포인터 수를 최대 2개로 제한하므로 메모리를 절약할 수 있습니다.
- 자식 수에 대한 사전 정보 없이도 임의의 N진 트리를 표현할 수 있어 구현이 간단합니다.
단점
- 검색·삽입·삭제와 같은 기본 연산에 더 많은 시간이 소요될 수 있습니다. 정확한 위치를 찾으려면 대상 노드의 모든 형제를 처음부터 순회해야 하기 때문입니다(최악의 경우).
정리
왼쪽 자식-오른쪽 형제 표현은 고정된 두 개의 포인터만으로 가변적인 자식 수를 가지는 트리를 표현할 수 있는 실용적인 방법입니다. 메모리 효율성과 구현 편의성이 중요한 상황에서 널리 활용되며, 반면 빈번한 탐색 연산이 필요한 경우에는 성능 저하를 고려해야 합니다.