[자료구조] 트리

참고자료

<C++로 쉽게 풀어쓴 자료구조> 천인국, 최영규 지음, 생능 출판사
공부 범위 : 챕터 8 트리

트리의 개념

트리는 계층적인 자료구조. 인공지능 문제에서는 결정 트리에 사용됨.

용어 정리

• 노드(node) : 트리에 존재하는 각 지점들
• 루트 노드(root node) : 트리 최상단에 있는 노드
• 서브트리(subtree) : 루트 노드 아래에 있는 노드들
• 간선(edge, 에지) : 노드의 연결선
• 부모 노드(parent node) : 어떤 노드의 바로 위에 연결된 노드
• 자식 노드(children node) : 어떤 노드의 바로 아래에 연결된 노드
• 형제 관계(sibling) : 같은 부모 노드를 갖는 자식 노드들 간의 관계
• 조상 노드(ancestor node) : 루트 노드에서 어떤 노드까지의 경로를 이루는 노드들
• 자손 노드(descendent node) : 어떤 노드 아래에 연결된 모든 노드
• 단말 노드(terminal node, leaf node) : 자식 노드가 없는 노드
• 비단말 노드(nonterminal node) : 자식 노드가 존재하는 노드, 단말 노드의 반대
• 차수(degree) : 어떤 노드가 갖는 자식 노드의 개수
• 트리의 차수 : 트리가 갖는 노드들의 차수 중 가장 큰 값
• 레벨(level) : 트리의 각 층에 번호를 매기는 것, 루트 노드에서 1부터 셈
• 트리의 높이(height) : 트리가 갖는 최대 레벨
• 포리스트(forest) : 트리의 집합

트리의 표현

가장 일반적인 방법은 노드 구조를 이용하는 것. 연결 리스트와 유사하며 각 노드는 데이터 필드와 링크 필드를 갖는다. 링크 필드의 개수는 자식 노드의 수와 같다. 실제로 구현할 때는 링크 필드의 수가 일정하지 않으면 구조가 복잡해지므로 이진트리를 많이 사용함. 이 책에서는 이진트리만 다룬다.

이진트리 소개

이진트리란?

모든 노드가 2개의 서브트리를 갖는 트리, 서브트리는 공집합일 수 있다. 모든 노드는 최대 2개의 자식만을 가질 수 있으며 왼쪽과 오른쪽이 구분되어야 한다.

이진트리의 성질

• 노드 n개 → 간선 (n - 1)개
• 높이가 h인 이진트리의 노드 수 : h개 이상, (2^h - 1)개 이하. 레벨 i에서 노드의 최대 개수는 (2ⁱ - 1)개.
• n개의 노드를 갖는 이진트리의 높이 : ⌈log₂(n + 1)⌉ 이상, n 이하
• 포화 이진트리(full binary tree) : 각 레벨에 노드가 꽉 찬 이진트리. 높이가 k이면 노드는 (2^k - 1)개. 각 노드에 번호를 붙일 수 있으며 레벨 단위로 왼쪽에서부터 차례로 붙이면 되고, 항상 일정하게 부여됨.
• 완전 이진트리(complete binary tree) : 높이가 k인 트리에서 레벨 1부터 (k - 1)까지는 모든 노드가 채워져 있고, 마지막 레벨은 왼쪽부터 순서대로 노드가 채워진 트리. 절대 중간이 비어 있으면 안 되고 노드 번호는 포화 이진트리와 같음.

이진트리의 추상 자료형

트리를 생성하고, 이런저런 정보를 확인하고 삽입, 삭제 등을 수행하는 추상 자료형. 자세한 건 직접 책을 보자.

이진트리의 표현

배열 표현법

저장하고자 하는 이진트리가 완전 이진트리라고 가정, 정해진 높이에 따른 노드 수만큼의 배열을 생성한다. 완전 이진트리의 노드 번호대로 정보를 배열에 저장한다. 주로 포화/완전 이진트리에서 많이 쓰긴 하는데 일반 이진트리도 저장할 수 있다(대신 공간 낭비 심함). 다만 인덱스 0번은 사용하지 않는다. 그게 편하다. 배열의 크기를 변경할 수 없으므로 트리의 높이가 제한되어 많이 사용하지 않음.

링크 표현법

