이 페이지를 참고하여 정리하였습니다.
배열을 이용했을 때의 장점
-
자식 노드를 찾는 게 빠르다.
관련 포스트를 보시면 아시겠지만 부모 노드의 배열 인덱스가 k이면 왼쪽 자식 노드의 인덱스는 2k+1, 오른쪽 자식 노드의 인덱스는 2k+2입니다.
이 말은 곧, 왼쪽 자식 노드 값을 알기 위해서는 arr[2k+1], 오른쪽 자식 노드 값을 알기 위해서는 arr[2k+2]에 바로 직접 접근하면 된다는 뜻입니다.
또한, 왼쪽 자식 노드의 왼쪽 자식 노드를 알고 싶다면 그냥 arr[2*(2k+1)]에 접근하면 됩니다.
리스트의 경우에는 지속적으로 포인터 연산을 해야 되기 때문에 속도면에서는 당연히 배열 인덱스에 별다른 연산 없이(단순히 사칙 연산만 함) 직접 접근해버리는 배열을 이용한 구현이 더 앞설 것입니다.
-
힙(완전 이진 트리)을 구현하는데 더욱 효율적이다.
힙을 구현할 때는 보통 완전 이진 트리를 이용해서 구현합니다.
완전 이진 트리에는 중간 중간 빈 노드들이 없기 때문에 배열을 이용해서 구현하면 0번부터 마지막 잎 노드가 들어가 있는 인덱스까지 중간에 텅 비어있는 인덱스가 없습니다.
그리고, 완전 이진 트리에서 노드를 추가하는 것은 어차피 제일 오른쪽에 있는 잎 노드 옆에 새로운 노드를 붙이는 것이기 때문에 결국 arr[제일 오른쪽에 있는 잎 노드의 인덱스 + 1]에 새로운 데이터를 할당하는 것입니다.
만약, 완전 이진 트리를 구현하는데 리스트를 썼다면 왼쪽 오른쪽 자식 노드에 대한 포인터까지 들고 있어야 하므로 메모리적으로는 당연히 배열이 유리할 것입니다.
리스트를 이용했을 때의 장점
-
완전 이진 트리가 아닌 경우, 메모리적으로 더 효율적이다.
완전 이진 트리가 아닌데 만약 배열을 이용해서 구현한다고 가정해봅시다.
임의의 위치에 노드들을 삽입할 텐데 이렇게 되면 중간 중간 배열 인덱스가 텅 비어있게 됩니다.
예를 들어 보면 아래와 같습니다.
A(0) ↙ ↘ B(1) C(2)
이 트리에서 C에 오른쪽 자식 노드 D를 추가한다 하면 어떻게 될까요?
A(0) ↙ ↘ B(1) C(2) ↘ D(6)C의 인덱스는 2였으므로 일반식에 의해 D는 당연히 2*2+2 = 6, 배열의 6번 인덱스에 할당받을 것입니다.
이러면 결국, 배열의 3번, 4번, 5번 인덱스는 텅 비어있게 되고 메모리 낭비로 이어지게 됩니다.
만약 여기서 또 D에 오른쪽 자식 노드 E를 추가한다면 E는 6*2+2 = 12, 배열의 12번 인덱스에 할당받을 것이고, 배열의 7~11번의 인덱스는 또 메모리 낭비로 이어질 것입니다.
따라서, 완전 이진 트리가 아닌 경우에는 왼쪽과 오른쪽 자식 노드에 대한 포인터만 가지고 있으면 되는 리스트를 이용한 구현이 메모리적으로 효율적일 것입니다.
