Binary Tree
개념
- 가장 흔하게 사용되는 Tree의 형태
- 노드들은 2개의 Subtree를 가짐
- 2개의 Subtree들은 left와 right의 순서를 가짐
- 자식 노드를 하나도 가지지 않은 empty set 가능
구성요소
edge
- 노드의 개수가
n개라면 edge는n-1개 - 모든 노드는 부모로 연결되는 edge(=link)를 갖지만
root는 가지지 않으므로n-1개
height
- 한 Binary Tree의 height가
h라면 가능한 노드의 최대 개수는2^h -1개 - 모든 노드가 2개의 자식을 갖는다면 특정 레벨
l에서의 최대 노드의 개수는2^(l-1)개
Ex)root에서 레벨이 1이므로 노드의 개수2^0 = 1, 레벨이 3일 경우2^2 = 4 - 높이가
h일 경우1~h까지 모든 레벨에서의 노드 개수의 합이므로2^h -1
예시
레벨 1 : 1개 = 2^(1-1)
레벨 2 : 2개 = 2^(2-1)
레벨 3 : 4개 = 2^(3-1)
총합 7개 = 2^3 -1
종류
Full Binary Tree
- 모든 노드가 0개 또는 2개의 자식 노드를 가짐
- 1개의 자식을 갖는 노드가 있으면 Full Binary Tree가 아님
Complet Binary Tree
- 마지막 레벨을 제외하고 모든 레벨이 전부 채워진 상태
- 마지막 레벨은 전부 채워질 필요는 없지만
left to right의 순서를 따라 채워져야함
Perfect Binary Tree
- 모든 노드는 2개의 자식을 가지며 모든
leaf노드들은 동일한 레벨을 가짐 - Perfect Binary Tree일 경우 높이가
h일 경우 노드의 개수가2^h -1을 보장
구현
Array를 통한 구현
-
Array를 통해 Binary Tree를 구현하기 위해서는 높이가
h일 경우2^h -1크기를 할당해야함 -
각각의 값을 대응되는 인덱스에 저장
root: 1번 인덱스에 저장
Level 1: 2,3번 인덱스에 저장
Level 2: 4~8번 인덱스에 저장
...
(각 레벨당2^(l-1)개수의 메모리 공간을 할당) -
Complet Binary Tree나Prefect Binary Tree에는 적합 -
편향된 Binary Tree일 경우 사용하지 않는 배열 영역이 많아져 공간 활용에 불리함
-
0번 인덱스는 사용하지 않음
주변 노드의 인덱스
특정 노드의 인덱스가 i라고 가정
1. 부모 노드의 인덱스 : i/2
2. 자식 노드 중 left 노드의 인덱스 : 2*i
3. 자식 노드 중 right 노드의 인덱스 : 2*i +1
Linked List를 통한 구현
- Link 파트와 Data 파트로 구성된 노드를 통해 구현
- 메모리 공간 상에 산재하나 포인터를 통해 연결됨
