자료 구조 - 트리

‘c++로 쉽게 풀어쓴 자료구조 1판 - 천인국, 최영규’ 책을 참고하여 작성한 포스트입니다.

트리

스택, 큐, 리스트는 모두 자료들이 일렬로 나열된 형태인 선형 자료구조(linear data structure)이다.
트리(tree)는 계층적인 구조(hierarchical structure)에 속한다.

트리의 용어들

노드

• 트리의 구성 요소. 트리는 한 개 이상의 노드로 이루어진 유한 집합이다.

  루트(root) 노드

• 계층적인 구조에서 가장 높은 곳에 있는 노드

  서브트리

• 루트 노드를 제외한 나머지 노드들

  간선 또는 에지(edge)

• 트리에서 루트와 서브트리를 연결하는 선

  부모 노드, 자식 노드, 형제 관계, 조상 노드, 자손 노드

  단말 노드(terminal node or leaf node)

• 자식 노드가 없는 노드

  비단말 노드

• 단말 노드의 반대

  노드의 차수(degree)

• 어떤 노드가 가지고 있는 자식 노드의 개수

  트리의 차수

• 트리가 가지고 있는 노드의 차수 중 가장 큰 차수

  레벨(level)

• 트리의 각 층에 번호를 매기는 것. 루트의 레벨은 1이고 한 층씩 내려갈수록 1씩 증가

  높이(height)

• 트리가 가지고 있는 최대 레벨

트리의 표현

가장 일반적인 트리 표현 방법은 연결 리스트와 유사한 방법으로 링크에 자식 노드들을 연결하는 방법이다.
실제로는 두 개의 자식 노드를 사용하는 이진트리(binary tree)가 많이 사용된다.

이진 트리

이진트리(binary tree)는 모든 노드가 2개의 서브트리를 갖는 트리로, 이때 서브트리는 공집합일 수도 있다. 자식 노드가 두개 이하란 뜻! 서브트리 간의 순서가 존재하는데, 왼쪽 서브트리와 오른쪽 서브트리는 반드시 서로 구별되어야 한다.

• 이진트리는
  1. 공집합 이거나
  2. 루트와 왼쪽 서브트리, 오른쪽 서브트리로 구성된 노드들의 유한 집합으로 구성된다.
  3. 이진트리의 서브트리들은 모두 이진트리여야 한다.

이진트리의 성질

• n개의 노드를 가진 트리는 n-1개의 간선을 가진다. 루트를 제외한 트리의 모든 노드가 하나의 부모 노드를 가지기 때문!
• 높이가 h인 이진트리는 h개 이상, $2^h - 1$개 이하의 노드를 가진다.

  포화 이진트리(full binary tree)

• 각 레벨에 노드가 꽉 차있는 이진트리

  완전 이진트리(complete binary tree)

• 마지막 레벨을 제외하고 모든 레벨에 노드가 꽉 차있고, 마지막 레벨은 노드들이 왼쪽에서 오른쪽으로 순서대로 채워져 있는 트리
• 힙(heap)이 완전 이진트리의 대표적인 예이다.

이진트리의 추상 자료형

데이터: 노드와 간선의 집합, 노드는 공집합이거나 공집합이 아닌 경우 루트노드와 왼쪽 서브트리, 오른쪽 서브트리로 구성됨. 이때 모든 서브트리도 이진트리여야 함.
연산
 - create(): 이진트리를 생성한다
 - isEmpty(): 이진트리가 공백 상태인지 확인한다. 
 - getRoot(): 이진트리의 루트 노드를 반환한다.
 - getCount(): 이진트리의 노드의 수를 반환한다.
 - getHeight(): 이진트리의 높이를 반환한다.
 - insertNode(n): 이진트리에 노드 n을 삽입한다.
 - deleteNode(n): 이진트리에 노드 n을 삭제한다.
 - display(): 이진트리의 내용을 화면에 출력한다.

이진트리의 표현

배열 표현법

완전 이진트리를 예로 가정하고, 이진트리의 높이가 k일 떄 노드의 개수는 $2^k-1$개 이므로, 배열의 공간을 $2^k-1$만큼 할당한다. 완전 이진트리의 번호대로 노드의 정보를 배열에 저장한다. 그러면,

• 노드 i의 부모 노드 인덱스 = i/2
• 노드 i의 왼쪽 자식 노드 인덱스 = 2i
• 노드 i의 오른쪽 자식 노드 인덱스 = 2i+1

하지만 배열 표현법은 기억공간의 낭비와 함께 표현할 수 있는 트리의 높이가 배열의 크기에 따라 제한되는 단점 때문에 많이 사용되지는 않는다.

