#19. 이진 트리(Binary tree)

이진 트리(Binary tree)

• 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.

 

관련 용어

• 왼쪽 자식 노드(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)
• 자손 노드(descendant node)
• 노드의 깊이(depth) : 루트 노드에서 자신까지 가는 경로의 길이 (루트 노드의 깊이는 0)
• 노드의 레벨(level) : 루트 노드에서 자신까지 가는 경로의 길이 + 1 (루트 노드의 레벨은 1)
• 노드의 높이(height)
• 노드의 크기(size) : 자기 자신 및 모든 자손 노드의 수

---

이진 트리의 종류

 

• 루트 이진 트리(rooted binary tree) : 하나의 루트 노드를 가지며 모든 노드가 최대 두 개의 자식 노드를 갖는다.
• 정 이진 트리(full binary tree, 때로는 proper 또는 plane 이진 트리라고도 함) : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
• 포화 이진 트리(perfect binary tree) :  모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎 노드가 동일한 깊이 또는 레벨을 갖는다.
• 완전 이진 트리(complete binary tree)
• 무한 완전 이진 트리(infinite complete binary tree)
• 균형 이진 트리(balanced binary tree)
• 변질 트리(degenerate tree, 또는 pathological tree) : 각 부모 노드는 오직 한 개의 연관 자식 노드를 갖는다. 

---

이진 트리의 속성

 

---

이진 트리 탐색

: 이진 트리의 모든 노드를 방문하는 것 혹은 방문하여 어떤 작업을 하는 것

 

• in-order(중위 순회) : 왼쪽 자식노드(L), 내 노드(P), 오른쪽 자식노드(R) 순서로 방문한다.
• pre-order(전위 순회) : 내 노드(P), 왼쪽 자식노드(L), 오른쪽 자식노드(R) 순서로 방문한다.
• post-order(후위 순회) : 왼쪽 자식노드(L),  오른쪽 자식노드(R), 내 노드(P) 순서로 방문한다.
• level-order(레벨 순회) : 내 노드(P), 내 노드로부터 깊이 1인 노드들, 내 노드로부터 깊이 2인 노드들, ... , 내 노드로부터 깊이 N인 노드들 (N: 나(트리)의 깊이)

---

표현 방법

1차원 배열 표현

• 이진 트리의 i번째 노드를 배열의 i번째 요소에 저장하는 방법
• 장점 : 노드의 위치를 색인에 의하여 쉽게 접근할 수 있다.
• 단점 : 특정 트리에서 기억 공간의 낭비가 심할 수 있다.

 

연결리스트 표현

• 왼쪽 자식을 가리키는 포인터 필드와 오른쪽 자식을 가리키는 포인터 필드를 포함하는 노드로 표현하는 방법
• 장점 : 기억 장소를 절약할 수 있고, 노드의 삽입과 삭제가 용이하다.
• 단점 : 이진 트리가 아닌 일반 트리의 경우에는 각 노드의 차수만큼 가변적인 포인터 필드를 가져야 하기 때문에 접근상의 어려움이 따른다.

---

References

 

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

이진 트리 - 위키백과, 우리 모두의 백과사전