이진 트리

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

컴퓨터 과학에서, 이진 트리(二進-, 영어: binary tree)는 모든 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조이다. 이 두 자식 노드를 왼쪽 자식 노드와 오른쪽 자식 노드라고 하며, 원래의 노드를 이들의 부모 노드라고 한다. 이진 트리는 이진 탐색 트리이진 힙의 구현에 흔히 쓰인다.

정의[편집]

(루트) 이진 트리(영어: (rooted) binary tree) 공집합이거나, 다음과 같은 세 가지 요소로 구성되는 자료 구조이다. (이는 재귀적인 정의이다.)

  • 노드 . 이를 루트 노드(영어: root node)라고 한다.
  • 이진 트리 . 이를 왼쪽 부트리(-副-, 영어: left subtree)라고 한다.
  • 이진 트리 . 이를 오른쪽 부트리(-副-, 영어: right subtree)라고 한다.

용어[편집]

  • 노드의 왼쪽 자식 노드(-子息-, 영어: left child node)는 왼쪽 부트리의 노드이다.
  • 노드의 오른쪽 자식 노드(-子息-, 영어: right child node)는 오른쪽 부트리의 노드이다.
  • 노드의 부모 노드(父母-, 영어: parent node)는 그 노드를 자식으로 하는 노드이다.
  • 형제 노드(兄弟-, 영어: sibling node)는 부모가 같은 두 노드이다.
  • 노드의 차수(次數, 영어: degree)는 자식의 수이다.
  • 단말 노드(端末-, 영어: external/leaf node)는 차수가 0인 노드이다. 즉, 자식이 없는 노드이다.
  • 내부 노드(內部-, 영어: internal/branch node)는 차수가 0이 아닌 노드이다. 즉, 자식이 있는 노드이다.
  • 방향 간선(方向幹線, 영어: directed edge)은 부모 노드가 첫째, 자식 노드가 둘째 원소인 순서쌍이다. 그림의 화살표라고 생각할 수 있다.
  • 경로(徑路, 영어: path)는 이웃하는 두 노드가 앞이 부모, 뒤가 자식인, 노드의 열이다.
  • 경로의 길이(영어: length)는 경로가 포함하는 방향 간선의 수이다. 특히, 시작점과 출발점이 같은 경로의 길이는 0이다.
  • 두 노드 사이에 양수 길이 경로가 존재한다면, 시작점 노드를 도착점 노드의 조상 노드(祖上-, 영어: ancestor node)이라고 하고, 반대로 도착점을 시작점의 자손 노드(子孫-, 영어: descendent node)이라고 한다.
  • 노드의 깊이(영어: depth)는 루트 노드에서 자신까지 가는 경로의 길이이다. 특히, 루트 노드의 깊이는 0이다.
  • 노드의 레벨(영어: level)는 루트 노드에서 자신까지 가는 경로의 길이 더하기 1이다. 특히, 루트 노드의 레벨은 1이다. 간혹 트리의 특정 깊이를 가지는 노드의 집합을 레벨이라고 하기도 한다.
  • 노드의 높이(영어: height)는 그 노드와 단말 노드 사이의 경로의 최대 길이이다.
  • 노드의 크기(영어: size)는 자기 자신 및 모든 자손 노드의 수이다.
  • 트리의 깊이와 레벨과 높이와 크기는 각각 노드의 길이와 레벨과 높이의 최댓값이다. 특히, 트리의 높이는 그 루트 노드의 높이와 같으며, 트리의 크기는 그 루트 노드의 크기와 같다.

종류[편집]

  • 루트 이진 트리(-二進-, 영어: rooted binary tree)는 이진 트리가 루트 노드를 가짐을 강조하기 위한 용어이다.
  • 정 이진 트리(整二進-, 영어: full binary tree)는 모든 노드의 차수가 0이나 2인 이진 트리이다.
  • 포화 이진 트리(飽和二進-, 영어: perfect binary tree)는 모든 단말 노드의 깊이가 같은 정 이진 트리이다.
  • 완전 이진 트리(完全二進-, 영어: complete binary tree)는 마지막 두 레벨을 제외한 모든 노드의 차수가 2이며, 마지막 레벨의 노드가 왼쪽에 몰려있는 이진 트리이다.
  • 무한 완전 이진 트리(無限完全二進-, 영어: infinite complete binary tree)는 모든 노드의 차수가 2인 이진 트리이다.
  • 균형 이진 트리(均衡二進-, 영어: balanced binary tree)는 모든 노드의 두 부트리의 레벨의 차가 1 이하인 이진 트리이다.
  • 변질 트리(變質-, 영어: degenerate tree)는 모든 노드의 차수가 0이나 1인 이진 트리이다. 즉, 연결 리스트 꼴의 이진 트리이다.

성질[편집]

  • 공집합이 아닌 이진 트리의, 차수가 0, 1, 2인 노드의 수가 라면, 가 성립한다.
  • 이진 트리의 노드의 수가 이라면, 공집합 부트리의 수는 이다.
  • 이진 트리의 높이가 라면, 노드의 수는 최소 , 최대 이다.
  • 정 이진 트리의 높이가 라면, 노드의 수는 최소 , 최대 이다.
  • 포화 이진 트리의 높이가 라면, 노드의 수는 이며, 말단 노드의 수는 이다.
  • 완전 이진 트리의 높이가 라면, 노드의 수는 최소 , 최대 이다.
  • 완전 이진 트리의 노드의 수가 이라면, 그 높이는 이며, 내부 노드의 수는 이다.
  • 완전 이진 트리의 노드에 0부터 시작하여 번호를 매긴다면, 째 노드의 자식 노드는 (존재한다면) 째 노드이며, 부모 노드는 (존재한다면) 째 노드이다.
  • 무한 완전 이진 트리의 노드의 수는 이며, 경로의 수는 이다.

이진 트리 탐색[편집]

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

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

표현 방법[편집]

이진 트리를 표현하는데는 크게 두 가지 방법이 있다.

  • 1차원 배열 표현: 이진 트리의 i번째 노드를 배열의 i번째 요소에 저장하는 방법이다.
  1. 장점: 노드의 위치를 색인에 의하여 쉽게 접근할 수 있다.
  2. 단점: 특정 트리에서 기억 공간의 낭비가 심할 수 있다.
  • 연결리스트 표현: 왼쪽 자식을 가리키는 포인터 필드와 오른쪽 자식을 가리키는 포인터 필드를 포함하는 노드로 표현하는 방법이다.
  1. 장점: 기억 장소를 절약할 수 있고, 노드의 삽입과 삭제가 용이하다.
  2. 단점: 이진 트리가 아닌 일반 트리의 경우에는 각 노드의 차수만큼 가변적인 포인터 필드를 가져야 하기 때문에 접근상의 어려움이 따른다.