이진트리(Binary Tree)란? - From 위키백과

From  https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC

이진 트리

위키백과, 우리 모두의 백과사전.

크기가 9이고, 높이가 3인 이진 트리

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

목차

  [숨기기] 

• 1정의
• 2종류
• 3특징
• 4이진 트리 탐색
• 5표현 방법

정의[편집]

• 방향 간선(directed edge)은 부모에서 자식으로 가는 경로를 가리킨다. (그림의 화살표 부분)
• 루트 노드(root node)는 부모가 없는 노드이다. 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node)는 자식이 없는 노드이다.
• 각 노드의 깊이(depth)는 루트 노드에서 자신까지 가는 경로의 길이이다. 트리의 특정 깊이를 가지는 노드의 집합을 레벨(level)이라 부르기도 한다. 루트 노드의 깊이는 0이다.
• 트리의 높이(height)는 루트 노드에서 가장 깊이 있는 노드까지 가는 경로의 길이이다. 루트 노드만 있는 트리의 높이는 0이다.
• 형제(sibling)은 같은 부모를 가지는 노드이다.
• 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)는 끝 부분(마지막 레벨)을 제외하고 모든 노드가 채워진(마지막 레벨을 제외하고는 모든 노드가 자식노드를 2개를 가진) 이진 트리. 마지막 레벨의 노드들은 왼쪽으로 채워져 있다. 마지막 레벨이 다 채워질 수도 있다.
• 무한 완전 이진 트리(infinite complete binary tree)는 레벨이 ${\displaystyle \aleph _{0}}$인 이진 트리에서, 각각의 레벨 d에 존재하는 모든 노드의 수가 ${\displaystyle 2^{d}}$인 트리이다. 모든 노드 집합의 기수는 ${\displaystyle \aleph _{0}}$이다. 모든 경로 집합의 기수는 ${\displaystyle 2^{\aleph _{0}}}$이다.
• 균형 이진 트리(balanced binary tree)는 모든 단말 노드의 깊이 차이가 많아야 1인 트리이다. 균형 이진 트리는 예측 가능한 깊이(predictable depth)를 가진다. 균형 트리의 노드의 개수를 n이라고 하면 깊이는 ${\displaystyle \lfloor log_{2}n\rfloor }$과 같다.
• 변질 트리(degenerate tree)는 각각의 부모 노드가 하나의 자식만을 갖는 트리이다. 이는 성능 측정에서, 트리가 연결 리스트와 같이 움직인다는 것을 의미한다.

특징[편집]

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

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

이진 트리 탐색[편집]

 이 부분의 본문은 트리 순회입니다.

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

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

표현 방법[편집]

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

• 1차원 배열 표현

이진 트리의 i번째 노드를 배열의 i번째 요소에 저장하는 방법이다.

1. 장점 : 노드의 위치를 색인에 의하여 쉽게 접근할 수 있다.
2. 단점 : 특정 트리에서 기억 공간의 낭비가 심할 수 있다.

• 연결리스트 표현

왼쪽 자식을 가리키는 포인터 필드와 오른쪽 자식을 가리키는 포인터 필드를 포함하는 노드로 표현하는 방법이다.

1. 장점 : 기억 장소를 절약할 수 있고, 노드의 삽입과 삭제가 용이하다.
2. 단점 : 이진 트리가 아닌 일반 트리의 경우에는 각 노드의 차수만큼 가변적인 포인터 필드를 가져야 하기 때문에 접근상의 어려움이 따른다.