Tree란

트리(Tree)는 비선형구조로 하나의 루트 노드를 가지며, 루트 노드는 0개 이상의 자식 노드를 가지고 있습니다.
그리고 그 자식 노드 또한 0개 이상의 자식 노드를 가지고 있으며, 이는 반복적으로 정의됩니다.

• Root Node: 트리 구조에서 최상위에 존재하는 노드
• Node: 트리 구조의 구성 요소
• Edge: 노드와 노드를 연결하는 연결선
• Leaf Node(Terminal Node): 자식 노드가 없는 노드
• Sub-Tree: 큰 트리에 속하는 작은 트리

Tree의 종류

• 이진 트리
  • 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리를 말합니다.
• 이진 탐색 트리
  • 이진 탐색 트리는 모든 노드가 다음과 같은 특정 순서를 따르는 속성을 가진 이진 트리를 말합니다.
  • 모든 왼쪽 자식 노드 <= n < 모든 오른쪽 자식 노드 (모든 노드 n에 대해서 반드시 true)
• 균형 트리
  • O(logN) 시간에 insert와 find를 할 수 있을 정도로 균형이 잘 잡힌 트리를 말합니다.
  • ex) 레드-블랙 트리, AVL 트리

Binary Tree란

• 이진 트리는 위에서 설명했듯이 각 노드가 최대 두 개의 자식 노드를 가지는 트리를 말합니다.
  

Binary Tree의 종류

• 완전 이진 트리(Complete Binary Tree)
  • 트리의 마지막 레벨을 제외한 모든 레벨에서 노드가 꽉 채워져 있는 트리
  • 마지막 레벨의 노드는 모든 노드가 채워져 있지 않아도 되지만 좌측에서부터 채워져 있어야 함
• 전 이진 트리(Full Binary Tree)
  • 모든 노드가 0개 혹은 2개의 자식 노드를 가지는 트리
• 포화 이진 트리(Perfect Binary Tree)
  • 전 이진 트리이면서 동시에 완전 이진 트리인 경우 포화 이진 트리라고 함
  • 모든 노드가 두 개의 자식 노드를 가져야 함
  • 노드의 개수 = 2^(k-1)개 (k:트리의 높이)

Binary Tree 탐색

• 중위 순회(In-order traversal): 왼쪽 자손, 자신, 오른쪽 자손 순서로 방문하는 순회 방법. 이진 탐색 트리를 중위 순회하면 정렬된 결과를 얻을 수 있습니다.
• 전위 순회(Pre-order traversal): 자신, 왼쪽 자손, 오른쪽 자손 순서로 방문하는 순회 방법.
• 후위 순회(Post-order traversal): 왼쪽 자손, 오른쪽 자손, 자신 순서로 방문하는 순회 방법.
• 레벨 순서 순회(Level-order traversal): 너비 우선 순회(Breadth-First traversal)라고도 합니다. 노드를 레벨 순서로 방문하는 순회 방법. 위의 세 가지 방법은 스택을 활용하여 구현할 수 있는 반면 레벨 순서 순회는 큐를 활용해 구현할 수 있습니다.

Binary Search Tree 탐색

• 특정 키 값에 따라서 왼쪽의 서브트리 또는 오른쪽 서브트리를 recursive하게 탐색한다.
• 1.키 값이 현재 노드의 값보다 작으면 왼쪽의 서브노드로 내려가고, 아니면 오른쪽의 서브노드로 내려갑니다.
• 2.만약 키 값과 동일한 값의 노드를 찾았다면 탐색을 종료합니다.
• 3.키 값과 동일한 값의 노드를 찾지 못했다면 1번의 과정을 반복합니다.