[Algorithms] 이진트리(Binary tree)

                                                                                                                                                         

                                                                                                                                                                                                                   

                                                                                                                                                         

                                                                                                                                                                                                             

                                                                                                                                                                                                          

 

 

이진 트리(binary tree)란 한 노드가 최대 두 개의 자식 노드를 가지는 트리를 말한다. 보통 첫 번째 노드를 부모 노드라고 하며 자식 노드는 왼쪽 노드(left noe)와 오른쪽 노드(right node)로 부른다. 이진 트리는 이진 탐색 트리와 이진 힙의 구현에 흔히 쓰이는 자료구조다.

 

 

용어정의

• 방향 간선(directed edge) : 부모 노드에서 자식 노드로 가는 경로를 가리킨다. 위 그림에서 화살표로 표현되어 있다.
• 루트 노드(root node) : 자신의 위로 부모 노드가 없는 노드다. 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node) : 자식 노드가 없는 노드다.
• 노드의 깊이(depth) : 루트 노드에서 특정 단말 노드까지의 길이다. 레벨(level)이라고 부르기도 한다. 루트 노드의 깊이는 0이다.
• 트리의 높이(height) : 루트 노드에서 단말 노드까지의 길이다. 루트 노드만 있는 트리의 높이는 0이다.
• 형제(sibling) : 같은 부모를 가지는 노드를 말한다.
• p에서 q까지 가는 경로가 존재할 때, p가 q보다 루트에 가까운 노드라면 p를 q의 조상(ancestor)이라 하며, q를 p의 자손(descendent)이라고 부른다.
• 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수다.
• 노드의 진입차수(In-degree) : 노드에 들어오는 모든 간선의 개수다.
• 노드의 진출차수(Out-degree) : 노드로부터 나가는 모든 간선의 개수다.
  
  

---

이진 트리 탐색

이진 트리의 모든 노드를 방문하는 것, 혹은 방문하여 어떤 작업을 하는 것을 이진 트리 탐색이라고 한다. 이진 트리 탐색의 방법에는 다음의 것들이 있다.

• in-order : 왼쪽 자식노드, 내 노드, 오른쪽 자식노드 순서로 방문
• pre-order : 내 노드, 왼쪽 자식노드, 오른쪽 자식노드 순서로 방문
• post-order : 왼쪽 자식노드, 오른쪽 자식노드, 내 노드 순서로 방문
• level-order : 내 노드, 내 노드로부터 깊이 1인 노드들, 내 노드로부터 깊이 2인 노드들, … , 내 노드로부터 깊이 N인 노드들 (N: 나(트리)의 깊이)
  
  

이진트리에서 ‘균형이 맞지 않다’는 것은 루트높이를 기준으로 왼쪽트리와 오른쪽트리의 높이의 차이가 2 이상 나는 것을 말한다. 그 이하의 차이는 허용범위다. 
이진트리에서 최악의 경우 O(N)의 성능을 보이는데, 이런 경우는 모든 노드들이 오른쪽으로 쏠리는 등의 극단적으로 트리의 균형이 깨져버려 선형검색이 되어 버린 경우를 말한다. 이를 방지하기 위한 방법은 항상 트리의 균형을 유지하는 것이다. 그럴 경우 O(logN)의 성능을 보장하게 된다. 균형을 유지하는 트리는 대표적으로 AVL트리, 2-3트리, 2-3-4트리, Red-black트리 그리고 B-트리 등이 있다.