이진 트리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
크기가 9이고, 높이가 3인 이진 트리

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

정의[편집]

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

종류[편집]

  • 루트를 가진 트리(rooted binary tree)는 모든 노드의 자식이 최대 2개인 루트를 가진 트리(rooted tree)이다.
  • 전 이진 트리(full binary tree)는 단말 노드가 아닌 모든 노드가 2개의 자식을 가진 트리이다.
  • 포화 이진 트리(perfect binary tree)는 모든 단말 노드의 깊이가 같은 전 이진 트리이다.
  • 완전 이진 트리(complete binary tree)는 포화 이진 트리에서 끝 부분을 제외하고 다른 것이 남아 있는 트리이다. 포화 이진 트리의 각 노드에 부모에서 자식으로, 왼쪽에서 오른쪽으로 번호를 매겼을 때 포화 이진 트리는 아니지만 그 번호가 연속되어 있는 경우 완전 이진 트리가 된다.
  • 무한 완전 이진 트리(infinite complete binary tree)는 레벨이 \aleph_0인 이진 트리에서, 각각의 레벨 d에 존재하는 모든 노드의 수가 2^d인 트리이다. 모든 노드 집합의 기수\aleph_0이다. 모든 경로 집합의 기수는 2^{\aleph_0}이다.
  • 균형 이진 트리(balanced binary tree)는 모든 단말 노드의 깊이 차이가 많아야 1인 트리이다. 균형 이진 트리는 예측 가능한 깊이(predictable depth)를 가진다. 균형 트리의 노드의 개수를 n이라고 하면 깊이는 \lfloor log_2 n \rfloor과 같다.
  • 변질 트리(degenerate tree)는 각각의 부모 노드가 하나의 자식만을 갖는 트리이다. 이는 성능 측정에서, 트리가 연결 리스트와 같이 움직인다는 것을 의미한다.

특징[편집]

트리의 높이를 h라고, 트리에 존재하는 모든 단말 노드의 개수를 L이라고 할 때,

  • 포화 이진 트리의 노드의 개수는 2^{h+1}-1이다.
  • 완전 이진 트리의 노드의 개수는 2^h에서 2^{h+1}-1 사이의 값을 가진다.
  • 포화 이진 트리의 노드의 개수는 또한 2L-1로 나타낼 수 있다.
  • 포화 이진 트리의 단말 노드의 개수는 2^h이다.

이진 트리 탐색[편집]

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

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