#6 트리(Tree) 1 - 트리의 개념/이진 트리

2021. 10. 4. 15:23

트리는 그래프(Graph)와 유사한 형태를 가지며 어떤 의미로는 그래프의 일종이라고 볼 수도 있다.

다만 모든 노드가 동등한 관계였던 그래프와는 달리 트리의 노드는 서로 부모/자식의 관계를 가진다.

아래 예시를 보며 좀더 자세히 알아보자.

부모 노드를 가지지 않는 노드를 루트(root) 노드 라고 한다.
루트 노드를 제외한 모든 노드는 한 개의 부모 노드를 가진다.(두 개 이상의 부모 노드를 가질 수 없다)
자식 노드를 가지지 않는 노드들을 리프(leaf) 노드 라고 한다.
리프 노드를 제외한 모든 노드는 한 개 이상의 자식 노드를 가진다.
어떤 노드의 자식노드를 루트로 하는 트리를 그 노드의 서브 트리(subtree)라고 한다.
어떤 노드가 가지는 자식 노드의 갯수(혹은 서브트리의 갯수)를 노드의 차수(degree) 라고 한다.
트리 전체의 차수는 노드들의 차수 중 가장 큰 값이 된다.
루트 노드로부터 어떤 노드 까지 거쳐야하는 간선의 갯수를 그 노드의 깊이(depth) 라고 한다.
루트 노드의 깊이는 0이다.
서로 깊이가 같은 노드들의 집합을 레벨(level) 이라고 한다. 위 트리에서의 레벨 1에 해당하는 노드는
3, 2, 0 이 있다.

배열을 사용한 트리의 표현
- arr[0] 을 루트 노드로 한다
- 노드 arr[i] 의 좌측 자식 노드는 arr[i * 2 + 1], 우측 자식 노드는 arr[i * 2 + 2] 에 저장된다.
- 특수한 트리가 아니면 메모리의 낭비가 매우 심하다.
- 완전 이진 트리를 나타내는 경우라면 빈 공간이 없고 자식 노드를 가리키기 위한 포인터가
  필요하지 않기 때문에 효율적이다.
연결 리스트를 사용한 트리의 표현
- 자기 자신의 데이터와 좌측, 우측 자식노드를 가리키는 포인터를 가지는 노드 간의 연결로 표현한다.
- 정확히 노드의 수 만큼만 메모리를 차지하기 때문에 대부분의 경우 배열을 사용한 방식보다
  메모리 효율이 좋다.
- 특정 노드에의 접근이나 트리의 순회 등은 배열을 사용한 방식에 비해 느리다.

트리의 순회방법 네 가지에 대해 알아본다. 모든 순회는 루트 노드로부터 시작한다.

1) 전위 순회(Preorder Traversal)

2) 후위 순회(Postorder Traversal)

3) 중위 순회(Inorder Traversal)

4) 레벨 순회(Level-order Traversal)

1) 이진 트리(Binary Tree)

2) 이진 탐색 트리(Binary Search Tree)

어떤 노드의 좌측 서브 트리에는 자신보다 작은 값을 가지는 노드만이, 우측 서브 트리에는 자신보다 큰 값을
가지는 노드만이 존재하는 상태의 이진 트리이다.
균형이 잘 잡힌 이진 탐색 트리의 경우 트리 내의 특정 데이터를 탐색하는데 O(logN) 의 시간복잡도를 보인다.

3) 완전 이진 트리(Complete Binary Tree)

마지막 레벨을 제외한 레벨이 완전히 채워져있으며 마지막 레벨의 노드가 왼쪽에서부터 채워진 상태인
이진 트리이다.
배열로 표현했을 때 빈 칸이 생기지 않는 트리이다.
위 그림에서 A는 완전 이진 트리지만 B는 레벨 2가 완전히 채워지지 않았기 때문에, C는 마지막 레벨의 노드 8, 9 가
왼쪽에서부터 채워지지 않았기 때문에 완전 이진 트리가 아니다.

4) 정 이진 트리(Full Binary Tree)

5) 포화 이진 트리(Perfect Binary Tree)

6) 균형 이진 트리(Balanced Binary Tree)

명확한 정의가 있는 것은 아니지만 트리 B와 같이 치우친 상태가 아닌 A와 같이 균형을 이룬 상태의
이진 트리이다.
균형의 기준을 어떻게 세우느냐에 따라 다른 형태가 될 수 있지만 일반적으로는 모든 노드에 대해
좌측과 우측의 서브트리의 높이 차이가 일정이상 나지 않을 것을 기준으로 한다.

공부정리