프롤로그
이 내용은 개인학습을 위해 기록했으며, 문제 시 수정하겠습니다!
이진 트리란?
이진트리(Binary Tree)는 트리 중에서도 각 노드가 최대 2개의 자식노드를 가질 때 이진트리라고 한다.
최대 2개이기 때문에 자식이 없을 수도 있고, 한개만 있을 수도 있다.
이때 자식노드는 각각 왼쪽 자식노드와 오른쪽 자식노드로 표현한다.
그래서 같은 루트에 같은 자식노드 하나를 가지고 있어도
자식노드의 위치가 각각 왼쪽과 오른쪽으로 다르다면?
서로 다른 트리가 된다.
출처:https://rosweet-ai.tistory.com/55
이진트리의 종류
1) 정 이진트리 (Full Binary Tree)
이진트리 중에서도 모든 노드가 2개의 자식을 가지거나 자식이 없는 경우에는 정 이진트리 또는 엄격한 이진트리라고 한다.
출처:https://rosweet-ai.tistory.com/55
용어 정리
루트 노드 (root node, 뿌리)
- 부모가 없는 최상위 루트 노드(트리 자료구조의 진입 노드) : root node
리프 노드 (leaf node, 잎)
- 맨 마지막 끝 노드 : leaf node
왼쪽 트리 - 자식을 한 개만 가지는 노드가 있어서 정이진트리가 안됨
오른쪽 트리 - 모든 노드들이 자식을 2개 또는 아예 가지고 있지 않아서 정이진트리가 됨.
이진 트리의 높이가 h라면, 노드의 수는 최소 h, 최대 2^(h+1)-1이다.
2) 포화 이진트리(Perfect Binary Tree)
이진트리 중 모든 노드가 2개의 자식을 가지고 leaf 노드가 모두 같은 레벨일 때, 포화 이진트리라고 한다.
포화 이진트리의 높이가 h인 포화 이진트리의 노드 수는 2^(h+1)-1이며, leaf 노드 수는 2^h
3) 완전 이진트리(Complete binary tree)
이 트리는 두 가지 조건을 충족해야 되는데,
-
마지막 레벨을 제외하고 모든 노드가 채워져있어야한다. 마지막 레벨의 노드는 다 채워져 있을수도, 아닐 수도 있다.
-
노드는 왼쪽에서 오른쪽 방향으로 채워져야 한다. 그래서 어느 노드에 오른쪽 자식이 존재한다면 왼쪽 자신도 가지고 있어야 완전 이진트리로 볼 수 있다.
출처: https://rosweet-ai.tistory.com/55
왼쪽 그림 - 왼쪽 자식이 하나만 있지만, 왼쪽에서 오른쪽으로 채워져있기 떄문에, 완전이진트리 조건을 충족한다.
오른쪽 그림 - 자식이 2개 거나 아예 없거나인 포화이진트리도 완전이진트리의 조건을 충족한다.
but, 완전 이진트리라고 해서 포화 이진트리라는 역은 성립 안되는데, 왼쪽 그림은 완전 이진트리지만, 포화 이진트리는 아닌 것을 보면 알 수 있다.
이진트리의 특징
1) 1차원 배열로 표현 할 수 있다.
이진트리는 트리지만, 선형자료구조인 1차원 배열로도 표현할 수 있다는 특징을 가졌다.
출처: https://rosweet-ai.tistory.com/55
루트에서 시작해서 왼쪽노드부터 오른쪽 노드까지 순서를 매기면, 완전 이진트리 같은 경우 빈 숫자가 없게 된다.
그래서 완전 이진트리는 각 번호를 인덱스로 써서 1차원 배열로 표현이 가능하고, 빈틈없이 값을 채운 배열이 될 수 있다.
중간에 빈 값이 있는 이진트리는 배열로 표현하면 비어있는 공간의 인덱스에 null 값이 들어간 1차원 배열로 표현이 가능하다.
출처: https://rosweet-ai.tistory.com/55
1차원 배열로 이진트리를 표현할 때 0번째 인덱스를 비우고, 첫번째 인텍스부터 루트값이 들어간다.
이진트리의 단점
1차원 배열로 이진트리를 표현하면 간단하게 트리를 나타낼 수 있다는 장점이 있지만, 배열의 한계인 공간의 제약이나 데이터의 삽입, 삭제시 기존 데이터의 이동 같은 단점 극복이 어려워 트리는 배열보다 노드의 연결로만 표현한다.
참고 자료 :
https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC
https://rosweet-ai.tistory.com/55
http://www.ktword.co.kr/test/view/view.php?no=4726
