비순차적(비선형) 자료구조 - 트리
순차적 자료구조는 어떠한 '순서'를 가지고 데이터가 저장 공간에 저장되었습니다. 비순차적 자료구조는 트리구조와 같이 계층적 구조를 가지는 자료구조입니다. 한 노드의 다음의 노드가 여러 개일수 있기 때문에 탐색을 구현하기 복잡하지만, 메모리를 좀 더 효율적으로 활용할 수 있다는 장점이 있습니다.
트리
가계도나 회사 조직도와 같이 위아래의 개념을 컴퓨터로 표현한 자료구조이며, 루트 노드와 부모-자식 관계의 서브 트리로 구성됩니다.
- 간선(엣지, 링크) : 노드 사이의 연결을 의미
- 크기 : 자신을 포함한 자식 노드의 개수
- 루트 : 최상위 노드
- 리프 : 가장 하위에 있는 노드들
- 높이 : 루트 노드부터 가장 멀리 떨어진 리프까지 간선의 수. 가장 높은 레벨과 동일함
- 깊이 : 현재 노드에서 목적지 노드까지 간선의 수
- 차수 : 한 노드와 연결된 간선의 수
트리 구현
파이썬에서는 트리를 배열 또는 연결 리스트로 구현할 수 있습니다.
1. 배열로 트리 구현
배열로 트리를 구현하면 자식 노드가 없는 노드가 많을 경우 'None'으로 배열을 채워야 하므로 메모리 공간을 낭비할 수 있습니다.
트리 A = [a, b, c, None, d, e, f, None, None, g, h, i, j]
2. 연결 리스트로 트리 구현
연결 리스트로 구현하면 앞서 배열로 구현했을 때 발생하는 메모리 낭비를 어느정도 보완할 수 있습니다.
이진트리
모든 노드의 차수가 2 이하인 트리를 이진트리라고 부릅니다. 이진트리는 아래와 같은 유형을 가지고 있습니다.
- 정 이진트리(Full Binary Tree)
모든 노드가 0개 또는 2개의 자식 노드를 갖습니다.
- 완전 이진트리(Complete Binary Tree)
마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있습니다.
- 포화 이진트리(Perfect Binary Tree)
모든 노드가 2개의 자식 노드를 갖고 있으며, 모든 리프 노드가 동일한 깊이 또는 레벨을 갖습니다.
트리 순회
각 노드를 정확히 한 번 방문하는 과정으로 아래와 같은 4개의 방법이 있습니다.
1. 전위(Pre-Order) 순회(NLP)
현재(N) 노드 -> 왼쪽 -> 오른쪽
2. 중위(In-Order) 순회(LNR)
왼쪽(L) 노드 -> 현재 -> 오른쪽
3. 후위(Post-Order) 순회(LRN)
왼쪽(L) 노드 -> 오른쪽 -> 현재