트리의 노드들은 공간적으로는 흩어져 있고, 각각 데이터 필드와 링크 필드를 갖는다. 왼쪽과 오른쪽을 구분한다.

링크 표현법을 이용한 이진트리의 구현

자세한 코드는 생략. 노드 클래스를 먼저 만들고, 그것을 이용해 트리 클래스를 만든다. 노드 클래스는 데이터 필드와 왼쪽, 오른쪽 자식 노드의 링크 필드를 갖고, 트리 클래스는 루트 노드의 포인터만을 멤버 필드로 갖는다.

이진트리의 순회

이진트리의 순회 방법

루트와 서브트리 방문 순서에 따라 구분, 이름은 루트 기준

• 전위(preorder) : 루트 - 왼쪽 - 오른쪽
• 중위(inorder) : 왼쪽 - 루트 - 오른쪽
• 후위(postorder) : 왼쪽 - 오른쪽 - 루트

순회 방법은 자식 노드와 부모 노드의 처리 순서에 따라 다르게 선택한다. 자식 노드를 먼저 봐야 한다면 후위 순회, 부모 노드를 먼저 봐야 한다면 전위 순회. 실제 구현하는 코드는 재귀 호출의 순서만 다를 뿐 큰 구조는 같다.

레벨 순회(level order)

표준 순회 방법은 아니지만 많이 사용한다고 한다. 각 노드를 레벨 순으로 검사하는 방법이다. 앞서 소개한 세 가지 방법은 자료구조로 치면 스택을 사용한 것이고 이 방법은 큐를 사용하는 것이다.
큐에서 노드를 하나 꺼내 방문하고 그 자식들을 큐에 넣어 같은 과정을 반복한다. 자식이 없으면 삽입하지 않고 큐가 빌 때까지 한다. 처음에는 루트 노드를 넣는다. 재귀 호출을 사용하지 않는다.

이진트리 연산

트리의 노드 개수 구하기

모든 노드를 순회하여 개수를 센다. 루트 노드와 양쪽 서브트리의 노드 개수를 합하면 된다. 재귀 호출로 구현한다.

단말 노드 개수 구하기

마찬가지로 모든 노드를 순회하는데, 양쪽 자식이 모두 없는 경우만 센다. 구현은 전체 노드 개수 구하기와 유사하다.

높이 구하기

루트노드에 대해 양쪽 서브트리의 높이를 구하고 그 중 (높은 쪽 + 1)을 결과로 반환한다. 루트 노드도 높이로 셈해야 하기 때문에 서브트리의 높이에 1을 더해야 한다. 재귀 호출로 구현한다. 이 챕터에서 다루는 함수 중 재귀 호출로 구현되는 것 대부분이 실제 사용을 위해 작성되는 함수와 그것을 호출했을 때 실행되는 함수가 메소드 오버로딩으로 서로 다른 인자를 받도록 구현되어 있음에 주의해야 한다.

이진트리 응용

수식 트리

노드가 산술식이나 논리식의 연산자와 피연산자로 이루어진 트리이다. 피연산자는 단말 노드가 되며 연산자는 비단말노드이다. 이 트리는 자식 노드를 먼저 계산하고 부모 노드를 계산해야 하므로 후위 순회를 해야 한다.

디렉터리 용량 계산

지금은 이진트리를 사용하고 있기 때문에 한 폴더에 두 개보다 많은 하위 폴더가 존재하면 안 된다. 서브 디렉터리의 용량을 계산한 후 루트 디렉터리의 용량을 계산해야 하므로 마찬가지로 후위 순회를 사용한다.

스레드 이진트리

목적 : 재귀 호출이나 다른 자료구조의 혼용 없이 순회를 구현하고 싶다.
실현 방안 : 트리에 존재하는 null 링크들(주로 단말 노드에 많음)을 원래 순회 과정에서 다음에 방문해야 할 노드(후속자)에 연결해놓기. 예를 들어 중위 순회이고 B - A - C 순서로 방문해야 한다면 실제 트리 구조상 연결 관계는 B ← A → C인데, 순회 순서에 맞게 B → A 링크를 만들어 둔다는 것. 이때 각 노드에 연결된 링크가 트리의 간선인지 순회를 위한 링크인지 구분하기 위한 필드 변수(bool)가 추가로 필요하다. 순회를 위해 연결하는 링크는 오른쪽 간선을 이용한다. 자세한 코드는 생략한다.