트리 -> 배열(Array)로 구현 vs 연결리스트(Linked list)로 구현
1. 배열의 장점
- 배열로 구현할 때는 저장하고자 하는 데이터를 N개로 선언하고 N개만 받기에 부가적인 메모리를 사용하지 않아도 된다
- 트리 구조의 부모 / 자식 간의 이동이 간단한 연산만으로 가능
2. 배열의 단점
- 중간에 데이터가 삭제될 경우, 삭제할 데이터만 사라지는 것이 아닌 하위의 노드들도 자리를 옮겨 주어하고, 아래의 서브트리가 클 경우 오버헤드가 더 커지게 된다
- 완전 이진트리에서 거리가 먼, 편향이진트리 같은 형태가 될 경우 메모리 낭비가 발생된다
3. 연결리스트 장점
- 필요한 노드에 해당하는 메모리만 malloc 받으므로 메모리의 낭비가 없다
- 노드의 삽입, 삭제가 정확히 삽입되는 노드와 그 노드의 부모노드에게만 영향을 미치고 그 노드의 하위서브트리와는 아무 상관 없이 삽입/삭제가 자유롭게 가능
- 완전이진트리 또는 편향이진트리 두 경우 모두 정확히 필요한 만큼의 메모리만 사용
4. 연결리스트 단점
- 배열로 했을 때는 '데이터부'만 있으면 됐었지만, 연결리스트로 구현할 경우 '데이터부 + 양쪽의 링크부' 가 필요함으로 부가적인 메모리가 필요하다.
Jacob