이진트리의 개념과 구조
사실 트리에는 이진 트리만 있는 것이 아니다.
삼진 트리도 있고 십육진 트리도 있을 것이다. 그러나 우리가 가장 잘 알아야 하는 이진트리에 대해 가장 먼저 살펴보기로 하고 다른 구조를 갖는 트리들은 어디에 쓰이는지 나중에 또…. 공부할 기회가 뭐 있겠죠.
우선 트리에서 사용하는 용어들을 잠깐 살펴봅시다.
기본 용어와 개념들
노드
- 우리가 트리에서 가장 쉽게 보는 그 동글뱅이.
노드에도 몇 가지 종류가 있음.
계층에 따른 노드 구분
- 부모 노드 : 자식을 1개 이상 갖고 있는, 즉, 하위레벨에 노드가 한 개라도 있는 모든 노드
- 자식 노드 : 상위 노드를 갖고 있는, 즉 부모 노드가 아닌 노드
특성에 따른 노드 구분
- 루트 노드 : 트리의 최상단에 위치하는 노드. 각 트리별로 하나 뿐이다.
- 단말 노드 : 마지막 노드. 최하위 노드. 자식이 없는 노드이다.
- 내부 노드 : 단말 노드를 제외한 모든 노드.
- 형제 : 같은 부모를 갖고 있는 두 개의 노드.
노드의 ~
- 크기 : 자신을 포함한 자손들의 총 갯수.
- 깊이 : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 링크의 수
- 차수 : 노드가 가진 가지의 수
링크
- 노드를 이어주는 선
n개의 노드를 갖는 트리에서, 링크의 갯수는n-1개임
레벨
- 같은 깊이에 있는 노드들의 총 집합
- 최상단이 레벨 1부터 시작, 아래로 내려갈때마다 1씩 커짐
이진 트리의 종류
포화 이진 트리 : 모든 레벨에서 노드들이 꽉 채워진 상태.
- 높이가 h인 포화 이진 트리는 2^h - 1 개의 노드를 가짐.
완전 이진 트리 : 마지막 레벨을 제외하고 모든 노드가 채워짐, 마지막 레벨도 다 채워져도 무방.
편향 트리 : 보시다시피….
- 트리 최악의 경우가 발생 : 최악의 경우 노드가 N개인 이진 트리의 높이는 O(N)이 될 수도 있음.
- 포화 트리, 혹은 완전 트리의 경우 : O(logN)