[자료구조] 트리(Tree)

■ 트리 (Tree)

• 트리는 일반적으로 대상 정보의 각 항목들을 계층적으로 연관되도록 구조화시키고자 할 때 사용하는 비선형 자료구조이다.
• 데이터 요소들의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현이 된다.
• 트리는 그래프의 한 종류이며 사이클이 없다.

 

• [Tree 구조]

• Node: 트리를 구성하고 있는 각 요소
• Edge(간선): 트리를 구성하기 위해 노드와 노드를 연결하는 선
• Root Node: 최상위 계층에 존재하는 노드
• Level: 트리의 특정 깊이를 가지는 노드의 집합
• Degree(차수): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
• Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드
• Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.

 

---

 

▷ 이진트리 (Binary Tree)

• 이진트리는 트리를 구성하는 노드들의 최대 차수(degree)가 2인 노드들로 구성되는 트리이다.
  • 이진트리의 레벨 i에서 가질 수 있는 최대 노드의 수는 2^i이다. (i>=0)
  • 깊이가 k인 이진트리가 가질 수 있는 최대 노드의 수는 2^k-1이다.(k>=1)
• 이진트리는 완전 이진 트리(Completable Binary Tree)와 포화 이진 트리(Perfect Binary Tree), 전 이진 트리(Full Binary Tree)라고 하는 특별한 트리 구조를 정의할 수 있다.

▶ 완전 이진 트리

• 트리를 구성하고 있는 임의의 두 단말 노드의 레벨 차이가 1이하이고,
• 마지막 레벨을 제외한 모든 레벨에 존재할 수 있는 모든 노드를 갖고 있으며,
• 왼쪽에서 오른쪽으로 채워지는 이진트리
• heap

 

▶ 전 이진 트리

• 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

 

▶ 포화 이진 트리

• 모든 레벨에 노드가 차있는 상태로 최대 노드 수인 2^k-1개로 채워져 있는 트리
• 전 이진 트리이면서 완전 이진 트리인 경우

 

※ 이진 트리의 표현

1. 배열을 이용한 표현

• 빈 노드에 대해서는 계속 사용하지 않기 때문에 메모리 낭비
• 데이터의 삽입, 삭제 연산시 노드의 레벨 변경으로 인한 데이터의 이동 발생
• 연결리스트를 이용한 표현
• 각 노드는 data필드와 왼쪽 서브 트리를 가리키는 필드, 오른쪽 서브 트리를 가리키는 필드로 구성

 

※ 이진 트리 순회

 

	중위 순회 (inorder traversal)	후위 순회 (postorder traversal)	전위 순회(preorder traversal)
순서	왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리	왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트	루트 -> 왼쪽 -> 오른쪽
루트 노드	가운데	후위	맨 앞
결과	4-2-5-1-3	4-5-2-3-1	1-2-4-5-3

 

---

 

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

• 모든 노드가 자신의 왼쪽 서브트리에는 현재노드보다 작은 키값이, 오른쪽 서브트리에는 현재 노드보다 큰 값이 오는 규칙을 만족하는 이진트리이다.
• 모든 왼쪽 자식들 <= n < 모든 오른쪽 자식들 (모든 노드 n에 대해서 반드시 참)
  
  • 규칙 1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.
  • 규칙 2. 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.
  • 규칙 3. 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.
  • 규칙 4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

• 이진 탐색 트리의 탐색 연산은 평균 O(logn)의 시간 복잡도를 갖는다.
• 비교적 삽입, 삭제가 효율적인 자료구조이다.
• 이진 탐색 트리는 Skewed Tree(편향 트리)가 될 수 있다.
  • 저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 경우가 발생하기 때문.(O(n))
  • 이를 해결하기 위해 균형잡힌 이진검색트리를 고안. 대표적인 것은 Red-Black Tree와 AVL Tree다.
• 이진 탐색 트리는 이진 탐색을 쉽게 할 수 있도록 만들어진 트리이다.

 

▶ Red-Black Tree

• 레드블랙 트리는 자가균형이진탐색 트리(self-balancing binary search tree)로써, 대표적으로 연관배열(associative array) 등을 구현하는데 쓰이는 자료구조이다.

 

※ Red-Black Tree 특징

• balanced binary search tree
• 이진 탐색 트리가 편향 트리가 될 경우를 방지하는 조건을 추가함
  • 균형이 잡혀 위 그림 같은 경우가 안나온다 -> 레드블랙트리의 높이는 logn에 바운드 된다 -> 레드블랙트리에서 삽입, 삭제, 검색 연산은 O(logn)의 시간복잡도를 가지게 된다.
• 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다(worst-case guarantees).
  • 이는 실시간 처리와 같은 실행시간이 중요한 경우에 유용하게 쓰일 뿐만 아니라, 일정한 실행 시간을 보장하는 또 다른 자료구조를 만드는 데에도 쓸모가 있다.
  • 예를 들면, 각종 기하학 계산에 쓰이는 많은 자료 구조들이 레드-블랙 트리를 기반으로 만들어져 있다.

 

※ Red-Black Tree 조건

1. Root Property : 루트노드의 색깔은 검정(Black)이다.
   
   1. (추가되는 노드는 빨강이다)
2. External Property : 모든 external node들은 검정(Black)이다.
3. Internal Property : 빨강(Red)노드의 자식은 검정(Black)이다.
   
   1. == No Double Red (빨간색 노드가 연속으로 나올 수 없다.
4. Depth Property : 모든 리프노드에서 Black Depth는 같다.
   
   1. == 리프노드에서 루트노드까지 가는 경로에서 만나는 블랙노드의 개수는 같다. (그냥 노드의 수는 다를 수 있음.)

• 위 조건들을 만족하게 되면, 레드블랙 트리는 가장 중요한 특성을 나타내게 된다.
  • 루트 노드부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 두 배보다 항상 작다.
  • 다시 말해 레드블랙 트리는 개략적으로 균형이 잡혀있다.
  • 따라서, 삽입, 삭제, 검색 시 최악의 경우(worst-case)에서의 시간복잡도가 트리의 높이(깊이)에 따라 결정되기 때문에 보통의 이진검색 트리에 비해 효율적이다.

※ Double Red 해결 전략

• 연속해서 빨강 노드가 오게 되었을 때 해결 방법은 두가지 이다.
• 현재 insert된 노드의 uncle node(부모 노드의 형제 노드)fmf w 라고 할 때,
  • w==Black 👉 Restructuring
  • w==Red 👉 Recoloring
• 즉, insert노드의 uncle node의 색을 기준으로 해결 전략이 달라지게 된다.

 

※ Red-Black Tree 와 AVL Tree 의 차이

• AVL Tree가 Red Black Tree보다 빠른 Search를 제공
  • AVL Tree가 더 엄격한 Balanced를 유지하고 있기 때문
• Red Black Tree은 AVL Tree보다 빠른 삽입과 제거를 제공
  • AVL Tree보다 Balanced를 느슨하게 유지하고 있기 때문
• Red Black Tree는 AVL Tree보다 색깔을 저장하기 위해 더 많은 Space Complexity가 필요
• Red Black Tree는 대부분의 언어의 map, multimap, multiset에서 사용
• AVL tree는 조회에 속도가 중요한 Database에서 사용