링크 표현법

노드는 두 개의 포인터 변수를 가지며 각각 왼쪽 자식 노드와 오른쪽 자식 노드를 가리킨다.

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

이진트리 구현(순회 포함)

이진트리의 순회

트리를 순회(traversal)한다는 것은 트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 말한다.

이진트리 순회 방법

• 이진트리를 순회하는 표준적인 방법에는 전위, 중위, 후위의 3가지 방법이 있다. 루트 방문 작업을 V, 왼쪽 서브트리 방문을 L, 오른쪽 서브트리 방문을 R이라고 하면,
  • 전위 순회(preorder traversal) : VLR
  • 중위 순회(inorder traversal) : LVR
  • 후위 순회(postorder traversala) : LRV
    이다.
• 이진 트리를 보면 전체 트리나 서브트리나 그 구조는 완전히 동일하다. 따라서 전체 트리 순회에 사용된 알고리즘은 똑같이 서브트리에 적용이 가능하다. 순환이 최선의 해결책이다.

전위 순회(preorder)

• 전위 순회에서 루트 노드의 방문을 마쳤다고 가정하자. 그러면 왼쪽 서브트리를 방문할 차례다.
• 왼쪽 서브트리도 하나의 이진트리이다. 왼쪽 서브트리의 루트를 먼저 방문하고,
• 왼쪽 서브트리의 왼쪽 서브트리를 그 다음에, … 반복하면 된다.

  중위 순회(inorder)

• 왼쪽, 루트, 오른쪽 순서로 순회한다.

  후위 순회(postorder)

• 왼쪽, 오른쪽, 루트 순으로 순회한다.

순위 방법의 선택

• 순서는 중요치 않고 전부 방문해야 된다면 어떤 방법을 택해도 상관 없다.
• 자식 노드를 처리한 다음 부모 노드를 처리해야 하는 상황이라면 후위 순회를 택해야 한다.
• 부모 노드를 처리한 후 자식 노드를 처리해야 한다면 전위 순회를 택해야 겠죠

이진트리 연산

트리의 노드 개수 구하기 (해보기!!)

단말 노드 개수 구하기 (해보기!!)

높이 구하기 (해보기!1)

이진트리 응용

수식 트리

• 이진 트리로 수식 트리(expression tree)를 구현할 수 있다.
• 이 때 전위 , 중위, 후위 순회에 따라 각각 전위, 중위, 후위 표기 수식이 된다.
  • 스택을 이용해 후위 표기로 계산했었죠

수식 트리 후위 표기 통한 계산 구현해 보기 ( 해보기!! )

스레드 이진트리

• 트리 노드를 중위 순회할 때 노드 바로 앞에 방문하는 노드를 중위 선행자(inorder predecessor)라고 하고 바로 다음에 방문하는 노드를 중위 후속자(inorder successor)라고 한다.
• 스레드 이진트리는 링크 값이 NULL을 갖는 대신 중위 선행자나 중위 후속자를 저장시켜 놓는다.
  • 이 경우 링크가 자식 노드를 가리키는 지 스레드가 저장되어 있는 지 구별해주는 필드(보통 boolean)가 있어야 하겠죠

스레드 이진트리 구현해보기 (해보기 !!)

문제

1. 이진트리 클래스 확장

1. 이진트리가 완전 이진트리인지 검사하는 연산 구현
   • bool isFull()
2. 임의의 node의 레벨 구하는 연산 구현. 노드가 트리 안에 없으면 0 반환
   • int level(Node* node)
3. 이진트리가 균형 잡혀 있는 지 검사. 왼쪽 서브트리와 오른 쪽 서브트리의 높이의 차이가 2보다 작으면 균형 잡혀 있는 트리임
   • bool isBalanced()
4. 루트에서부터 모든 자식 노드까지의 경로의 길이의 합 구현. 높이가 3인 포화 이진 트리의 경우엔 0+1+1+2+2+2+2 = 10 이다.
   • int pathLength()
5. 이진트리를 좌우로 대칭시키는 연산 구현
   • bool reverse()
6. 현재 트리와 that 트리가 같은 노드를 가지지 않으면 서로 분리되어(disjoint) 있다고 하는데, 이를 판단하는 연산을 순환을 이용해 구현
   • bool isDisjointFrom(Binarytree* that);
7. 모든 서브트리가 서로 분리되어 있으면 트리가 유효하다(valid)라고 판단한다. 이를 판단하는 연산 구현
   • bool isValid()