이진 트리 (Binary Tree)

트리(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)

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

Loading comments...