이진 트리란?

이진 트리란?

●이진 트리란?

• 트리(Tree) 는 방향이 존재하는 그래프의 일종으로 부모 정점 밑에 여러 자식 정점이 연결되고, 자식 정점 각각에 다시 자식 정점이 연결되는 재귀적 형태의 자료구조이며, 그 중에서 각 정점이 최대 2개의 자식 정점을 가지는 트리를 이진 트리(Binary Tree)

●이진 트리의 종류

• 정점이 채워져 있는 형태에 따라서 대표적으로 포화 이진 트리, 완전 이진 트리, 편향 이진 트리가 존재

• 마지막 레벨까지 모든 정점이 채워져 있는 경우, 포화 이진 트리

        1                --- level 1
      /   \
    2       3            --- level 2
   / \     / \
  4   5   6   7          --- level 3
  

• 마지막 레벨을 제외하고 모든 정점이 채워져 있는 경우, 완전 이진 트리

        1                --- level 1
      /   \
    2       3            --- level 2
   / \     /
  4   5   6              --- level 3
  

• 한 방향으로만 정점이 이어지는 경우, 편향 이진 트리

    1                    --- level 1
     \
      2                  --- level 2
       \
        3                --- level 3
         \
          4              --- level 4
           \
            5            --- level 5
  

●이진 트리의 특징과 활용 사례

• 이진 트리의 정점이 N개인 경우, 최악의 경우 높이가 (N - 1)이 될 수 있음
• 포화 이진 트리와 완전 이진 트리의 높이는 log N
• 높이가 h인 포화 이진 트리는 2^(h + 1) - 1개의 정점을 가집
• 이진 트리는 다른 자료 구조를 만드는 경우에 주로 활용되며, 대표적으로 힙(Heap), 이진 탐색 트리(Binary Search Tree)가 존재

●이진 트리의 탐색 방법

• 이진 트리를 탐색하기 위한 방법으로 중위 순회(in-order), 전위 순회(pre-order), 후위 순회(post-order), 층별 순회(level-order)가 존재

• 중위 순회는 왼쪽 정점, 부모 정점, 오른쪽 정점 순서로 방문

• 전위 순회는 부모 정점, 왼쪽 정점, 오른쪽 정점 순서로 방문

• 후위 순회는 왼쪽 정점, 오른쪽 정점, 부모 정점 순서로 방문

• 층별 순회는 시작 정점의 레벨을 순서대로 모두 방문하고, 이후에 다음 레벨의 정점을 순서대로 방문(층별로 방문)