트리(Tree)

트리(Tree)

트리 자료구조는 계층 구조를 가지는 비선형 자료구조이다. 컴퓨터과학 분야에서 다양하게 활용이 되고 있다. 예를 들면, 파일 시스템, 디렉토리 구조, 데이터베이스 인덱스, 그래프 알고리즘등에 사용이 되고 있다.

 

트리는 하나의 루트(Root) 노드와 루트 노드를 중심으로 여러 개의 자식 노드들이 있는 노드들로 이루어져 있다. 각 노드는 다수의 자식 노드를 가질 수 있지만, 하나의 부모 노드만 가질 수 있다.

용어

• 노드(Node) : 트리 구조의 자료값을 담고 있는 단위
• 엣지(Edge) : 노드 간의 연결선(= link, branch)
• 루트 노드(Root) :  부모가 없는 노드, 가장 위의 노드 
• 잎새 노드(Leaf) : 자식이 없는 노드 (= 단말)
• 내부 노드(Internal) : 잎새 노드를 제외한 모든 노드

• 부모(Parent) : 연결 된 두 노드 중 상위노드
• 자식(Child) : 연결 된 두 노드중 하위노드
• 형제(Sibling) : 같은 부모를 가지는 노드

• 깊이(Depth) : 루트에서 어떤 노드까지의 간선의 수
• 레벨(Level) : 트리의 특정 깊이를 가지는 노드 집합
• 높이(Height) : 트리에서 가장 큰 레벨의 값
• 크기(Size) : 자신을 포함한 자식 노드의 개수
• 차수(Degree) : 각 노드가 지닌 가지의 수
• 트리의 차수 : 트리의 최대 차수

특징

• 하나의 노드에서 다른 노드로 이동하는 경로는 유일하다.
• 노드가 n개인 트리의 Edge 수는 N-1 개 이다.
• Acyclic한 자료구조이다. (원형구조가 아니다)
• 모든 노드는 서로 연결되어져 있다. 
• 하나의 Edge를 끊으면 2개의 sub- tree로 분리가 된다.

 

Sub-tree
트리 자료구조에서 Sub-Tree는 트리 안에 존재하는 또 다른 트리를 의미한다. Sub-Tree는 부모 노드와 그 자식 노드들로 이루어진 하위 트리를 말한다. 즉, 트리의 일부분이 자체적으로 하나의 트리를 형성하는 것이다. 

---

이진 트리(Binary Tree)

이진트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조이다. 각 노드는 왼쪽 자식 노드와 오른쪽 자식 노드를 가질 수 있으며, 자식 노드가 없는 경우도 있다. 

 

 

이진트리 종류

• 포화 이진 트리(Perfect binary Tree) 

모든 레벨에서 노들이 꽉 채워져 있는 트리를 말한다. 즉, 모든 내부 노드가 두 개의 자식 노드를 가지며, 모든 리프 노드는 같은 레벨에 있다.

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

완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 이진 트리이다. 마지막 레벨은 왼쪽부터 순서대로 채워져 있어야 하며, 노드가 없는 자리는 채워지지 않는다. 

• 정 이진 트리(Full Binary Tree)

정 이진 트리는 모든 내부 노드가 두 개의 자식 또는 0개의 자식 노드를 갖는 트리를 말한다.

• 편향 트리(Skewed Tree) - 사향트리

모든 노드가 한 쪽 방향으로만 자식 노드를 가지는 비균형 이진트리이다. 보통 왼쪽또는 오른쪽 방향으로 자식 노드를 가지며, 한쪽 방향으로만 자식 노드를 가지는 경우는 편향되었다고 표현한다.

• 균형 이진 트리(Balance Binary Tree) 

균형 이진 트리는 모든 리프 노드의 깊이 차이가 1이라인 이진 트리이다. 즉, 루트 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리의 깊이 차이가 1이하인 트리를 말한다.  

왼쪽은 불균형, 오른쪽은 균형

특징

• 포화이진 트리의 높이가 h일 때, 노드의 수는 2^(h+1) - 1 개 이다. 
• 포화 (or 완전) 이진 트리의 노드가 N개 일 때, 높이는 logN이다. 
• 이진 트리의 노드가 N개 일때, 최대 가능 높이는 N-1이다. (편향트리)

 

이진트리의 순회(Traversal)

• 모든 노드를 빠트리거나 중복하지 않고 방문하는 연산
• 순회 종류는 4가지가있다.
  • 전위순회(Preorder Traversal)
  • 중위순회(Inorder Traversal)
  • 후위순회(Postorder Traversal)
  • 레벨순회(Levelorder Traversal)

이진트리 구현

배열로 구현이 가능하며 레벨 순회순으로 배열에 구성한다. 

• 부모노드값 찾아가는 공식 : index / 2
• 부모노드에서 왼쪽 자식 노드 찾아가는 공식 : index * 2 + 1
• 부모노드에서 오른쪽 자식 노드 찾아가는 공식 : index * 2 + 2