용어 정리
노드
- 트리를 구성하는 요소
- 노드 중 가장 위에 있는 노드를 루트 노드라고 한다.
- 자식이 없는 말단 노드를 리프노드라고 한다.
에지
- 노드와 노드 사이를 이어주는 선(간선 또는 에지라고 함.)
- 트리는 노드가 단방향 간선으로 연결 되어 있고, 루트 노드에서 각 노드까지 경로는 유일하다.
부모-자식 관계
- 간선으로 연결 된 노드들은 서로 부모-자식 관계에 있다고 한다.
- 위의 노드를 부모 노드, 아래의 노르를 자식 노드라고 한다.
- 같은 부모를 갖는 노드는 형제 노드라고 한다.
이진트리 배열 표현
- 루트 노드는 배열 인덱스 1번에 저장한다.
- 시작 인덱스를 0으로 하면 특정 노드의 계산식이 달라지기 때문에 1로 시작하는 것이 간편하다. - 왼쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 * 2 이다.
- 오른쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 * 2 + 1 이다.
장점: 구현이 쉽다.
단점: 실제 노드개수보다 많은 공간을 사용해 낭비되는 메모리가 많다.
