최종 수정 : 25.1.2
이진 트리의 저장
이진 트리의 표현방법은 기억장소에 저장하는 방법과 동일하며, 이는 일차원 배열과 연결 리스트로 표현하는 방법이 있다.
1. 배열을 이용한 저장
일차원 배열로 표현하는 방법은 완전 이진 트리의 레벨 오더의 순서를 배열의 인덱스로 사용하여 나타낸다 레벨 오더란 상위에서 하위로 같은 레벨은 왼쪽부터 오른쪽으로 운행하는 것이다.
레벨 오더에 따라 저장되는 전이진 트리는 기억효율이 매우 좋다. 이와 달리, 편향 트리와 같이 빈 노드가 많고, 트리의 깊이가 깊어질수록 저장 공간의 낭비가 심하다.
이진 트리를 일차원 배열로 푷표현하는 경우는 어떠한 이진 트리도 사용이 가능하다는 점과 완전 이진 트리에는 기억 공간의 낭비가 없어 최적이다. 반면에 편향이진 트리에서는 배열 공간의 낭비가 심하다. 또한, 트리의 중간에 노드의 삭제나 삽입의 경우, 많은 다른 노드의 이동이 불가피하다는 점이 트리를 배열로 표현했을 경우의 단점이다.
2. 연결 리스트를 이용한 저장
트리를 일차원 배열로의 표현하는 경우는 완전 이진 트리 외에는 저장 공간의 낭비가 심하여 트리의 또 다른 표현방법으로 연결 리스트를 사용한다. 각 노드를 3개의 필드 left, data, right로 구성하여 left와 right는 각각 왼쪽 서브 트리와 오른쪽 서브 트리를 가리키는 링크를 저장한다. left는 왼쪽 자노드를 가리키고, right는 오른쪽 자노드를 가리키게 된다. 만약, 자노드가 없는 경우는 null 값을 가지게 된다. 이렇게 하면, 트리를 일차원 배열로 표현했을 경우보다 저장 공간의 낭비가 적고, 편향 이진 트리의 경우에 저장 공간이 효율적이다.
참고
독학사 교재
댓글